基于比较的排序（7种）
1.冒泡排序BubbleSort
** 1.1 基本思想 **
冒泡排序是最简单粗暴的排序方法之一。它的原理很简单，每次从左到右两两比较，把大的交换到后面，每次可以确保将前M个元素的最大值移动到最右边。
1.2时间复杂度
平均：O（N^2）
最好情况下：正序有序，则只需要比较n次。故，为O(n)
最坏情况下: 逆序有序，则需要比较(n-1)+(n-2)+……+1，故，为O(N^2)
1.3稳定性
排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以，它们的相对位置并没有改变，冒泡排序算法是稳定的！
1.4 源码实现
void bubble_sort(vector<int> &nums)
{
for (int i = 0; i < nums.size() - 1; i++) { // times
for (int j = 0; j < nums.size() - i - 1; j++) { // position,size-i之后的元素已经有序
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
2.选择排序 SelectionSort
2.1 基本思想
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。具体做法是：选择最小的元素与未排序部分的首部交换，使得序列的前面为有序。
2.2时间复杂度
最好情况下：交换0次，但是每次都要找到最小的元素，因此大约必须遍历(N ^ 2)次，因此为O(N ^ 2)。减少了交换次数！
最坏情况下，平均情况下：O(N^2)
2.3稳定性
由于每次都是选取未排序序列A中的最小元素x与A中的第一个元素交换，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不稳定
！
2.4 源码实现
void selection_sort(vector<int> &nums)
{
for (int i = 0; i < nums.size(); i++) { // position,记录下标，进行交换
int min = i;
for (int j = i + 1; j < nums.size(); j++) {
if (nums[j] < nums[min]) {
min = j;
}
}
int temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
3.插入排序 InsertionSort
3.1 基本思想
每次选择一个元素K插入到之前已排好序的部分A[1…i]中，插入过程中K依次由后向前与A[1…i]中的元素进行比较。如果A[x]<K,，将A[x]后移一位(或者将A[x]与K进行交换，当A[x]>=K，停止交换)。若发现发现A[x]>=K,则将K插入到A[x]的后面，插入前需要移动元素。
3.2时间复杂度
最好的情况下：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n)
最坏的情况下：逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n2)
平均情况下：O(n2)
3.3稳定性
在插入排序中，K1是已排序部分中的元素，当K2和K1比较时，直接插到K1的后面(没有必要插到K1的前面，这样做还需要移动！！)，因此，插入排序是稳定的。
3.4 源码实现
void insert_sort(vector<int> &nums)
{
for (int i = 1; i < nums.size(); i++) { // position
for (int j = i; j > 0; j--) {
if (nums[j] < nums[j - 1]) {//交换至临界值时停止交换
int temp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = temp;
}
}
}
}
4. 希尔排序 ShellSort
4.1 基本思想
希尔排序也是一种插入排序方法,实际上是一种分组插入方法。先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量d2(＜d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
例如：将 n 个记录分成 d 个子序列：
{ R[0]， R[d]， R[2d]，…， R[kd] }
{ R[1]， R[1+d]， R[1+2d]，…，R[1+kd] }
…
{ R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1] }
说明：d=5 时，先从A[d]开始向前插入，判断A[d-d]，然后A[d+1]与A[(d+1)-d]比较，如此类推，这一回合后将原序列分为d个组。<由后向前>
4.2时间复杂度
最好情况：由于希尔排序的好坏和步长d的选择有很多关系。目前还没有得出最好的步长如何选择所以，不知道最好的情况下的算法时间复杂度。
最坏情况下：O(NlogN)，最坏的情况下和平均情况下差不多。
平均情况下：O(NlogN)
4.3稳定性
由于多次插入排序，一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。(一般来说，若存在不相邻元素间交换，则很可能是不稳定的排序。)
4.4 源码实现
void shell_sort(vector<int> &nums)
{
for (int gap = nums.size() >> 1; gap > 0; gap >>= 1) { // times
for (int i = gap; i < nums.size(); i++) { // position
int temp = nums[i];
int j = i - gap;
for (; j >= 0 && nums[j] > temp; j -= gap) {
nums[j + gap] = nums[j];
}
nums[j + gap] = temp;
}
}
}
5.归并排序 MergeSort
5.1 基本思想
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序，再合并数组。
合并两个有序数组，基本思路是先分别赋值给两个子数组，再比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
5.2时间复杂度
最好的情况下：一趟归并需要n次，总共需要logN次，因此为O(NlogN)
最坏的情况下，接近于平均情况下，为O(NlogN)
说明：对长度为n的文件，需进行logN 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
5.3稳定性
归并排序最大的特色就是它是一种稳定的排序算法。归并过程中是不会改变元素的相对位置的。
5.4 源码实现
void merge(int *data, int p, int q, int r) //合并，先分开赋值为两个数组，再进行合并
{
int n1, n2, i, j, k;
int *left=NULL, *right=NULL;
n1 = q-p+1;
n2 = r-q;
left = (int *)malloc(sizeof(int)*(n1));
right = (int *)malloc(sizeof(int)*(n2));
for(i=0; i<n1; i++) //对左数组赋值
left[i] = data[p+i];
for(j=0; j<n2; j++) //对右数组赋值
right[j] = data[q+1+j];
i = j = 0;
k = p;
while(i<n1 && j<n2) //将数组元素值两两比较，并合并到data数组
{
if(left[i] <= right[j])
data[k++] = left[i++];
else
data[k++] = right[j++];
}
for(; i<n1; i++) //如果左数组有元素剩余，则将剩余元素合并到data数组
data[k++] = left[i];
for(; j<n2; j++) //如果右数组有元素剩余，则将剩余元素合并到data数组
data[k++] = right[j];
}
void mergeSort(int *data, int p, int r)
{
int q;
if(p < r) //只有一个或无记录时不须排序
{
q = (int)((p+r)/2); //将data数组分成两半
mergeSort(data, p, q); //递归拆分左数组
mergeSort(data, q+1, r); //递归拆分右数组
merge(data, p, q, r); //合并数组
}
}
6.快速排序 QuickSort
6.1 基本思想
关于快排，我的另一篇文章提到了思想以及源码
：https://www.jianshu.com/p/d4435162640c
6.2时间复杂度
最好的情况下：因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)，故为 O(NlogN)
最坏的情况下：基本有序时，退化为冒泡排序，几乎要比较N ^ 2次，故为O(N^2)
6.3稳定性
由于每次都需要和中轴元素交换，因此原来的顺序就可能被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以说，快速排序是不稳定的！
7.堆排序
7.1 基本思想
利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或者最小)的记录。也就是说，以最小堆为例，根节点为最小元素，较大的节点偏向于分布在堆底附近。
7.2时间复杂度
最坏情况下，接近于最差情况下：O(NlogN)，因此它是一种效果不错的排序算法。
7.3稳定性
堆排序需要不断地调整堆，因此它是一种不稳定的排序！
7.4 源码实现
void max_heapify(vector<int> &nums, int beg, int end)//调整为最大堆
{
int curr = beg;
int child = curr * 2 + 1;
while (child < end) {
if (child + 1 < end && nums[child] < nums[child + 1]) {
child++;
}
if (nums[curr] < nums[child]) {
int temp = nums[curr];
nums[curr] = nums[child];
nums[child] = temp;
curr = child;
child = 2 * curr + 1;
} else {
break;
}
}
}
void heap_sort(vector<int> &nums)
{
int n = nums.size();
for (int i = n / 2 - 1; i >= 0; i--) { // build max heap
max_heapify(nums, i, nums.size());
}
for (int i = n - 1; i > 0; i--) { // heap sort
int temp = nums[i];
nums[i] = nums[0];
nums[0] = temp;
max_heapify(nums, 0, i);//建立下一次的最大堆
}
}
基于非比较的排序
8.计数排序
8.1 基本思想
假设我们有一个待排序的整数序列A，其中元素的最小值不小于0，最大值不超过K。建立一个长度为K的线性表C，用来记录不大于每个值的元素的个数。
- 扫描序列A，以A中的每个元素的值为索引，把出现的个数填入C中。此时C[i]可以表示A中值为i的元素的个数。
- 对于C从头开始累加,使C[i]就表示A中值不大于i的元素的个数。
3.按照统计出的值，输出结果。
8.2时间复杂度
计数排序的时间复杂度为O(N+K)，空间复杂度为O(N+K)。
8.3稳定性
它是一种稳定排序算法，即排序后的相同值的元素原有的相对位置不会发生改变(表现在Order（见8.5源码）上)，这是计数排序很重要的一个性质，就是根据这个性质，我们才能把它应用到基数排序。
8.4 适用情况
当K不是很大时，这是一个很有效的线性排序算法。
8.5 代码（一般不要求）
由线性表C我们可以很方便地求出排序后的数据，定义B为目标的序列，Order[i]为排名第i的元素在A中的位置
void CountingSort(int *A,int *B,int *Order,int N,int K)
{
int *C=new int[K+1];
int i;
memset(C,0,sizeof(int)*(K+1));
for (i=1;i<=N;i++) //把A中的每个元素分配
C[A[i]]++;
for (i=2;i<=K;i++) //统计不大于i的元素的个数
C[i]+=C[i-1];
for (i=N;i>=1;i--)
{
B[C[A[i]]]=A[i]; //按照统计的位置，将值输出到B中，将顺序输出到Order中
Order[C[A[i]]]=i;
C[A[i]]--;
}
}
9.桶排序
9.1 基本思想
桶为一个数据容器，每个桶存储一个区间内的数。依然有一个待排序的整数序列A，元素的最小值不小于0，最大值不超过K。假设我们有M个桶，第i个桶Bucket[i]存储iK/M至(i+1)K/M之间的数，有如下桶排序的一般方法：
- 扫描序列A，根据每个元素的值所属的区间，放入指定的桶中(顺序放置)。
- 对每个桶中的元素进行排序，什么排序算法都可以，例如快速排序。
- 依次收集每个桶中的元素，顺序放置到输出序列中。
9.2 时间复杂度
与桶内排序的算法相关。
9.3 稳定性
桶中元素的顺序放入和顺序取出是有必要的，因为这样可以确定桶排序是一种稳定排序算法
9.4 代码（一般不要求）
struct linklist
{
linklist *next;
int value;
linklist(int v,linklist *n):value(v),next(n){}
~linklist() {if (next) delete next;}
};
inline int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
/*
为了方便，我把A中元素加入桶中时是倒序放入的，而收集取出时也是倒序放入序列的，所以不违背稳定排序。
*/
void BucketSort(int *A,int *B,int N,int K)
{
linklist *Bucket[101],*p;//建立桶
int i,j,k,M;
M=K/100;
memset(Bucket,0,sizeof(Bucket));
for (i=1;i<=N;i++)
{
k=A[i]/M; //把A中的每个元素按照的范围值放入对应桶中
Bucket[k]=new linklist(A[i],Bucket[k]);
}
for (k=j=0;k<=100;k++)
{
i=j;
for (p=Bucket[k];p;p=p->next)
B[++j]=p->value; //把桶中每个元素取出，排序并加入B
delete Bucket[k];
qsort(B+i+1,j-i,sizeof(B[0]),cmp);
}
}
10.基数排序
10.1 基本思想
它是一种非比较排序。它是根据位的高低进行排序的，也就是先按个位排序，然后依据十位排序……以此类推。
10.2时间复杂度
分配需要O(n),收集为O(r),其中r为分配后链表的个数，以r=10为例，则有0～9这样10个链表来将原来的序列分类。而d，也就是位数(如最大的数是1234，位数是4，则d=4)，即"分配-收集"的趟数。因此时间复杂度为O(d(n+r))。
10.3稳定性
基数排序过程中不改变元素的相对位置，因此是稳定的！
10.4 适用情况
如果有一个序列，知道数的范围(比如1～1000)，用快速排序或者堆排序，需要O(NlogN)，但是如果采用基数排序，则可以达到O(4(n+10))=O(n)的时间复杂度。算是这种情况下排序最快的！！
10.5 代码（一般不要求）
radixSort(a, n)的作用是对数组a进行排序。
1. 首先获取最大值,目的是计算出数组a的最大指数。获取到数组a中的最大指数之后，再从指数1开始，根据位数对数组a中的元素进行排序。排序的时候采用了计数排序。
2.countSort(vec, exp)的作用是对数组a按照指数exp进行排序。
下面简单介绍一下对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}按个位数进行排序的流程来理解countSort(vec, exp)函数。
a、个位的数值范围是[0,10)。因此，参见数组ranges，range[i]代表i之前的数据出现次数，也即当前数本应该在的位置。
b、 接着是根据数组range来进行排序。假设将排序后的数组存在tmpVec中；找出tmpVec和range之间的联系就可以对数据进行排序了
void countSort(vector<int>& vec,int exp)
{//计数排序
vector<int> range(10,0);
int length=vec.size();
vector<int> tmpVec(length,0);
for(int i=0;i<length;++i)
{
range[(vec[i]/exp)%10]++;
}
for(int i=1;i<range.size();++i)
{
range[i]+=range[i-1];//统计本应该出现的位置
}
for(int i=length-1;i>=0;--i)
{
tmpVec[range[(vec[i]/exp)%10]-1]=vec[i];
range[(vec[i]/exp)%10]--;
}
vec=tmpVec;
}
void radixSort(vector<int>& vec)
{
int length=vec.size();
int max=-1;
for(int i=0;i<length;++i)
{//提取出最大值
if(vec[i]>max)
max=vec[i];
}
//提取每一位并进行比较，位数不足的高位补0
for(int exp=1;max/exp>0;exp*=10)
countSort(vec,exp);
}
