排序
插入排序（最有价值）
类似于摸牌
InsertSort：O(N^2)；最好：O(N)
最坏情况：逆序有序
最好情况：O(N)顺序有序
比冒泡排序实际应用更高效
以下是单趟排序，实现多趟需要再嵌套一个for循环，控制end的初值由0到n-1
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}// 时间复杂度：O(N^2) 逆序
// 最好的情况：O(N) 顺序有序
void InsertSort(int* a, int n)
{// [0, end] end+1for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp > a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}冒泡排序：
BubbleSort：O(N^2)；最好：O(N)
最好情况：O(N)，包含标志位即可实现，表示第一次就没有发生交换，也就是说前一个总比后一个大，结束
先选出一个最大的，交换到最后一个位置。
第一个数进行n-1次交换，也就是小于n次交换，n-j（j=0）
第二个数进行n-2次交换，也就是小于n-1次交换，n-j（j=1）
第n个数进行n-n次交换，也就是小于n-（n-1）次交换，n-j（j=n-1）
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false)break;}//for (int i = 0; i < n-1; i++)//{// if (a[i] > a[i+1])// {// Swap(&a[i], &a[i+1]);// }//}
}希尔排序
类似于插入排序，但是存在gap的间隔
ShellSort：平均O(N^1.3)
以上是分组排序，可以替换成多组并排
gap随着n进行变化
越到后面的每一次都可能比设想小，不能完全按逆序去算，因为前面已经排过了
最后一轮，gap=1，同时已经非常接近有序了。累计挪动大约n次
void ShellSort(int* a, int n)
{int gap = n;// gap > 1时是预排序，目的让他接近有序// gap == 1是直接插入排序，目的是让他有序while (gap > 1){//gap = gap / 2;gap = gap / 3 + 1;//+1可以保证最后一次一定是1for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}/*for (int j = 0; j < gap; ++j){for (int i = j; i < n-gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}*/
}选择排序
Selectsort：O(N^2)；最好：O(N^2)
最小的和左边换，最大的和右边换
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}//循环结束后mini是更新出来的最小的数值//max是最大的Swap(&a[begin], &a[mini]);//如果最大的值和最小的值是两个互换的位置，begin大和end小//min（end）和begin互换后，此时begin是最小的值，但是max存的是begin位置为最大值if (maxi == begin){//为了检测上一个交换的原位置是不是最大值//如果是最大值，则找最大值的新位置，也就是minimaxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}堆排序：
HeapSort：O(N*logN)
void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假设左孩子小，如果假设错了，更新一下if (child + 1 < size && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}快速排序：
有序情况下，快排很吃亏。因为快排的key选的是第一个数，在有序情况下，导致划分出的两个子序列长度极度不均衡，一个子序列可能只包含一个元素（即key本身），而另一个子序列包含了几乎所有剩余元素。以下有优化算法解决这个问题
越接近二分，快排越快
思想：
选一个关键字key，一般都是第一个数。
一个L，找比key大的，一个R，找比key小的。找到了就交换一下。相等的在哪都行，不用LR交换，否则死循环
然后将比key小的放左边，比key大的放右边
L和R相遇之后，和key交换，划分大小两边的分界线
注意：
为什么相遇位置比key小？因为右边先走
相遇有两种情况：
R遇见L。说明R没有找到比key小的，直到遇到L
L遇见R。R先走，找到小的停下来了。同时L没有找到比key大的，都比key小，直到遇到R
如果L先走就保证不了，因为L找大，以找大为前提的话，相遇位置可能是比key大的
所以：左边做key，R先走。右边做key，L先走（三数选中就不会出现这种情况，不可能存在一边的是=数都比key大或者小）
while循环，在循环体内自增到不满足循环体的条件之后还会走完这个循环，就出现错误，所以要在循环体内部，也就是自增的这个循环加上控制条件
交换的时候不能和key交换，如果和key交换代表着数组和一个局部变量换位置了，并没有改变数组里的数字，所以要写成和a[keyi]交换
left不能从key+1开始，要从key开始比较，否则会出现以下情况：
这种写法坑很多的同时，在有序排列还会很不占优势：
QuickSort：O(N*logN)
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;if (end - begin + 1 <= 10){InsertSort(a + begin, end - begin + 1);}else{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}hoare版本单趟排序：O(N)
// hoare
int PartSort1(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}
优化算法：
三数取中值法选key：
int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;// begin end midi三个数选中位数，也就是不大不小的值if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else{//a[begin] > a[midi]if(a[midi] > a[end]){return midi;}else if(a[begin] > a[end]){return begin;}else{return end;}}
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int midi = GetMidi(a, begin, end);//这里还是选择了最左边的值作为key，选哪都可以//然后再选出中间大小的值当做下面算法里的keySwap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}与插入排序结合：
优化效果一般
当待排序区间长度小于等于 10 时，采用插入排序进行优化，此时快排就减少了很大一部分递归，保证了在数据很大的情况下，栈不会溢出
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;if (end - begin + 1 <= 10){InsertSort(a + begin, end - begin + 1);}else{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}挖坑法单趟排序：O(N)
方便写一点，不用管先走的问题
// 挖坑法
int PartSort2(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int key = a[begin];int hole = begin;while (begin < end){// 右边找小，填到左边的坑while (begin < end && a[end] >= key){--end;}a[hole] = a[end];hole = end;// 左边找大，填到右边的坑while (begin < end && a[begin] <= key){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = key;return hole;
}挖坑法和hoare版本的单趟排序结果可能不同
前后指针法：O(N)
1、cur遇到比key大的值，++cur
2、cur遇到比key小的值，++prev，交换prev和cur的值，++cur
3、cur出界后，交换prev和key的值
prev只有需要交换的时候才往前走，所以prev要么紧跟cur，要么和cur间隔比key大的值，等待下一次交换
int PartSort3(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;//本来是else内的，但是cur都需要++}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}非递归排序：
递归排序：
递归排序是指在排序算法的设计中，通过函数自身调用自身来解决问题的排序方法。以快速排序为例，它的基本思想是选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。然后对左右两部分分别递归地进行排序，直到子数组的长度为 1 或 0（即已经有序）
非递归排序：
非递归排序不依赖函数自身调用自身来实现排序，而是使用迭代的方式，通常借助数据结构如栈或队列来模拟递归的过程。以快速排序的非递归实现为例，可以使用一个栈来保存待排序的子数组的边界信息。开始时，将整个数组的边界信息（起始下标和结束下标）压入栈中，然后在循环中从栈中取出一个子数组的边界信息，进行划分操作，将划分后的左右子数组的边界信息再压入栈中，直到栈为空
QuickSortNonR：
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(&s);STPush(&s, end);STPush(&s, begin);while (!STEmpty(&s)){int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);int keyi = PartSort3(a, left, right);// [left, keyi-1] keyi [keyi+1, right]if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi + 1);}}STDestroy(&s);
}归并排序：
后续递归
借助一个tmp数组，比较好大小之后再拷贝回去，再释放tmp数组
MergeSort：O(N*log(N))
一共log(N)层，一层N个
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid][mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);// [begin, mid][mid+1, end]归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//把tmp数组拷贝回去memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//首先，递归的时候需要一个区间//其次，有malloc，要是递归自己，那每次还会生成一个空间//所以要借助一个子函数_MergeSort(a, 0, n - 1, tmp);free(tmp);
}测试排序的性能对比
