常用排序算法之javaScript实现

　　笔试面试经常涉及各种算法，本文简要介绍常用的一些算法，并用Javascript实现。

1、插入排序

1）算法简介

　　插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2）算法描述和实现　

　　一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

　　JavaScript代码实现：

 1 function insertionSort(array) { 2     if (Object.PRototype.toString.call(array).slice(8, -1) === 'Array') { 3         for (var i = 1; i < array.length; i++) { 4             var key = array[i]; 5             var j = i - 1; 6             while (j >= 0 && array[j] > key) { 7                 array[j + 1] = array[j]; 8                 j--; 9             }10             array[j + 1] = key;11         }12         return array;13     } else {14         return 'array is not an Array!';15     }16 }

3）算法分析

• 最佳情况：输入数组按升序排列。T(n) = O(n)
• 最坏情况：输入数组按降序排列。T(n) = O(n2)
• 平均情况：T(n) = O(n2)

二、二分插入排序

1）算法简介

　　二分插入（Binary-insert-sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接插入排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。

2）算法描述和实现　　

　　一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置；
3. 将新元素插入到该位置后；
4. 重复上述两步。

　　JavaScript代码实现：

 1 function binaryInsertionSort(array) { 2     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { 3         for (var i = 1; i < array.length; i++) { 4             var key = array[i], left = 0, right = i - 1; 5             while (left <= right) { 6                 var middle = parseInt((left + right) / 2); 7                 if (key < array[middle]) { 8                     right = middle - 1; 9                 } else {10                     left = middle + 1;11                 }12             }13             for (var j = i - 1; j >= left; j--) {14                 array[j + 1] = array[j];15             }16             array[left] = key;17         }18         return array;19     } else {20         return 'array is not an Array!';21     }22 }

3）算法分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

三、选择排序

1）算法简介

　　选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2）算法描述和实现

　　n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

1. 初始状态：无序区为R[1..n]，有序区为空；
2. 第i趟排序(i=1,2,3...n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3. n-1趟结束，数组有序化了。

　　JavaScript代码实现：

 1 function selectionSort(array) { 2     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { 3         var len = array.length, temp; 4         for (var i = 0; i < len - 1; i++) { 5             var min = array[i]; 6             for (var j = i + 1; j < len; j++) { 7                 if (array[j] < min) { 8                     temp = min; 9                     min = array[j];10                     array[j] = temp;11                 }12             }13             array[i] = min;14         }15         return array;16     } else {17         return 'array is not an Array!';18     }19 }

3）算法分析

• 最佳情况：T(n) = O(n2)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

四、冒泡排序

1）算法简介

　　冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2）算法描述和实现

　　具体算法描述如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

　　JavaScript代码实现：

 1 function bubbleSort(array) { 2     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { 3         var len = array.length, temp; 4         for (var i = 0; i < len - 1; i++) { 5             for (var j = len - 1; j >= i; j--) { 6                 if (array[j] < array[j - 1]) { 7                     temp = array[j]; 8                     array[j] = array[j - 1]; 9                     array[j - 1] = temp;10                 }11             }12         }13         return array;14     } else {15         return 'array is not an Array!';16     }17 }

3）算法分析

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

五、快速排序

1）算法简介

　　快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2）算法描述和实现

　　快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

1. 从数列中挑出一个元素，称为"基准"（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

　　JavaScript代码实现：

 1 //方法一 2 function quickSort(array, left, right) { 3     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') { 4         if (left < right) { 5             var x = array[right], i = left - 1, temp; 6             for (var j = left; j <= right; j++) { 7                 if (array[j] <= x) { 8                     i++; 9                     temp = array[i];10                     array[i] = array[j];11                     array[j] = temp;12                 }13             }14             quickSort(array, left, i - 1);15             quickSort(array, i + 1, right);16         };17     } else {18         return 'array is not an Array or left or right is not a number!';19     }20 }  21 var aaa = [3, 5, 2, 9, 1];22 quickSort(aaa, 0, aaa.length - 1);23 console.log(aaa);24 25 26 //方法二27 var quickSort = function(arr) {28 　　if (arr.length <= 1) { return arr; }29 　　var pivotIndex = Math.floor(arr.length / 2);30 　　var pivot = arr.splice(pivotIndex, 1)[0];31 　　var left = [];32 　　var right = [];33 　　for (var i = 0; i < arr.length; i++){34 　　　　if (arr[i] < pivot) {35 　　　　　　left.push(arr[i]);36 　　　　} else {37 　　　　　　right.push(arr[i]);38 　　　　}39 　　}40 　　return quickSort(left).concat([pivot], quickSort(right));41 };

3）算法分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(nlogn)

六、堆排序

1）算法简介

　　堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

2）算法描述和实现

　　具体算法描述如下：

1. 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]；
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

　　JavaScript代码实现：

 1 /*方法说明：堆排序 2 @param  array 待排序数组*/             3 function heapSort(array) { 4     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { 5         //建堆 6         var heapSize = array.length, temp; 7         for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { 8             heapify(array, i, heapSize); 9         }10         11         //堆排序12         for (var j = heapSize - 1; j >= 1; j--) {1