Javascript中的冒泡排序，插入排序，选择排序，快速排序，归并排序，堆排序算法性能分析...

今天药忘吃喽~ 2023-08-17 17:19 106阅读 0赞

阿里面试中有一道题是这样的：

请用JavaScript语言实现 sort 排序函数，要求：sort(\[5, 100, 6, 3, -12\]) // 返回 \[-12, 3, 5, 6, 100\]，如果你有多种解法，请阐述各种解法的思路及优缺点。（仅需用代码实现一种解法，其它解法用文字阐述思路即可）

那我们就来看一下各种解法的思路以及优缺点~

**简单排序**

1冒泡法：

原理：对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻两个数据的次序与要求的不同时，即将两个数据进行互换，第一次扫描结束后，进行第二次扫描，直到所有数据符合要求。

优点：

平均时间复杂度O（n\*n），是比较容易实现的算法，相对稳定。

缺点：

慢，每次只能移动相邻两个数据

1 var sortArray=new Array();
 2 var temp;
 3 sortArray=id_list.split(":");
 4 for(var i=0;i<sortArray.length;i++)
 5 {
 6 for(var j=0;j<i;j++)
 7 {
 8 
 9 if(parseInt(sortArray[j])>parseInt(sortArray[i]))
 10 {
 11 temp=sortArray[j];
 12 sortArray[j]=sortArray[i];
 13 sortArray[i]=temp;
 14 }
 15 }
 16 }

2插入排序：  
原理：首先新建一个空列表用于保存已经排序的有序数列A，从原序列B中取出一个数，逐个与有序列表中的数比较，如果b\[0\]大于a\[0\]则跳过，继续比较b\[0\]与a\[1\],如果前者仍大于后者，则继续跳过，直到b\[0\]小于a\[x\],则将b\[0\]插入到a\[x\]的位置，a\[x\]及其后面的往后移动一位。使其仍旧保持有序状态。然后再取出一个数按相同方法插入，直至原数列为空。它借助了“逐步扩大成果”的思想，使有序列表的长度逐渐增长，直至等于元列表的长度即排序完成。

优点：

容易实现，稳定，快，适合少量数据比较。时间复杂度为O（n\*n）。

缺点：

效率不高，比较次数不一定，比较次数越少，插入点后的数据移动越多，如果数据量庞大的话，可以使用链表来解决这个问题~

1 function insertSort(){
 2 var A=[5,2,4,6,1,3];
 3 
 4 document.write("原数组:")
 5 for (var n = 0; n < A.length; n++) {
 6 document.write(A[n] + " ");
 7 }
 8 document.write("原数组长度:"+A.length+" ");
 9 var key;
 10 var i;
 11 for(var j=1;j<A.length;j++){
 12 key=A[j];
 13 i=j-1;
 14 while(i>-1&&A[i]>key){
 15 A[i+1]=A[i];
 16 i=i-1;
 17 }
 18 A[i+1]=key;
 19 
 20 //输出结果
 21 document.write("第" + j + "遍排序的结果是:")
 22 for (var n = 0; n < A.length; n++) {
 23 document.write(A[n] + " ");
 24 }
 25 document.write(" ")
 26 }
 27 }

3选择排序

原理：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好的数列的最后，直到全部待排序的数据元素排完。

优点：进行（n-1）趟排序即可排序完成，时间复杂度为n的平方O（n\*n）

缺点：比较次数比较多，每一趟从数据中选出的目标数据都是和剩下所有数据比较的结果。

\*注意和冒泡排序的区别 选择排序是从一个序列到另一个序列，冒泡排序是在本身序列的排序，选择排序性能稍稍好于冒泡排序。

