#### 排序算法
一、插入排序
（1）算法思维（以升序举例）：
对于一个曾经有序的序列，又来一个数 x，从倒数第一个数进行比拟，如果 x 比这个数小，这个数就往后挪。
（2）代码实现
//O(N)最好程序 -O(N*N)最坏逆序
void insert_sort(int*a, int n)
{for (int i = 0; i < n-1; ++i)
{
int end = i;
int x = a[i+1];
while (end >= 0)
{if (a[end] > x)
{a[end+1] = a[end];
--end;
}
else
{break;}
}
a[end + 1] = x;
}
}（3）改良：希尔排序
思维：插入排序在整体有序的状况下成果最好，于是希尔排序先预排序让序列先大体有序，最初进行插入排序来获得最好的成果。它的工夫复杂度大略为 O(N^1.3)。
步骤：把数字分成 gap 个一组 -> 对每组数据进行插入排序来达到大体有序的目标 -> 对整体插入排序
//gap 越小，越靠近有序。pow(n,1.3)
void shell_sort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap/3 + 1;//gap>1 都是预排序，gap== 1 为间接插入排序
for (int i = 0; i < gap; ++i)
{for (int j = i; j < n - gap; j += gap)
{
int end = j;
int x = a[end + gap];
while (end >= 0)
{if (a[end] > x)
{a[end + gap] = a[end];
end -= gap;
}
else
{break;}
}
a[end + gap] = x;
}
}
}
}二、抉择排序
思维：在序列中每次都找到最小值和最大值，把它们放在应该的地位。
//O(N*N)
void select_sort(int* a, int n)
{//assert(a);
int begin = 0, end = n - 1;
while (begin < end)
{
int min_ = begin, max_ = end;
for (int i = begin; i <= end; ++i)
{if (a[i] < a[min_])min_ = i;
if (a[i] > a[max_])max_ = i;
}
swap(&a[begin], &a[min_]);
if (max_ == begin)
{max_ = min_;}
swap(&a[end], &a[max_]);
++begin;
--end;
}
}三、堆排序
思维：应用堆的 down 操作来找到大堆中的最大值，把它替换到尾部，再对 a[0]进行一个 down。
//nlogn
void heap_sort(int* a, int n)
{for (int i = (n - 2) / 2; i >= 0; --i)
{heap_down(a, n, i);
}
int end = n - 1;
while (end > 0)
{swap(&a[0], &a[end]);
heap_down(a, end, 0);
--end;
}
}四、冒泡排序
思维：每次循环都确定一个最大值，先是最大的，放到尾部，其次是第二大的，直到没有产生替换，阐明排序曾经实现。
//O(n*n) 最好:n, 遍历一次就晓得后果
void bubble_sort(int* a, int n)
{for (int i = 0; i < n; ++i)
{
int f = 0;
for (int j = 0; j < n-i-1; ++j)
{if (a[j] > a[j+1])
{
f = 1;
swap(&a[j], &a[j+1]);
}
}
if (f == 0)
{break;}
}
}五、疾速排序
(1)思维：每次排序找一个 key，通过排序使得序列的右边数据都 <=key，左边数据都 >=key，递归解决。
void quick_sort(int* a, int begin, int end)
{if (begin >= end)
return;
int keyi = quick1_sort(a, begin, end);
quick1_sort(a + begin, begin, keyi - 1);
quick1_sort(a + begin, keyi + 1, end);
}
// 传统写法：抉择一个 key，左边先走，右边再走，替换，直到 l ==r
int quick1_sort(int* a, int begin, int end)
{
int l = begin;
int r = end;
int keyi = a[l];
while (l < r)
{
// 左边先走
while (l < r && a[r] >= a[keyi])
{r--;}
// 当初的 a[r]<key
while (l < r && a[l] <= a[keyi])
{l++;}
swap(&a[l], &a[r]);
}
swap(&a[keyi], &a[l]);
keyi = l;
return keyi;
}
// 挖坑法
int quick2_sort(int* a, int begin, int end)
{
int l = begin;
int r = end;
int key = a[begin];
int pit = begin;
while (l < r)
{
// 左边先走
while (l < r && a[r] >= key)
{r--;}
a[pit] = a[r];
pit = r;// 这是新的坑
while (l < r && a[l] <= key)
{l++;}
a[pit] = a[l];
pit = l;// 这是新的坑
}
a[pit] = key;
return pit;
}
// 前后指针法
int quick3_sort(int*a, int begin, int end)
{
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{if (a[cur] < a[keyi])
{
++prev;
if(prev != cur)
swap(&a[prev], &a[cur]);
}
cur++;
}
swap(&a[prev], &a[keyi]);
return prev;
}在传统写法中，右边作 key，为什么让左边先走？
为了保障找到的相遇的地位肯定是 <=key，r 停的地位肯定 <= key;
r 始终往左边走，直到遇到 l，阐明这个地位左边的值都比 Key 大，相遇的地位是 l 上一轮停下来的，这里要么是 key（第一轮），要么比 key 小（不是第一轮了，上一轮 r 换过去的），工夫复杂度为 nlogn。
(2)优化
思维 1：当 key 每次都是最大或者最小时复杂度最高，抉择一个值在两头的数能力有好的后果。
// 优化 1 =key 每次都是最小或者最大成果最差：有序或者靠近有序 ->1. 随机选 Key 2. 三数选中
int get_key(int* a, int begin, int end)// 失去下标
{int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{if (a[mid] < a[end])return mid;
else if (a[begin] < a[end])return end;
else return begin;
}
else
{if (a[end] > a[begin])return begin;
else if (a[mid] < a[end])return end;
else return mid;
}
}思维 2：当递归区间比拟小的时候，不再递归解决，而是用其余算法对小区间排序，这样能够大大减少递归的次数（80%）
void quick_sort(int* a, int begin, int end)
{if (begin >= end)return;
if (end - begin > 10)//80%
{int keyi = quick1_sort(a, begin, end);
quick1_sort(a + begin, begin, keyi - 1);
quick1_sort(a + begin, keyi + 1, end);
}
else
{insert_sort(a,end -begin+1);
}
}(3)快拍的非递归写法
递归转非递归的办法：1. 间接改循环。2. 应用栈来模仿（这样不必放心栈溢出，因为堆的空间比拟大）
void quick_sort_nor(int* a, int begin, int end)
{
stack<int>st;
st.push(end);
st.push(begin);
while ()
{int l = st.top();
st.pop();
int r = st.top();
st.pop();
//(l,key-i-1)(keyi+1,r)
int keyi = quick1_sort(a, l, r);
if (r > keyi + 1)
{st.push(r);
st.push(keyi + 1);
}
if (l < keyi - 1)
{st.push(keyi - 1);
st.push(l);
}
}
}六、归并排序
（1）思维：先把序列递归分成小区间，再把小区间排成有序，接着把曾经有序的小区间进一步变成有序的区间。
void merge_sort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{exit(-1);
}
_merge_sort(a, 0, n - 1, temp);
free(temp);
}
void _merge_sort(int* a, int begin, int end, int* temp)
{if (begin >= end)return;
int mid = (begin + end) / 2;
_merge_sort(a, begin, mid, temp);
_merge_sort(a, mid+1, end, temp);
// 归并，使小区间有序
int begin1 = begin, end1 = mid,
begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{if (a[begin1] < a[begin2])
{temp[i++] = a[begin1++];
}
else
{temp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{temp[i++] = a[begin2++];
}
memcpy(a + begin, temp + begin,(end - begin + 1)*sizeof(int));
}(2)非递归写法
思维：把数组分成 1 个一组，2 个一组 …… 对每两个小组进行归并合成一个大的组。要留神边界问题。
对 [i, i+gap-1] 和[i+gap, i+2gap-1]归并；[i+2gap, i+3gap-1]和 [i+3gap, i+4gap-1] 归并 ……
void merge_sort_nor(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{exit(-1);
}
int gap = 1;
while (gap<n)
{
//i i+gap-1;i+gap i+2*gap-1;
int j = 0;
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1,
begin2 = i + gap, end2 = i + 2 * gap - 1;
// 修改边界
if (end1 >= n)
{
end1 = n - 1;
// 修改成不存在的区间
begin2 = n;
end2 = n - 1;
}
else if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
else if (end2 >= n)
{end2 = n - 1;}
j = i;
while (begin1 <= end1 && begin2 <= end2)
{if (a[begin1] <= a[begin2])// 加个 =，使他能够稳固
{temp[j++] = a[begin1++];
}
else
{temp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{temp[j++] = a[begin1++];
}
while (begin2 <= end2)
{temp[j++] = a[begin2++];
}
}
memcpy(a, temp, 2*gap* sizeof(int));
gap *= 2;
}
free(temp);
}七、相干概念
1. 稳定性：绝对程序不变。eg: 1 2 3 3 4 2，在排序之后，2 的绝对程序不变，5 的绝对程序不变。
2. 内排序：在内存上进行的排序
外排序：在磁盘上进行的排序
eg. 有 10 亿个 int 整数，须要 4G 的空间，对这些数字排序。思维：为了进步速度，先把这些数字分成四份，把每一份放在内存外面归并排序再写入文件，之后对这些文件进行归并排序。（fprintf/fscanf)。
八、各个内排序算法比拟