排序，作为算法入门第一关，为多少计算机学生的算法之路打开了大门，念旧怀友，特撰此文，隆重介绍那些帮助我风雨来雨里去的“排序”小友们
快排显然不是最简单的，但是基本是学会之后用的最多的。曾几何时，默写一段快排是一个计算机人最起码的标识。
快排原理简单，取出一个值，比如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(n2 ),代码实现
//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(n2 )，代码实现
//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(n2 )，代码实现
//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排序算法