排序算法
一、冒泡排序
复杂度：O(n2)
代码实现
public static void sort(int arr[]){ for( int i = 0 ; i < arr.length - 1 ; i++ ){ for(int j = 0;j < arr.length - 1 - i ; j++){ int temp = 0; if(arr[j] < arr[j + 1]){ temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }冒泡优化
冒泡有一个最大的问题就是这种算法不管不管你有序还是没序，闭着眼睛把你循环比较了再说。
针对这个问题，我们可以设定一个临时遍历来标记该数组是否已经有序，如果有序了就不用遍历了。
public static void sort(int arr[]){ for( int i = 0;i < arr.length - 1 ; i++ ){ boolean isSort = true; for( int j = 0;j < arr.length - 1 - i ; j++ ){ int temp = 0; if(arr[j] < arr[j + 1]){ temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; isSort = false; } } if(isSort){ break; } } }
二、选择排序
复杂度：O(n2)
首先，找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置，第二步，在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置，如此循环，直到整个数组排序完成。
代码实现
public static void sort(int arr[]){ for( int i = 0;i < arr.length ; i++ ){ int min = i;//最小元素的下标 for(int j = i + 1;j < arr.length ; j++ ){ if(arr[j] < arr[min]){ min = j;//找最小值 } } //交换位置 int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } }
三、插入排序
复杂度：O(n2)
代码实现
function insertSort(arr) { let length = arr.length; for(let i = 1; i < length; i++) { let temp = arr[i]; let j = i; for(; j > 0; j--) { if(temp >= arr[j-1]) { break; // 当前考察的数大于前一个数，证明有序，退出循环 } arr[j] = arr[j-1]; // 将前一个数复制到后一个数上 } arr[j] = temp; // 找到考察的数应处于的位置 } return arr; }
四、希尔排序
也称作“缩小增量排序”，是插入排序的一种更高效的改进版本。
代码实现
public static void sort(int[] arr) { int length = arr.length; //区间 int gap = 1; while (gap < length) { gap = gap * 3 + 1; } while (gap > 0) { for (int i = gap; i < length; i++) { int tmp = arr[i]; int j = i - gap; //跨区间排序 while (j >= 0 && arr[j] > tmp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } gap = gap / 3; } }
五、归并排序
将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。
复杂度： O(nlogn)
代码实现
自顶向下
function mergeSort(list) { if(list.length <= 1) { return list; } let middle = Math.floor(list.length/2); let left = list.slice(0, middle); let right = list.slice(middle); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { let result = []; while(left.length && right.length) { if(left[0] <= right[0]) { result.push(left.shift()) }else { result.push(right.shift()) } } while(left.length) { result.push(left.shift()) } while(right.length) { result.push(right.shift()) } return result; }
自底向上
// 自底向上 function mergeSort2(list) { const len = list.length; if(len <= 1) { return list; } let step = 1; let left,right; while(step < len) { left = 0; right = step; while(right + step < len) { merge(list, left, left + step, right, right+step); left = right + step; right = left + step; } if(right < len) { merge(list, left, left + step, right, len); } step *= 2; } return list } // 合并两个数组，其实是有序的数组，效率较高 function merge(list, startLeft, stopLeft, startRight, stopRight) { let rightArr = new Array(stopRight - startRight + 1); let leftArr = new Array(stopLeft - startLeft + 1); let k = startRight; for(let i = 0; i < rightArr.length - 1; i++) { rightArr[i] = list[k]; k++; } k = startLeft for(let i = 0; i < leftArr.length -1; i++) { leftArr[i] = list[k]; k++; } rightArr[rightArr.length - 1] = Infinity; leftArr[leftArr.length - 1] = Infinity; let m = 0; let n = 0; k =startLeft; for(; k < stopRight; k++) { if(leftArr[m] <= rightArr[n]) { list[k] = leftArr[m]; m++; }else { list[k] = rightArr[n]; n++; } } }
六、快速排序
快速排序的核心思想也是分治法，分而治之。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边，然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。
代码实现
function fastSort(list) { if(list.length <=1 ) { return list; } let pivotIndex = Math.floor(list.length/2); let pivot = list.splice(pivotIndex, 1)[0]; let left = [] let right = [] for(var i=0; i<list.length; i++) { if(list[i]<=pivot) { left.push(list[i]); }else { right.push(list[i]); } } return fastSort(left).concat([pivot], fastSort(right)); }
复杂度
快速排序的时间复杂度和归并排序一样，O(n log n)，但这是建立在每次切分都能把数组一刀切两半差不多大的前提下，如果出现极端情况，比如排一个有序的序列，如[ 9，8，7，6，5，4，3，2，1 ]，选取基准值 9 ，那么需要切分 n - 1 次才能完成整个快速排序的过程，这种情况下，时间复杂度就退化成了 O(n2)，当然极端情况出现的概率也是比较低的。
七、堆排序
复杂度：O(nlogn)
例题：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/comments/
function ListNode(val) { this.val = val; this.next = null; } var mergeKLists = function(lists) { let pq = new MinHeap(lists.length) for(let i = 0; i< lists.length; i++) { if(lists[i] != null) { pq.add(lists[i]); } } let dummyHead = new ListNode(0); let cur = dummyHead; while(!pq.isEmpty()) { let node = pq.extractMin(); cur.next = node; cur = node; if(node.next != null) { pq.add(node.next); } } return dummyHead.next; }; class MinHeap { constructor(capacity) { this.capacity = capacity; this.data = [] this.size = 0; } isEmpty() { return this.size === 0; } add(node) { if(this.size === this.capacity) { return } this.data[this.size] = node; this.shiftUp(this.size); this.size++; } swap(i, j) { let temp = this.data[i]; this.data[i] = this.data[j]; this.data[j] = temp; } shiftUp(k) { while(k > 0 && this.data[k].val < this.data[Math.floor((k - 1) / 2)].val) { let parent = Math.floor((k - 1) / 2); this.swap(k, parent) k = parent } } shiftDown(k) { while(2*k + 1 < this.size) { let j = 2 * k + 1; if(j + 1 < this.size && this.data[j + 1].val < this.data[j].val) { j++; } if(this.data[k].val <= this.data[j].val) { break; } this.swap(k, j) k = j; } } extractMin() { if(this.size === 0) { return; } let ret = this.data[0]; this.data[0] = this.data[--this.size]; this.shiftDown(0); return ret; } }
八、计数排序
复杂度
复杂度为 O(n + m )，m 指的是数据量，说的简单点，计数排序算法的时间复杂度约等于 O(n)，快于任何比较型的排序算法。
计数排序只适用于正整数并且取值范围相差不大的数组排序使用，它的排序的速度是非常可观的。
九、桶排序
复杂度
在额外空间充足的情况下，尽量增大桶的数量，极限情况下每个桶只有一个数据时，或者是每只桶只装一个值时，完全避开了桶内排序的操作，桶排序的最好时间复杂度就能够达到 O(n)。
十、基数排序
数据按位数切割成不同的数字，然后按每个位数分别比较。