那些排序们

排序，作为算法入门第一关，为多少计算机学生的算法之路打开了大门，念旧怀友，特撰此文，隆重介绍那些帮助我风雨来雨里去的“排序”小友们

快排

快排显然不是最简单的，但是基本是学会之后用的最多的。曾几何时，默写一段快排是一个计算机人最起码的标识。
快排原理简单，取出一个值，比如a[0]，前后扫描，将比他小的都放到他前面，比他大的都放到他后面，然后把它放中间。然后再对前面和后边进行递归
时间复杂度：O(nlogn)，代码实现

//quick sort
void qsort(int* a,int x,int y){
    int xx = x, yy = y;
    int k = a[x];
    if(xx >= yy)
        return;
    while(xx != yy){
        while(xx < yy && a[yy] >= k)
            yy--;
        a[xx] = a[yy];
        while(xx < yy && a[xx] <= k)
            xx++;
        a[yy] = a[xx];
    }
    a[xx] = k;
    qsort(a,x,xx-1);
    qsort(a,xx+1,y);

}

选择排序

对选择排序最恰当的比喻：班上的MM搞选美活动，有人叫我给所有MM排个名。我们通常会用选择排序，即先找出自己认为最漂亮的，然后找第二漂亮的，然后找第三漂亮的，不断找剩下的人中最满意的，最后完成排序
时间复杂度O(n² ),代码实现

//selection sort
void ssort(int* a,int x,int y){
    int min = x;
    if(x >= y)
        return;
    for(int i=x;i<=y;i++){
        if(a[i]<a[min])
            min = i;
    }
    int tmp = a[x];
    a[x] = a[min];
    a[min] = tmp;
    ssort(a,x+1,y);
}

冒泡排序

大名鼎鼎的冒泡排序，在大家都不会快排的时候，老师只能用冒泡排序证明大家还是学过计算机的
体育课上从矮到高排队时，站队完毕后总会有人出来，比较挨着的两个人的身高，指挥到：你们俩调换一下，你们俩换一下。这就是冒泡排序。

时间复杂度O(n² )，代码实现

//bubble sort
void bsort(int* a,int x,int y){
    if(x >= y)
        return;
    int bubble = 0,tmp;
    for(int i=x;i<y;i++){
        if(a[i]>a[i+1]){
            bubble = 1;
            tmp = a[i];
            a[i] = a[i+1];
            a[i+1] = tmp;
        }
    }
    if(bubble == 0)
        return;
    else
        bsort(a,x,y-1);
}

插入排序

打扑克牌时我们希望抓完牌后手上的牌是有序的，三个8挨在一起，后面紧接着两个9。这时，我们会使用插入排序，每次拿到一张牌后把它插入到手上的牌中适当的位置。

时间复杂度O(n² )，代码实现

//insertion Sort
void isort(int* a,int x,int y){
    if(x >= y)
        return;
    int tmp = a[x];
    for(int i=0;i<x;i++){
        if(a[i]>a[x]){
            for(int j=x;j>i;j--)
                a[j] = a[j-1];
            a[i] = tmp;
            break;
        }
    }
    isort(a,x+1,y);
}

归并排序

假设我们有两个已排好序的数组，将其合并成一个已排好序的数组，显然只要在两个数组的头部都设一个指针，谁的小就将值取出放入新的数组，然后指针后移。这样的时间复杂度是O(n)的。不断的把当前数组分成两个数组，知道每个数组中只有一个元素，然后再把这些数组不断合并成原数组，这个数组就是排好序的了，这个方法称之为归并排序

时间复杂度O(nlogn),代码实现

//merge sort
void msort(int* a,int x,int y){
    if(x >= y)
        return;

    int mid = (int)((x+y)/2);
    msort(a,x,mid);
    msort(a,mid+1,y);

    int n1 = mid-x+1;
    int n2 = y-mid;
    int* left = (int *)malloc(sizeof(int)*n1);
    int* right = (int *)malloc(sizeof(int)*n2);
    for(int i=0; i<n1; i++)
        left[i] = a[x+i];
    for(int j=0; j<n2; j++)
        right[j] = a[mid+1+j];

    for(int i=0,j=0,k=x;k<=y;k++){
        if(i<n1 && j<n2){
            if(left[i] <= right[j]){
                a[k] = left[i];
                i++;
            }
            else{
                a[k] = right[j];
                j++;
            }
        }
        else if(i<n1){
            a[k] = left[i];
            i++;
        }
        else{
            a[k] = right[j];
            j++;
        }
    }
    return;
}

桶排序

如果我们愿意付出一定空间，那么我们可不可以更快的排序呢？答案是肯定的，桶排序相当于遍历一遍数组，将每一个a[i]放入其对应的桶中（以期大小决定，相当于做了一个hash散列），然后，我们要做的就是按照桶的先后，把他们取出来就好了

时间复杂度O(n+k),伪代码实现(需要定义一个hash链表结构)

void BucketSort(int* a,int x,int y){
 vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
 for(int i=x;i<=y;++i){
  int index = a[i]/BUCKET_NUM;
  ListNode *head = buckets.at(index);
  buckets.at(index) = insert(head,a[i]);
 }
 ListNode *head = buckets.at(0);
 for(int i=1;i<BUCKET_NUM;++i){
  head = Merge(head,buckets.at(i));
 }
 for(int i=x;i<=y;++i){
  a[i] = head->mData;
  head = head->mNext;
 }
}

堆排序

利用大顶堆或小顶堆的结构，将数组先生成一个大顶堆，然后再将这个大顶堆变成一个数组的过程

时间复杂度O(nlogn),代码实现

void sift(int d[], int ind, int len)
{
     //#置i为要筛选的节点#%
     int i = ind;

     //#c中保存i节点的左孩子#%
     int c = i * 2 + 1; //#+1的目的就是为了解决节点从0开始而他的左孩子一直为0的问题#%

     while(c < len){ 
     //#如果要筛选的节点既有左孩子又有右孩子并且左孩子值小于右孩子#%
     //#从二者中选出较大的并记录#%
     if(c + 1 < len && d[c] < d[c + 1])
         c++;
     //#如果要筛选的节点中的值大于左右孩子的较大者则退出#%
     if(d[i] > d[c]) break;
     else
{ 
     //#交换#%
         int t = d[c];
         d[c] = d[i];
         d[i] = t;

     //#重置要筛选的节点和要筛选的左孩子#%
     i = c;
     c = 2 * i + 1;
     }
     }
return;
}

void heap_sort(int* a, int x, int y)
{
    int n = y - x + 1;
    for(int i = (n - 2) / 2; i >= 0; i--)
    sift(a, i, n);

    for(int j = 0; j < n; j++){
        int t = a[0];
        a[0] = a[n - j - 1];
        a[n - j - 1] = t;
        sift(a, 0, n - j - 1);
 }
}

基数排序

此小哥我还不认识，等我认识之后，回来补上介绍

参考

[1] 从零开始学算法：十种排序算法介绍 本文那几个恰当的比喻出自此处
[2] wiki排序算法