前端六大排序算法

jiezi

5 年前

阮一峰排序算法

一次比较两个元素，如果他们的顺序错误就把他们交换过来。这个算法的名字由来是因为越来越小的元素会经由交换慢慢“浮”到数列的顶端。
描述：

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

代码实现：

function bubbleSort(arr) {

   var len = arr.length;
   for(var i = 0; i < len - 1; i ++) {for(var j = 0; j < len - 1; j ++) {if(arr[j] > arr[j + 1]) {var temp = arr[j + 1];
               arr[j+1] = arr[j];
               arr[j] = temp;
           }
       }
   }
   return arr;

}

function bubbleSort(arr) {

   var len = arr.length;
   var i;
   var j;
   var stop;
   for(i = 0; i < len - 1; i ++) {for(j = 0, stop = len - 1 - i; j < stop; j ++) {if(arr[j] > arr[j + 1]) {swap(arr, j, j+1);
           }
       }
   }
   return arr;

}
function swap(arr, p1, p2) {

   arr[p1] = arr[p1] + arr[p2];
   arr[p2] = arr[p1] - arr[p2];
   arr[p1] = arr[p1] - arr[p2];

}

时间复杂度：O(n^2)（平均），O(N)（最好），O(n^2)（最坏），
空间复杂度：O(1)
稳定性：稳定

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩下未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述：

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

代码实现：

function seletionSort(arr) {

   var len = arr.length;
   var minIndex, temp;
   for(var i = 0; i < len - 1; i ++) {
       minIndex = i;
       for(var j = i + 1; j < len; j ++) {if(arr[j] < arr[minIndex]) {minIndex = j;}
       }
       temp = arr[i];
       arr[i] = arr[minIndex];
       arr[minIndex] = temp;
   }

}

算法分析：

表现最稳定的排序算法，因为无论什么数据进去都是 O(n^2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占额外的内存空间了吧。
稳定性：不稳定

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述：

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

代码实现：

function insertionSort(arr) {

   var len = arr.length;
   var preIndex, current;
   for(var i = 1; i < len; i ++) {
       preIndex = i - 1;
       current = arr[i];
       while(preIndex >= 0 && arr[preIndex] > current) {arr[preIndex + 1] = arr[preIndex];
           preIndex --;
       }
       arr[preIndex + 1] = current;
   }
   return arr;

}

时间复杂度：O(n^2)（平均），O(n^2)（最坏），O(n)（最好）

简单插入排序的改进版。与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述：

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

代码实现：

function sort(arr) {

   for(int gap = arr.length / 2; gap > 0; gap /= 2) {for(int i = gap; i < arr.length; i++) {
           int j = i;
           while(j - gap >= 0 && arr[j] < arr[j - gap]) {swap(arr, j, j - gap);
               j -= gap;
           }
       }
   }

}
function swap(arr, a, b) {

   arr[a] = arr[a] + arr[b];
   arr[b] = arr[a] - arr[b];
   arr[a] = arr[a] - arr[b];

}

时间复杂度：O(n^1.3)（平均）、O(n^2)（最坏）、O(n)（最好）

归并排序是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，成为 2 - 路归并。

算法描述：

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

代码实现：

function mergeSort(arr) {

   var len = arr.length;
   if(len < 2) {return arr;}
   var middle = Math.floor(len / 2),
   left = arr.slice(0, middle),
   right = arr.slice(middle);
   return merge(mergeSort(left), mergeSort(right));

}

function merge(left, right) {

   var result = [];
   while(left.length>0 && right.length>0) {if(left[0] <= right[0]) {result.push(left.shift());
       }
       else {result.push(right.shift());
       }
   }
   while(left.length) {result.push(left.shift());
   }
   while(right.length) {result.push(right.shift());
   }
   return result;

}

时间复杂度：O(nlog2n)（平均）、O(nlog2n)（最坏）、O(nlog2n)（最好）

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

算法描述：

从数列中挑出一个元素，称为“基准”
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作
递归地把小于基准值元素的子数列和大于基准值元素的子序列排序

代码实现一：

function quickSort(arr) {

   if(arr.length <= 1) {return arr;}
   var pivotIndex = Math.floor(arr.length / 2);
   var pivot = arr.splice(pivotIndex, 1)[0];
   var left = [], right = [];
   for(var i = 0; i < arr.length; i ++) {if(arr[i] < pivot) {left.push(arr[i]);
       } else {right.push(arr[i]);
       }
   }
   return quickSort(left).concat([pivot],quickSort(right));

}

代码实现二：

function swap(arr, a1, a2) {

   var temp = arr[a1];
   arr[a1] = arr[a2];
   arr[a2] = temp;

}
function partition(arr, left, right) {

   var pivot = arr[Math.floor((right + left) / 2)],
   i = left,
   j = right;
   while(i <= j) {while(arr[i] < pivot) {i ++;}
       while(arr[j] > pivot) {j --;}
       if(i <= j) {swap(arr, i ,j);
           i ++;
           j --;
       }
   }
   return i;

}
function quickSort(arr, left, right) {

   if(arr.length < 2) {return arr;}
   left = (tyepof left !== "number" ? 0 : left);
   right = (typeof right !== 'number' ? arr.length - 1 : right);
   var index = partition(arr, left, right);
   if(left <index - 1) {quickSort(arr, left, index - 1);
   }
   if(index <right) {quickSort(arr, index, right);
   }
   return arr;

}

前端六大排序算法

1. 冒泡排序

2. 选择排序

3. 插入排序

4. 希尔排序

5. 归并排序

6. 快速排序