主流排序算法概览
- n: 处理的数据规模
- k: “桶”的数量
- In-place: 占用常数内存，不占用额外内存
1. Out-place: 需要占用额外内存 - 稳定性： 排序完成后相等的键值的顺序和排序之前它们的顺序相同
排序的动态图（效果特别好）https://visualgo.net/sorting
冒泡排序（Bubble Sort）
冒泡排序其实很简单，也很容易明白，就是遍历数组，重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。
效果图
1 | function swap(arr,i,j){ |
2 | let temp = arr[i]; |
3 | arr[i] = arr[j]; |
4 | arr[j] = temp; |
5 | } |
6 | |
7 | function bubbleSort(arr){ |
8 | let len=arr.length; |
9 | for(let i=0;i<len;i++){ |
10 | for(let j=0;j<len-i-1;j++){ |
11 | if(arr[j]>arr[j+1]){ |
12 | swap(arr,j+1,j); |
13 | } |
14 | } |
15 | } |
16 | return arr; |
17 | }; |
选择排序（Selection Sort）
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
效果图
1 | function swap(arr,i,j){ |
2 | let temp = arr[i]; |
3 | arr[i] = arr[j]; |
4 | arr[j] = temp; |
5 | } |
6 | |
7 | function selectionSort(arr){ |
8 | |
9 | let len=arr.length, |
10 | minIndex=0; |
11 | |
12 | for(let i=0;i<len;i++){ |
13 | minIndex=i; |
14 | |
15 | for(let j=i+1;j<len;j++){ |
16 | if(arr[j]<arr[minIndex]){ |
17 | minIndex=j; |
18 | } |
19 | } |
20 | |
21 | swap(arr,i,minIndex); |
22 | } |
23 | |
24 | return arr; |
25 | }; |
插入排序（Insertion Sort）
插入排序从数组第二个元素开始跟前面的元素进行比较大小，如果比前者小则把前者往后推，直到遇到比他小的元素停止，然后插入进数组中，将所有元素循环一遍结束。
效果图
1 | function insertionSort(arr){ |
2 | let len=arr.length; |
3 | let cur,pre; |
4 | |
5 | for(let i=1 ; i<len ; i++){ |
6 | pre=i-1; |
7 | cur=arr[i]; |
8 | |
9 | while(cur<arr[pre]&&pre>=0){ |
10 | arr[pre+1]=arr[pre]; |
11 | pre--; |
12 | } |
13 | |
14 | arr[pre+1]=cur; |
15 | } |
16 | |
17 | return arr; |
18 | }; |
希尔排序（Shell Sort）
插入排序的升级版，有间隔的插入，然后间隔逐渐减小至0，即完成排除。
1 | function shellSort(arr){ |
2 | |
3 | let len= arr.length, |
4 | temp, |
5 | gap=1; |
6 | |
7 | if(gap<len/3){gap=gap*3+1;}; |
8 | |
9 | while(gap!==0){ |
10 | for(let i=gap ;i<len ; i+=gap){ |
11 | let pre =i-gap; |
12 | temp=arr[i]; |
13 | while(pre>=0&&temp<arr[pre]){ |
14 | arr[pre+gap]=arr[pre]; |
15 | pre-=gap; |
16 | } |
17 | arr[pre+gap]=temp; |
18 | } |
19 | gap=Math.floor(gap/2); |
20 | } |
21 | return arr; |
22 | } |
归并排序（Merge Sort）
归并排序是将数组用二分法分开，直到分成单个元素为止，然后再逐级合并排列好的元素，直到合并为原来长度为止。
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
效果图
1 | function mergeSort(arr){ |
2 | let len = arr.length; |
3 | |
4 | if(len<2){ |
5 | return arr; |
6 | }; |
7 | |
8 | let middle = Math.floor(len/2)， |
9 | left = arr.slice(0,middle)， |
10 | right = arr.slice(middle); |
11 | |
12 | return merge(mergeSort(left),mergeSort(right)); |
13 | } |
14 | |
15 | function merge(left,right){ |
16 | let result=[]; |
17 | |
18 | while(left.length&&right.length){ |
19 | if(left[0]<=right[0]){ |
20 | result.push(left.shift()); |
21 | }else{ |
22 | result.push(right.shift()); |
23 | } |
24 | }; |
25 | |
26 | while(left.length){ |
27 | result.push(left.shift()); |
28 | }; |
29 | |
30 | while(right.length){ |
31 | result.push(right.shift()); |
32 | }； |
33 | |
34 | return result; |
35 | |
36 | } |
快速排序（Quick Sort）
快速排序就是在数组中随便选一个元素，然后把小于这个元素的数放在一个数组中，大于的放入另一个数组中，然后递归分出来的两个数组做同样的操作，最后把所有结果合并。
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
效果图
1 | function quickSort(arr){ |
2 | let len = arr.length; |
3 | |
4 | if (len <= 1) { return arr; } |
5 | |
6 | let pivot=arr[0], |
7 | left =[], |
8 | right=[]; |
9 | |
10 | for(let i=1;i<len;i++){ |
11 | if(arr[i]<=pivot){ |
12 | left.push(arr[i]); |
13 | }else{ |
14 | right.push(arr[i]); |
15 | } |
16 | } |
17 | |
18 | return quickSort(left).concat(pivot,quickSort(right)); |
19 | } |
堆排序（Heap Sort）
堆排序要理解绝对二叉树，子节点是 2i+1 和 2i+2，父节点是（i-1）/2 js中要向下取整哦。基本思想就是每组二叉树，三个元素把大的放到顶上，小的两个放子节点上，然后遍历完成后，再把最顶上的元素依次跟最后一个元素调换，每次调换之后要把顶上的二叉树调整好顺序，保证最顶上的最大，如果需要变更顺序，要把被调换的那元素所在二叉树调整顺序，直到最顶上元素没有可调换对象为止。
效果图
1 | function swap(arr,i,j){ |
2 | let temp = arr[i]; |
3 | arr[i] = arr[j]; |
4 | arr[j] = temp; |
5 | } |
6 | |
7 | let len; |
8 | |
9 | function buildMaxHeap(arr){ |
10 | len = arr.length; |
11 | for(let i=Math.floor(len/2);i>=0;i--){ |
12 | heapify(arr,i); |
13 | } |
14 | } |
15 | |
16 | function heapify(arr,i){ |
17 | let left=2*i+1, |
18 | right=2*i+2, |
19 | largest=i; |
20 | |
21 | if(left<len&&arr[left]>arr[largest]){ |
22 | largest=left; |
23 | } |
24 | |
25 | if(right<len&&arr[right]>arr[largest]){ |
26 | largest=right; |
27 | } |
28 | |
29 | if(largest!==i){ |
30 | swap(arr,i,largest); |
31 | heapify(arr,largest); |
32 | } |
33 | } |
34 | |
35 | function heapSort(arr){ |
36 | buildMaxHeap(arr); |
37 | |
38 | for(let i=len-1;i>=0;i--){ |
39 | swap(arr,0,i); |
40 | len--; |
41 | heapify(arr,0); |
42 | } |
43 | |
44 | return arr; |
45 | } |
计数排序（Counting Sort）
计数排序就是在另一个数组中记录小于遍历到的元素的个数，直到所有元素便利完成，另一个数组中的数就是数组的正确顺序，存起即可。
效果图
1 | function countingSort(arr) { |
2 | |
3 | let arrLen = arr.length, |
4 | box = [], |
5 | bucket = []; |
6 | |
7 | for (let i = 0; i < arrLen; i++) { |
8 | box[i]=-1; |
9 | for (let j = 0; j < arrLen; j++) { |
10 | if(arr[i]>=arr[j]){ |
11 | box[i]++; |
12 | } |
13 | } |
14 | } |
15 | |
16 | for (let i = 0; i < arrLen; i++) { |
17 | bucket[box[i]]=arr[i] |
18 | } |
19 | |
20 | return bucket; |
21 | } |
参考文档 http://www.jianshu.com/p/1b4068ccd505;
If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !