排序算法 | 大洋

1.插入排序-直接插入排序
2.插入排序—希尔排序（Shell`s Sort）
3.选择排序—简单选择排序（Simple Selection
4.交换排序—冒泡排序（Bubble Sort）
5.交换排序—快速排序（Quick Sort）

平常在项目中可能都会用到排序，就我本人而言，可能大部分都是用的选择排序或者冒泡排序，简单粗暴，但是这往往都只是实现了功能，而没有去关注性能，所以还是有必要了解常用的排序方法(使用内存)。

插入排序-直接插入排序

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：

设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

原理演示：

点击查看

算法实现：


function insertSortArray(sort_Array,x){         //一趟排序的算法
for(var i=0;i<sort_Array.length;i++){
   if(sort_array[i]>=x){                    //找到插入点
    for (var j=sort_array.length; j>i; j--){   //后挪空出位置
     sort_array[j]=sort_array[j-1]
    }
    sort_array[i]=x;                             //插入
    break;                                      //任务结束，退出循环
   }
}
return sort_array;                                      //返回处理后的数组
}

function SortArrayByInsert(array){                      //主排序算法
var returnValue=new Array(1);                        //定义成功排序后的返回值，初始大小为一位
returnValue[0]=array[0];                               //在结果后置入排序前的第一位
for (i=1; i<array.length; i++){
   returnValue=insertSortArray(returnValue,array[i]);     //调用一趟排序函数，从第二个元素开始，依次使用
}
return returnValue;
}

2.插入排序—希尔排序（Shell`s Sort）

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

原理演示：

点击查看

操作方法：

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

示例：

算法实现

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 …..1} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

function shellInsertSort(elements, di){
  //从增量的所在位置开始
  for(var i = di; i < elements.length; i++){
    //升序
    if(elements[i] < elements[i-di]){
      //取出增量位置的元素作为被插入元素（哨兵）
      var guard = elements[i];
      var j = i - di;
      elements[i] = elements[j];

      //向前，将增量的倍数的位置作为同一组比较及进行直接插入法
      while(j >= 0 && guard < elements[j]){
        elements[j+di] = elements[j];
        j -= di;
      }

      //插入
      elements[j + di] = guard;
    }
  }
}

function shellSort(elements){
  //增量为序列的一半
  var di = parseInt(elements.length / 2);
  while(di >= 1){
    shellInsertSort(elements, di);
    //每次减半，最后增量必须为1
    di = parseInt(di / 2);
  }
}

var elements = [10, 9, 8, 7, 6, 5];
console.log('before: ' + elements);
shellSort(elements);
console.log(' after: ' + elements);

效率：比直接插入法快。但不是一种稳定的排序算法，关键取决于增量的选择，初次通常选取序列长度的一半。

3.选择排序—简单选择排序（Simple Selection Sort）

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例

原理演示：

点击查看

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推…..

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

算法实现

function sorrt(ary) {
    length = ary.length;
    for (var i = 0; i < length; i++) {
        _min = ary[i]
        k = i
        for (var j = i + 1; j < length; j++) {
            if (_min > ary[j]) {
                _min = ary[j]
                k = j
            }
        }
        ary[k] = ary[i]
        ary[i] = _min
    }
    return ary;
}

简单选择排序的改进——二元选择排序

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。

4. 交换排序—冒泡排序（Bubble Sort）

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序的示例

原理演示：

点击查看

算法的实现：

void bubbleSort(int a[], int n){
  for(int i =0 ; i< n-1; ++i) {
    for(int j = 0; j < n-i-1; ++j) {
      if(a[j] > a[j+1])
      {
        int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
      }
    }
  }
}

冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。

5. 交换排序—快速排序（Quick Sort）

基本思想

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

原理演示：

点击查看

快速排序的示例：

（a）一趟排序的过程：

（b）排序的全过程

算法的实现：

递归实现：

void print(int a[], int n){
    for(int j= 0; j<n; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int a[], int low, int high)
{
    int privotKey = a[low];                             //基准元素
    while(low < high){                                   //从表的两端交替地向中间扫描
        while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
        swap(&a[low], &a[high]);
        while(low < high  && a[low] <= privotKey ) ++low;
        swap(&a[low], &a[high]);
    }
    print(a,10);
    return low;
}


void quickSort(int a[], int low, int high){
    if(low < high){
        int privotLoc = partition(a,  low,  high);  //将表一分为二
        quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序
        quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序
    }
}

int main(){
    int a[10] = {3,1,5,7,2,4,9,6,10,8};
    cout<<"初始值：";
    print(a,10);
    quickSort(a,0,9);
    cout<<"结果：";
    print(a,10);

}

分析：

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

快速排序的改进

在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；