十大经典排序算法（动图演示）( 二 ) 作者|修罗神·唐三来源|urlify.cn/bMfU

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3 ，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5 。

3.2 动图演示

文章插图
3.2 代码实现

 1 function selectionSort(arr) { 2varlen = arr.length; 3varminIndex, temp; 4for(vari = 0; i < len - 1; i++) { 5minIndex = i; 6for(varj = i + 1; j < len; j++) { 7if(arr[j] < arr[minIndex]) {// 寻找最小的数 8minIndex = j;// 将最小数的索引保存 9}10}11temp = arr[i];12arr[i] = arr[minIndex];13arr[minIndex] = temp;14}15returnarr;16 }

3.4 算法分析插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 4、希尔排序（Shell Sort）1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。 4.1 算法描述先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1 ， t2 ， … ， tk ，其中ti>tj ， tk=1；
按增量序列个数k ，对序列进行k 趟排序；
每趟排序，根据对应的增量ti ，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 动图演示4.3 代码实现

 1 function insertionSort(arr) { 2varlen = arr.length; 3varpreIndex, current; 4for(vari = 1; i < len; i++) { 5preIndex = i - 1; 6current = arr[i]; 7while(preIndex >= 09preIndex--;10}11arr[preIndex + 1] = current;12}13returnarr;14 }

4.4 算法分析希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。5、归并排序（Merge Sort）归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。5.1 算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

文章插图
5.3 代码实现

 1 function shellSort(arr) { 2varlen = arr.length; 3for(vargap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) { 4// 注意：这里和动图演示的不一样 ， 动图是分组执行 ， 实际操作是多个分组交替执行 5for(vari = gap; i < len; i++) { 6varj = i; 7varcurrent = arr[i]; 8while(j - gap >= 0 10j = j - gap;11}12arr[j] = current;13}14}15returnarr;16 }

5.4 算法分析归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。 6、快速排序（Quick Sort）快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 6.1 算法描述快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：