常见的排序算法总结（JavaScript）(2)

　　插入排序的思想是将原始数组划分成两侧，一侧是有序数组，一侧是无序数组。每次取出无序数组的一个元素，将它插入到有序数组的正确位置上，这种方式也会导致有序数组中其插入位置之后的元素全部后移。插入排序的思想类似于我们抓扑克牌。

　　原理：假设排序方式为增序，数组长度为 N。初始设 A[0] 为有序数组，A[1] ~ A[N-1] 为无序数组，取出 A[1] 将其插入至有序数组中的正确位置，使得有序数组增大为 A[0] ~ A[1]。继续取 A[2] 将其插入至有序表数组的正确位置，以此类推，直至无序数组取完。

　　下面这张图展示了插入排序的全过程：

　　下面这张图展示了在宏观层面上插入排序的全过程：

平均时间复杂度   最优时间复杂度   最差时间复杂度   空间复杂度  
O(n^2)   O(n^2)   O(n^2)   O(1)  

 

1 function insertSort (arr) { 2 for(var i = 0, length1 = arr.length; i < length1; i ++){ 3 for(var j = 0, length2 = i + 1; j < length2; j ++){ 4 if(arr[j] > arr[length2]){ 5 var temp = arr[length2]; 6 for(var k = length2; k > j; k --){ 7 arr[k] = arr[k-1]; 8 } 9 arr[j] = temp; 10 } 11 } 12 } 13 }

 四、 希尔排序

　　希尔排序是优化过后的插入，其算法的思想是在插入排序的基础上加上了一个步长 gap，通过步长将数组分成若干个子项，先分别对子项进行插入排序，使得每一个元素朝着最终目的地跨了一大步。然后逐步缩小步长，这种排序算法也是不稳定的。

　　原理：假设排序方式为增序，数组长度为 N。首先取步长 gap = N/2，那么便将 N 长度的数组拆分成了 [A[0], A[gap]]，[A[1], A[gap+1]]，[A[2], A[gap+3]] ... ... [A[gap-1], A[N-1]] 子数组，分别对子数组进行插入排序。随后逐步缩小步长，再进行插入排序，直至步长为 1。

　　下面这张图展示了希尔排序的全过程：

　　下面这张图展示了希尔排序在宏观上的全过程：

平均时间复杂度   最优时间复杂度   最差时间复杂度   空间复杂度  
O(nLogn)~O(n^2)   O(n^1.3)   O(n^2)   O(1)  

 

1 function shellSort(arr) { 2 var gap = Math.floor(arr.length / 2); 3 while (gap >= 1) { 4 for (var i = 0; i < gap; i++) { 5 for (var j = i; j < arr.length; j += gap) { 6 for (var k = i, length = j + gap; k < length; k += gap) { 7 if (arr[k] > arr[length]) { 8 var temp = arr[length]; 9 for (var x = length; x > k; x = x - gap) { 10 arr[x] = arr[x - gap]; 11 } 12 arr[k] = temp; 13 } 14 } 15 } 16 } 17 gap = Math.floor(gap / 2); 18 } 19 }

五、归并排序