1 function selectSort(array) {
 2 var min, temp; ;
 3 for (var i = 0; i < array.length; i++) {
 4 min = i;
 5 for (var j = i + 1; j < array.length; j++) {
 6 if (array[min] > array[j])
 7 min = j;
 8 }
 9 if (min != i) {
 10 temp = array[i];
 11 array[i] = array[min];
 12 array[min] = temp;
 13 }
 14 /* 输出结果 */
 15 document.write("第 + i + "遍排序的结果是:")
 16 for (var n = 0; n < array.length; n++) {
 17 document.write(array[n] + ",");
 18 }
 19 
 20 document.write(" ")
 21 /* 输出结果结束 */
 22 
 23 }
 24 }

**高效排序**

快速排序

原理：快速排序是目前已知速度最快的排序方法，，排序方法所运用的思想和我们众所周知的二分法一脉相承，专业一点的话称为“分治策略”。保证列表的前半部分都小于后半部分，然后分别对两部分进行排序，这样比较前半部分时就不需要和后半部分比较了，这种方法大大减少了数据间的不必要排序，因而高效~具体步骤：假设要对一组数据进行升序排列，先任取数据a\[x\]作为基准，，比较a\[x\]与其他数据并排序，使a\[x\]排在数据的第k位，并且使a\[1\]~a\[k-1\]中的每一个数据都小于a\[x\],a\[k+1\]~a\[n\]中的每一个数据都大于a\[k\]，然后按同样的方法对两组数据进行快速排序。

优点：速度极快，数据移动较少 平均时间复杂度为(n\*log n)

缺点：不稳定

1 var count = 0;
 2 function quickSort(array, low, high) {
 3 var temp;
 4 
 5 if (low < high) {
 6 
 7 var keypoint = QuickSortHelp(array, low, high);
 8 count++;
 9 document.write(" 第台? + count + "遍括?排?序ò的?结á果?是?:")
 10 for (var l = 0; l < array.length; l++) {
 11 document.write(array[l] + ",");
 12 }
 13 quickSort(array, low, keypoint - 1);
 14 quickSort(array, keypoint + 1, high);
 15 
 16 
 17 }
 18 }
 19 function QuickSortHelp(array, low, high) {
 20 while (low < high) {
 21 
 22 while (low < high && array[low] <= array[high]) {
 23 high--;
 24 }
 25 temp = array[low];
 26 array[low] = array[high];
 27 array[high] = temp;
 28 while (low < high && array[low] <= array[high]) {
 29 low++
 30 }
 31 temp = array[low];
 32 array[low] = array[high];
 33 array[high] = temp;
 34 
 35 }
 36 return low;
 37 }
 38

归并排序：

原理：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。特点是相等的元素的顺序不会改变，这对要排序数据包含多个信息按其中的某一个信息排序，要求其他信息尽量按输入的顺序排列时很重要，这也是比快速排序优势的地方。归并排序对数据的有序性不敏感，其时间复杂度在任何情况下都是O(nlog 2n)，所以如果数据节点数据量大的话不是很合适。但是如果改造成索引操作的话效果还是很棒的~

优缺点在原理中说明~

1//source源数组
 2//dest目标数组
 3//s起始下标
 4//t目标下标
 5 function mSort(source, dest, s, t) {
 6 var m; //取中间值
 7 var dest2 = new Array();
 8 if (s == t) {
 9 dest[s] = source[s];
 10 
 11 }
 12 else {
 13 m = Math.floor((s + t) / 2);
 14 mSort(source, dest2, s, m);
 15 mSort(source, dest2, m+1 , t);
 16 merge(dest2, dest, s, m, t);
 17 /* 输出结果 */
 18 document.write(" 第 + ++count + "遍排序的结果是:")
 19 for (var n = 0; n < dest.length; n++) {
 20 document.write(array[n] + ",");
 21 }
 22 
 23 }
 24 
 25 }
 26 
 27
 28//source原数组
 29//dest排序后的数组
 30//s第一个下标
 31//m第二个数组下标
 3233 function merge(source, dest, s, m, n) {
 34 for (var j = m+1, k = s; j <= n && s <= m; k++) {
 35 if (source[s] < source[j]) {
 36 dest[k] = source[s++];
 37 }
 38 else {
 39 dest[k] = source[j++];
 40 }
 41 }
 42 
 43 //将剩余排不完的有序数组加入到dest的末端
 44 if (s <= m) {
 45 for (var l = 0; l <= m - s; l++) {
 46 dest[k + l] = source[s+l];
 47 }
 48 }
 49 if (j <= n) {
 50 for (var l = 0; l <= n - j; l++) {
 51 dest[k + l] = source[j+l];
 52 }
 53 
 54 }
 55 }

堆排序：

原理：首先新建一个空列表，在带排序数列中找到最大的数字，将其加在空列表的末尾，并将其从原数列中删除，重复以上步骤，直至原数列为空。

\*请注意与插入排序的区别，堆排序时间复杂度为O（nlog n），插入排序为O（n\*n）,堆排序新建的空列表作用与插入排序新建的有序列表作用相同，但仅仅是作用相同。

优点：效率高，如果只是要找到最大数的话时间复杂度仅仅为O(1)

缺点：实现相对复杂

1 function heapSort(array) {
 2 var temp;
 3 var i;
 4 for (i = Math.floor(array.length / 2); i >= 0; i--) {
 5 heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆
 6 }
 7 for (i = array.length - 1; i >= 0; i--) {
 8 /*把根节点交换出去*/
 9 temp = array[i];
 10 array[i] = array[0];
 11 array[0] = temp;
 12 
 13 /*余下的数组继续构建成大顶堆*/
 14 heapAdjust(array, 0, i - 1);
 15 /* 输出结果 */
 16 document.write(" 第 + (array.length - i).toString() + "遍排序的结果是:")
 17 for (var n = 0; n < array.length; n++) {
 18 document.write(array[n] + ",");
 19 }
 20 /* 输出结果结束 */
 21 }
 22 }
 23 //要调整的子树
 24 //start为数组开始下标
 25 //max是数组结束下标
 26 function heapAdjust(array, start, max) {
 27 var temp, j;
 28 temp = array[start];//temp是根节点的值
 29 for (j = 2 * start; j < max; j *= 2) {
 30 if (j < max && array[j] < array[j + 1]) { //取得较大孩子的下标
 31 ++j;
 32 
 33 }
 34 if (temp >= array[j])
 35 break;
 36 array[start] = array[j];
 37 start = j;
 38 }
 39 array[start] = temp;
 40 
 41 }

\*该代码部分借鉴CareySon

转载于:https://www.cnblogs.com/s-z-y/p/4444465.html