文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

十五周算法训练营——数组排序

2024-11-30 16:04

关注

冒泡

冒泡排序的思路:遍历数组,然后将最大数沉到最底部。
「时间复杂度:O(N^2);」
「空间复杂度:O(1)」

function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

function bubbleSort(arr) {
if (arr == null || arr.length <= 0) {
return [];
}

const len = arr.length;
for (let end = len - 1; end > 0; end--) {
for (let i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}

}

return arr;
}

选择

选择排序的实现思路:遍历数组,把最小数放在头部。
「时间复杂度:O(N^2);」
「空间复杂度:O(1)」

function selectionSort(arr) {
if (!Array.isArray(arr) || arr.length <= 0) {
return [];
}

const swap = (arr, i, j) => {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};

for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i;

for (let j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}

swap(arr, i, minIndex);
}

return arr;
}

插入排序

插入排序实现思路:将一个新的数,和前面的比较,只要当前数小于前一个则和前一个交换位置,否则终止。
「时间复杂度:O(N^2);」
「空间复杂度:O(1)」

function insertSort(arr) {
if (!Array.isArray(arr) || arr.length <= 0) {
return [];
}

const swap = (arr, i, j) => {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};

for (let i = 1; i < arr.length; i++) {
for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}

return arr;
}

归并排序

归并排序的思路:
1.先左侧部分排好序。
2.再右侧部分排好序。
3.再准备一个辅助数组,用外排的方式,小的开始填,直到有个动到末尾,将另一个数组剩余部分拷贝到末尾。
4.再将辅助数组拷贝回原数组。
「时间复杂度:O(N * logN)」
「空间复杂度:O(N)」

归并排序实际上就是一个二叉树的后序遍历过程。

function mergeSort(arr) {
if (arr == null || arr.length <= 0) {
return [];
}
sortProcess(arr, 0, arr.length - 1);

return arr;
}

function sortProcess(arr, L, R) {
// 递归的终止条件,就是左右边界索引一样
if (L === R) {
return;
}
const middle = L + ((R - L) >> 1); // 找出中间值
sortProcess(arr, L, middle); // 对左侧部分进行递归
sortProcess(arr, middle + 1, R); // 对右侧部分进行递归
merge(arr, L, middle, R);
}

function merge(arr, L, middle, R) {
var help = [];
var l = L;
var r = middle + 1;
var index = 0;

while (l <= middle && r <= R) {
help[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
}

while (l <= middle) {
help.push(arr[l++]);
}

while (r <= R) {
help.push(arr[r++]);
}

for (let i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}

// arr.splice(L, help.length, ...help); // 利用了ES6的语法
}

快排

快速排序实现思路:随机取出一个值进行划分,大于该值放右边,小于该值放左边(该算法在经典快排的基础上经过荷兰国旗思想和随机思想进行了改造)。
「时间复杂度:O(N*logN)」
「空间复杂度:O(logN)」

快速排序其实就是二叉树中前序遍历的处理方式。

function quickSort(arr) {
if (arr == null || arr.length <= 0) {
return [];
}

quick(arr, 0, arr.length - 1);
return arr;
}

function quick(arr, L, R) {
// 递归结束条件是L >= R
if (L < R) {
// 随机找一个值,然后和最后一个值进行交换,将经典排序变为快速排序(因为经典排序每次都取最后一个数据去对比,对应0,1,2……n的情况,其复杂度为O(N^2))
swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R);
//利用荷兰国旗问题获得划分的边界,返回的值是小于区域的最大索引和大于区域的最小索引,在这利用荷兰国旗问题将等于区域部分就不用动了
const tempArr = partition(arr, L, R, arr[R]);
quick(arr, L, tempArr[0]);
quick(arr, tempArr[1], R);
}
}

// 返回值是小于区域的最后的索引和大于区域的第一个索引
function partition(arr, L, R, num) {
var less = L - 1;
var more = R + 1;
var cur = L;
while (cur < more) {
if (arr[cur] < num) {
swap(arr, ++less, cur++);
} else if (arr[cur] > num) {
swap(arr, --more, cur);
} else {
cur++;
}
}

return [less, more];
}

function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

堆排序

堆排序思路:
1.让数组变成大根堆。
2.把最后一个位置和堆顶做交换。
3.则最大值在最后,则剩下部分做heapify,则重新调整为大根堆,则堆顶位置和该部分最后位置做交换。
4.重复进行,直到减完,则这样最后就调整完毕,整个数组排完序(为一个升序)。
「时间复杂度:O(N * logN)」
「空间复杂度:O(1)」

function heapSort(arr) {
if (arr == null || arr.length <= 0) {
return [];
}

// 首先是建立大顶堆的过程
for (let i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}

var size = arr.length;//这个值用来指定多少个数组成堆,当得到一个排序的值后这个值减一

//将堆顶和最后一个位置交换

//由于前面已经是大顶堆,所以直接交换
swap(arr, 0, --size);
while(size > 0) {
// 重新变成大顶堆
heapify(arr, 0, size);
// 进行交换
swap(arr, 0, --size);
}

return arr;
}

// 加堆过程中
function heapInsert(arr, index) {
//比较当前位置和其父位置,若大于其父位置,则进行交换,并将索引移动到其父位置进行循环,否则跳过
//结束条件是比父位置小或者到达根节点处
while (arr[index] > arr[parseInt((index - 1) / 2)]) {
// 进行交换
swap(arr, index, parseInt((index - 1) / 2));
index = parseInt((index - 1) / 2);
}
}

//减堆过程

function heapify(arr, index, size) {
let left = 2 * index + 1;
while (left < size) {
let largest = (left + 1 < size && arr[left] < arr[left + 1]) ? left + 1 : left;
largest = arr[index] > arr[largest] ? index : largest;

//如果最大值索引和传进来索引一样,则该值到达指定位置,直接结束循环
if (index == largest) {
break;
}

// 进行交换,并改变索引和其左子节点
swap(arr, index, largest);
index = largest;
left = 2 * index + 1;
}
}

function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
来源:前端点线面内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