常见排序算法

js

冒泡排序

算法描述：
1，比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2，对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3，针对所有的元素重复以上的步骤，除了最后一个。
4，持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

var array=[10,9,8,7,6,5,4,3,2,1];
//冒泡排序
function bubbleSort(a){
    var sign;
    for(var i=0;i<a.length;i++){
        sign = 0;
        for(var j=0;j<a.length;j++){
            if (a[j]>a[j+1]) {
                var tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
                sign = 1;
            };
        }
        if (sign == 0) {
            break;
        };
    }
    return a;
}
bubbleSort(array);

时间复杂度：
1，若数据初始状态为正序，扫描一趟就可完成排序，每趟排序要进行n-1次比较，所以冒泡排序最好的时间复杂度为O(n);
2,若数据初始状态为倒序，需要进行n-1趟排序。所以最坏的时间复杂度为O(n^2)

插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。

1，直接插入排序

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

值得注意的是，我们需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位。

//直接插入排序
function insertSort(array){
   for(var i=1;i<array.length;i++){
      if (array[i]<array[i-1]) {//从右往左比较
        var temp=array[i];
        for(var j=i-1;j>=0&&array[j]>temp;j--){
            array[j+1]=array[j];//往后移一位
        }
        array[j+1]=temp;
      };
   }
   return array;
}
insertSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]);

直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。

2，希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

//希尔排序
function shellSort(arr){
    var len=arr.length;
    for(var d=Math.floor(len/2);d>0;d=Math.floor(d/2)){//不断缩小增量d
        for(var i=d;i<len;i++){
            for(var j=i-d;j>=0&&arr[j]>arr[d+j];j-=d){
                var temp=arr[j];//交换
                arr[j]=arr[d+j];
                arr[d+j]=temp;
            }
        }
    }
    return arr;
}
shellSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]);

希尔排序动画演示

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法描述：设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

 //快速排序
function quickSort(arr){
    if (arr.length <= 1) { return arr; }
　　var midIndex = Math.floor(arr.length / 2);
　　var mid = arr.splice(midIndex, 1)[0];//取出中间数字，改变了原数组
　　var left = [];
　　var right = [];
    //选取中间的数mid作为基准,<mid 放入左边数组,>mid放入右边数组
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < mid) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([mid], quickSort(right));//递归
};
quickSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]);

快速排序的平均运行时间为O(nlogn)。

选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

1,简单选择排序

设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录下标，与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。

//简单选择排序
function simpleSelectionSort(arr){
    var min,tmp;
    for(var i=0;i<arr.length;i++){
        min=i;
        for(var j=i+1;j<arr.length;j++){//找到最小值
            if (arr[min]>arr[j]) {
                min=j;
            };
        }
        if (min!=i) {
            tmp=arr[i];
            arr[i]=arr[min];
            arr[min]=tmp;
        };
    }
    return arr;
}
simpleSelectionSort([3, 44, 38, 5, 47, 15, 36]);

2,堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

//堆排序
function heapSort(array){
    var temp;
    var i;
    for (i = Math.floor(array.length / 2); i >= 0; i--) {
        heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆
    }
    for(i=array.length-1;i>=0;i--){
        temp=array[i];//最后一个记录相互交换
        array[i]=array[0];
        array[0]=temp;
        heapAdjust(array, 0, i - 1);//重新调整为大顶堆
    }
    return array;
}
/*
  要调整的子树
  start为数组开始下标
  max是数组结束下标
*/
function heapAdjust(array, start, max) {
    var temp, j;
    temp = array[start];//temp是根节点的值
    for (j = 2 * start; j < max; j *= 2) {
        if (j < max && array[j] < array[j + 1]) {  //取得较大孩子结点的下标
            ++j;
        }
        if (temp >= array[j])
            break;
        array[start] = array[j];
        start = j;
    }
    array[start] = temp;
}
heapSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]);

时间复杂度O(n*logn)。

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

function　merge(left, right){
    var　result=[];
    while(left.length>0 && right.length>0){
        if(left[0]<right[0]){
        /*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    return　result.concat(left).concat(right);
}
function　mergeSort(arr){
    if(arr.length == 1){
        return　arr;
    }
    var　middle = Math.floor(arr.length/2),
         left = arr.slice(0, middle),
         right = arr.slice(middle);
    return　merge(mergeSort(left), mergeSort(right));
}
mergeSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]);

时间复杂度为O(nlogn)
排序算法动画演示