JavaScript排序
果冻OoO 人气:0一、插入排序
插入排序有直接插入排序,折半插入排序,希尔排序,这里只实现常用的直接插入排序
直接插入排序
将左侧序列看成一个有序序列,每次将一个数字插入该有序序列。
插入时,从有序序列最右侧开始比较,若比较的数较大,后移一位。
function insertSort(array) { //第一个默认已经排好 for (let i = 1; i < array.length; i++) { let target = i; for (let j = i - 1; j >= 0; j--) { if (array[target] < array[j]) { [array[target], array[j]] = [array[j], array[target]] target = j; } else { break; } } } return array; }
复杂度
时间复杂度:O(n2)
空间复杂度:O(1)
稳定性
稳定
二、交换排序
(1)冒泡排序
循环数组,比较当前元素和上一个元素,如果当前元素比上一个元素小,向下冒泡。
这样一次循环之后最前一个数就是本数组最小的数。
下一次循环继续上面的操作,不循环已经排序好的数。
优化:当一次循环没有发生冒泡,说明已经排序完成,停止循环。
function bubbleSort(array) { //第一个循环是所需次数 for (let j = 0; j < array.length; j++) { let complete = true; for (let i = array.length-1; i>j; i--) { // 比较相邻数 if (array[i] < array[i -1]) { [array[i], array[i - 1]] = [array[i - 1], array[i]]; complete = false; } } // 没有冒泡结束循环 if (complete) { break; } } return array; }
复杂度
时间复杂度:O(n2)
空间复杂度:O(1)
稳定性
稳定
(2)快速排序
快速排序:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据要小,再按这种方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,使整个数据变成有序序列。
实现步骤:
- 选择一个基准元素target(一般选择第一个数)
- 将比target小的元素移动到数组左边,比target大的元素移动到数组右边
- 分别对target左侧和右侧的元素进行快速排序
从上面的步骤中我们可以看出,快速排序也利用了分治的思想(将问题分解成一些小问题递归求解)
下面是对序列6、1、2、7、9、3、4、5、10、8排序的过程:
//JS自带的sort()就是快排 function quickSort(array, start, end) { if (end - start < 1) { return; } const target = array[start]; let l = start; let r = end; while (l < r) { while (l < r && array[r] >= target) { r--; } array[l] = array[r]; while (l < r && array[l] < target) { l++; } array[r] = array[l]; } array[l] = target; quickSort(array, start, l - 1); quickSort(array, l + 1, end); return array; }
复杂度
时间复杂度:平均O(nlogn),最坏O(n2),实际上大多数情况下小于O(nlogn)
空间复杂度:O(logn)(递归调用消耗)
稳定性
不稳定
三、选择排序
(1)简单选择排序
每次循环选取一个最小的数字放到前面的有序序列中。
function selectionSort(array) { for (let i = 0; i < array.length - 1; i++) { let minIndex = i; for (let j = i + 1; j < array.length; j++) { if (array[j] < array[minIndex]) { minIndex = j; } } [array[minIndex], array[i]] = [array[i], array[minIndex]]; } }
复杂度
时间复杂度:O(n2)
空间复杂度:O(1)
稳定性
不稳定
(2)堆排序
创建一个大顶堆,大顶堆的堆顶一定是最大的元素。
交换第一个元素和最后一个元素,让剩余的元素继续调整为大顶堆。
从后往前以此和第一个元素交换并重新构建,排序完成。
function heapSort(array) { creatHeap(array); console.log(array); // 交换第一个和最后一个元素,然后重新调整大顶堆 for (let i = array.length - 1; i > 0; i--) { [array[i], array[0]] = [array[0], array[i]]; adjust(array, 0, i); } return array; } // 构建大顶堆,从第一个非叶子节点开始,进行下沉操作 function creatHeap(array) { const len = array.length; const start = parseInt(len / 2) - 1; for (let i = start; i >= 0; i--) { adjust(array, i, len); } } // 将第target个元素进行下沉,孩子节点有比他大的就下沉 function adjust(array, target, len) { for (let i = 2 * target + 1; i < len; i = 2 * i + 1) { // 找到孩子节点中最大的 if (i + 1 < len && array[i + 1] > array[i]) { i = i + 1; } // 下沉 if (array[i] > array[target]) { [array[i], array[target]] = [array[target], array[i]] target = i; } else { break; } } }
复杂度
时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性
不稳定
四、归并排序
利用归并的思想实现的排序方法。
该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。(分治法将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
- 将已有序的子序列合并,得到完全有序的序列
- 即先使每个子序列有序,再使子序列段间有序
- 若将两个有序表合并成一个有序表,称为二路归并
分割:
- 将数组从中点进行分割,分为左、右两个数组
- 递归分割左、右数组,直到数组长度小于2
归并:
如果需要合并,那么左右两数组已经有序了。
创建一个临时存储数组temp,比较两数组第一个元素,将较小的元素加入临时数组
若左右数组有一个为空,那么此时另一个数组一定大于temp中的所有元素,直接将其所有元素加入temp
function mergeSort(array) { if (array.length < 2) { return array; } const mid = Math.floor(array.length / 2); const front = array.slice(0, mid); const end = array.slice(mid); return merge(mergeSort(front), mergeSort(end)); } function merge(front, end) { const temp = []; while (front.length && end.length) { if (front[0] < end[0]) { temp.push(front.shift()); } else { temp.push(end.shift()); } } while (front.length) { temp.push(front.shift()); } while (end.length) { temp.push(end.shift()); } return temp; }
做题时,上面多了删除过程,特别大的例子,时间也可能会超,用下面的方法
function merge(left, right){ let leftLen = left.length, rightLen = right.length; let i = 0, j = 0; let temp = new Array(leftLen + rightLen); for(let cur = 0; cur < leftLen + rightLen; cur++){ // 检查i, j有没有超界 if(i >= leftLen) temp[cur]= right[j++]; else if(j >= rightLen) temp[cur] = left[i++]; else if(left[i] <= right[j]){ temp[cur] = left[i++]; }else{ temp[cur] = right[j++]; } } return temp; }
复杂度
时间复杂度:O(nlogn)
空间复杂度:O(n)
稳定性
稳定
加载全部内容