排序
1、直接插入排序
void insert_sort()
{
for (int i = 1; i < n; i ++ ) //第一个数字有序，从第二个数字开始循环往后排序
{
int t = q[i], j = i; //t为当前插入元素值，用j寻找需要插入的位置
while (j && q[j-1] > t) //如果j前存在数（j!=0）且该数比t大；
{
q[j] = q[j - 1]; //将j前面一个数向后移动
j -- ; //依次比较前面的数，直到找出数值t对应的位置j
}
q[j] = t; //赋值
}
}
a. 时间复杂度
(1) 最好情况：O(n) 初始为顺序排列
(2) 平均情况：O(n^2)
(3) 最坏情况：O(n^2)
b. 辅助空间复杂度
O(1)
C.稳定(因为只移动比需要排序的元素要大的元素，相等的是不移动的所以是稳定的
2、折半插入排序
void binary_search_insert_sort()
{
for (int i = 1; i < n; i ++ ){
if (q[i - 1 <= q[i]) continue;
int t = q[i];
int l = 0; r = n - 1;
while(l < r) //找到l = r的下标的点，该点的值刚好大于t，r-1下标对应的值刚好小于等于t
{
int mid = (l + r) / 2;
if (q[mid] > t) r = mid;
else l = mid + 1;
}
for (int j = n- 1; j >= r; j -- )
{
q[j + 1] = q[j]; //将r及其后的点全部向后移动
}
q[r] = t; //赋值
}
}
a. 时间复杂度
(1) 最好情况：O(n)
(2) 平均情况：O(n^2)
(3) 最坏情况：O(n^2)
b. 辅助空间复杂度
O(1)
c. 稳定
3、冒泡排序
每次将最小的数冒泡到前面。
void bubble_sort()
{
for (int i = 0; i < n -1; i ++ ) //循环n-1次使n-1个数在自己位置，最后一个自然在自己位置
{
bool has_swap = false; //标记该次循环是否发生交换
for (int j = n - 1; j > i; j -- ) //第i+ 1次循环确定了i个数，所以该次循环从最后一个开始到第i+1个数（下标为i）比较
{
if (q[j -1] > q[j])
{
swap(q[j - 1], q[j]);
has_swap = true; //发生交换
}
}
if (!has_swap) break; //该次循环没有发生交换，说明后续数值均有序，结束循环
}
}
a. 时间复杂度
(1). 最好情况：O(n) //初始就为有序序列
(2). 平均情况：O(n^2)
(3). 最坏情况：O(n^2) //初始序列为逆序序列
b. 空间复杂度
O(1)
c. 稳定 // 相等元素不交换位置
4、简单选择排序
每次选择一个最小的数与对应位置交换。
void select_sort()
{
for (int i = 0; i < n-1; i ++ ) //同上，先排好n-1个数，最后一个数自然有序
{
int k = i;
for (int j = k +1; j < n; j ++ ) //找到最小元素的下标为k;
{
if (q[j] < q[k])
k = j;
}
swap(q[i], q[k]); //交换q[i]和q[k]的元素
}
}
(1) 时间复杂度
a. 最好情况：O(n^2) //每次都要比较
b. 平均情况：O(n^2)
c. 最坏情况：O(n^2)
//简单选择排序每次循环都会遍历一遍当前数后面的序列找到最小值，然后交换，所以平均，最好，最坏的复杂度都是O(n²)
(2) 空间复杂度
O(1)
(3) 不稳定（会和后面比自己小的元素交换，造成不稳定，eg: 2 2 1 中2会和1交换）
5、希尔排序
void shell_sort()
{
for (int d = n / 3; d; d = d == 2 ? 1 : d / 3){ //第一层循环：逐步减少元素增量d,最后使其为1，逐步接近插入排序
for (int start = 0; start < d; start ++ ){ //第二层循环：枚举每一个分组的起点，即start为0 1 2...d-1,
for (int i = start + d; i < n; i += d){ //第三层循环，对每一个分组进行直接插入排序，但要注意分组中的下标增量为d
int t = q[i], j = i;
while(j > start && q[j - d] > t){
q[j] = q[j - 1];
j -= d;
}
q[j] = t;
}
}
}
}
(1) 时间复杂度
O(n^(3/2))
(2) 空间复杂度
O(1)
(3) 不稳定
6、快速排序
void quick_sort(int l, int r) //进行排序的区间
{
if (l <= r) return;
int i = l - 1, j = r + 1, x = q[(l + r) / 2]; //i=l-1,j=r+1,是为了保证do i++后为第一个数，do j--为最后一个数，否则就首位俩个数就会被跳过判断不了
while (i < j)
{
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
/不能用while do，如果q[i]=q[j]=x，用while do会死循环，交换之后i，j的值也不会变。
if (i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
a. 时间复杂度
(1). 最好情况：O(nlogn)
(2). 平均情况：O(nlogn)
(3). 最坏情况：O(n^2)
b. 空间复杂度
O(logn)
c. 不稳定
7、堆排序
堆的下标从1开始
void down(int u){
int t = u;
if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;
//找到u以及其子节点中最大值的下标为t
if (u != t){ //发生了交换，则继续递归处理发生交换的子树
swap (q[u], q[t]);
down(t);
}
}
void up(int u){
if (u <= 1) return;
if (q[u >> 1] < q[u]){
swap(q[u >>1], q[u]);
up(u >> 1);
}
}
void heap(){
sz = n;
for (int i = n >> 1; i; i --) down (i); //建大顶堆，从第n/2个元素向上看
for (int i = 0; i < n; i ++ ){
swap(q[i], q[sz]); //将最大值（q[1]）依次与最后的值交换，最后得到的q数组为从小到大的顺序
sz -- ;
down (1);
}
}
a.时间复杂度
(1)最好情况：O(nlogn)
(2)平均情况：O(nlogn)
(3)最坏情况：O(nlogn)
b.空间复杂度
O(logn)
c.不稳定
8、归并排序(数学归纳法)
void merge_sort(){
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1,r);
int i = l, j = mid + 1, k = 0; //辅助数组w[k]
while (i <= mid && j <= r)
{
if (q[i] <= q[j])
w[k ++] = q[i];
else
w[k ++] = q[j];
}
whlie (i <= mid) //合并剩余数组
w[k ++] = q[i ++];
while (q <= r)
w[k ++] = q[j ++];
for (int i = l, j = 0; j < k; i ++, j ++ ) //拷贝合并后的数组回原数组
q[i] = w[j];
}
a.时间复杂度
(1) 最好情况：O(nlogn)
(2)平均情况：O(nlogn)
(3) 最坏情况：O(nlogn)
b.空间复杂度
O(n)
c.稳定
