第11讲 排序
流程
算法流程————运行效率———–（时空复杂度）————-稳定性
排序的基本概念
-
内排序和外排序
-
时间复杂度：最好情况，最坏情况，平均情况
运行效率取决于：
-
比较次数
-
移动次数
-
空间复杂度：一个算法只要没有开额外的空间（数组）或者递归过，那就是）O(1)的。
-
算法的稳定性：权值相等的两个元素，排序前和排序后相对位置没有发生变化就是稳定。
-
基于比较的排序有个下界：O(nlogn)
插入排序
-
简介：选定第一个元素作为新序列，然后不断从原序列中依次拿一个元素，比较出在新序列中的位置（从后往前），插入进去，大的全部后移。
-
（直接）插入排序：就是上面说的，没有任何优化的。
a. 时间复杂度
[1] 最好情况：O(n)
[2] 平均情况：O(n^2)
[3] 最坏情况：O(n^2)
b. 辅助空间复杂度
O(1)
c. 稳定
/*（直接）插入排序:可以过前十个数据，效率不是很高。*/
void insert_sort(){
/*第一个元素本身就是有序的，所以不用动，遍历从第二个开始。下标从0开始
的，所以从1开始遍历*/
for(int i = 1 ; i < n ; i ++){
//t等于当前元素 j从当前元素往前看
int t = q[i] , j = i;
//当j>0并且前一个元素也是大于t，把前一个元素后移
while(j && q[j - 1] > t){
q[j] = q[j - 1];
j--;
}
//遍历完之后，把t放到对应的位置上
q[j] = t;
}
}
- 折半插入排序：优化了比较次数
简介：在插入排序的基础上选出有序的新序列了，当一个新元素要插进去时我们不是挨个比，而是直接二分出第一个大于当前插入这个元素的位置，然后插进去（因为新序列里面是排好的，有序的）。
a. 时间复杂度
[1] 最好情况：O(n)
[2] 平均情况：O(n^2)
[3] 最坏情况：O(n^2)
b. 辅助空间复杂度
O(1)
c. 稳定
/*折半插入排序：*/
void binary_search_insert_sort(){
/*第一个元素本身就是有序的，所以不用动，遍历从第二个开始。下标从0开始
的，所以从1开始遍历*/
for(int i = 1 ; i < n ;i++){
//t当前数
int t = q[i];
/*二分出第一个大于当前数的位置。但是有个特殊情况，就是所有元素都小于
当前元素。所以需要对这种情况进行特判*/
//前一个元素比当前元素小，这个元素就不需要再去比较了，直接略过
if(q[i - 1] <= q[i]) continue;
//下面二分，l左边界，r右边界
int l = 0 , r = i - 1;
while(l < r){
int mid = l + r >> 1;
//前面序列中间元素大于当前元素，该元素在中间或者左边区间里面
if(q[mid] > t) r = mid;//改右边界，下一次继续二分
else l = mid + 1; //当前元素应该在右边，改左边界。
}
//找到一个中间位置后，将r及以后的元素往后移动一位，便于当前元素插入
for(int j = i - 1 ; j >= r ; j--){
q[j + 1] = q[j];
}
//将当前元素放到r（中间）位置上
q[r] = t;
}
}
- 希尔排序（shell sort）
简介：随意选取一个增量将序列分成若干组，组内用插入排序；所有组排完序之后，缩小增量，重新分组，再进行组内排序；如此重复直至增量为1，形成有序。（排序过程中，shell序列组间无序，组内有序）
(1) 时间复杂度
O(n^(3/2)) (每次除3的优化)
（插入排序对于部分有序的序列效率很高，所以组间用插入排序。n / 2 , n/ 4 , n/8 …这种增量的时间复杂度是O(n2) ）
(2) 空间复杂度
O(1)
(3) 不稳定
/*希尔排序：不稳定*/
void shell_sort(){
//枚举公差（增量），从n/2开始
// for(int d = n / 2 ; d ; d /= 2){
//增量n/3的，最后公差不一定等于2(2/3=0）,特判d=2除1，d！=2除3
for(int d = n / 3 ; d ; d = d == 2 ? 1 : d / 3){
//枚举每次的起点，从0开始
for(int start = 0 ; start < d ; start++){
//每隔d之间的元素为一组，组间用插入排序
for(int i = start + d ; i < n ; i += d ){
int t = q[i] , j = i;
while(j > start && q[j - d] > t){
q[j] = q[j - d];
j -= d;
}
q[j] = t;
}
}
}
}
交换排序
- 冒泡排序（bubble sort）
简介：会循环多次，第一次会将最小的元素冒泡到开头，后面全是一样的把次小元素冒到后面，最终形成有序。（把最小的元素冒到开头是从后开始遍历；那最大元素冒到最后是从前开始遍历）
优化：在某次冒泡的过程当中发现，没有交换过任何两个相邻的元素，那就说明每一对相邻元素都是前一个小于后一个，已经有序 ，可以提前退出。
(1) 时间复杂度
a. 最好情况：O(n)
b. 平均情况：O(n^2)
c. 最坏情况：O(n^2)
(2) 空间复杂度
O(1)
(3)稳定
/*冒泡排序：*/
void bubble_sort(){
//i从0开始，共迭代n-1次
for(int i = 0 ; i < n - 1 ; i++){
//有没有交换过
bool has_swap = false;
//每趟从后往前枚举. j>i:因为执行第i次的时候，0-i已经排好序了
for(int j = n - 1 ; j > i ; j-- ){
//所以只需要看i - n-1的部分
//后一个元素比前一个元素要小,交换
if(q[j] < q[j - 1]){
swap(q[j] , q[j - 1]);
//更新标记，交换过
has_swap = true;
}
}
//发现某次迭代过程当中没有交换过，说明前面已经有序
if(!has_swap) break;//退出循环
}
}
- 快速排序（基于分治，可以支持链式存储）
简介：找一个分界点，把序列分成小于等于和大于等于的两段，然后i，j指针遍历两个区间，左边区间大于分界点的和右边区间小于分界点的两个元素交换，直到两个指针相遇后，继续递归对这两段子段进行分区间遍历，直至有序。
(1) 时间复杂度
a. 最好情况：O(nlogn)
b. 平均情况：O(nlogn)
c. 最坏情况：O(n^2)
(2) 空间复杂度
O(logn)
（因为用到了递归，系统栈）
(3) 不稳定
/*快速排序*/
void quick_sort(int l , int r){
//当单个区间长度为1的时候就可以不用再分了
if(l >= r) return ;
//定义2个左右遍历指针指针i j 分界点x(取区间中点)
int i = l -1 , j = r + 1 , x = q[(l + r) / 2];
while(i < j){
//当当前指针所指的元素小于分界点的时候，i往后走
do i++; while(q[i] < x);
//当当前指针所指的元素大于分界点的时候，j往前走
do j--; while(q[j] > x) ;
//如果两个指针没有相遇过，交换2个位置的元素
if(i < j ) swap(q[i] , q[j]);
}
//递归左边区间
quick_sort(l , j) ;
//递归右边区间
quick_sort(j + 1 , r);
}
选择排序
- （简单）选择排序
简介：每次找第 i 小 的元素放到前面第 i 个位置上，交换过去。
(1) 时间复杂度
a. 最好情况：O(n^2)
b. 平均情况：O(n^2)
c. 最坏情况：O(n^2)
(2) 空间复杂度
O(1)
(3)不稳定
/*（简单）选择排序：*/
void select_sort(){
//从前往后遍历，枚举到n-1即可。因为前面n-1个元素排完序，最后一个元素必然在最后
for(int i = 0 ; i < n - 1 ; i++){
//用下标存一下，那个元素是最小的
int k = i ;
for(int j = i + 1 ; j < n ; j++){
//后面的元素小于前面的元素，k存下最小元素的下标
if(q[j] < q[k]){
k = j;
}
}
//将第k个元素换到第i个位置上
swap(q[i] , q[k]);
}
}
- 堆排序
简介：堆，完全二叉树，分 小根堆和大根堆为例。对于大根堆，性质： 每个结点大于等于子结点的值（小根堆反之）。一般用顺序存储，比链式存储效率快（这里的链式指的是链表，如果用二叉链表来存效率一样，注意甄别）。
建堆：按次序构建二叉树
排序（down）：从下往上递归进行，把根结点和子结点比较，最大的为根结点，其余的子结点，子树同样进行递归处理。
删除：把根结点和最后一个叶结点交换，然后删除叶结点即可，对于新的根结点，重新进行排序即可。
(1) 时间复杂度
a. 最好情况：O(nlogn)
b. 平均情况：O(nlogn)
c. 最坏情况：O(nlogn)
(2) 空间复杂度
O(logn)
(3)不稳定
void down(int u){
//t暂存当前点
int t = u ;
//u左儿子没有越界并且大于t, 把左儿子变成父结点（父结点t暂存了，直接覆盖）
if(u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
//这里处理u的右儿子
if(u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;
//如果根结点不等于子结点，交换
if(u != t){
swap(q[u] , q[t]);
//对子树进行同样操作，递归
down(t);
}
}
/*堆排序（大根堆）：下标一定要从1 开始，注意主函数中for*/
void heap_sort(){
//堆要维护它的长度，刚开始有n个
sz = n;
//从n/2开始(从下往上维护堆的性质,略过最后一层自然有序符合)，
for(int i = n / 2 ; i ; i --)down(i);
/*只要循环n-1次，最后一个自然有序*/
for(int i = 0 ; i < n - 1 ; i ++){
//将堆顶（最大元素）放大最后
swap(q[1] , q[sz]);
//删除最后一个元素
sz--;
//然后重新对堆进行down（排序）
down(1);
}
}
二路归并排序（merge sort）
基于分治的思想。
简介：划分两个区间，递归这两个区间进行排序；排完序后i，j两个指针从两个区间开始处进行比较，小的就赋值到辅助数组中去，最后在赋值到原数组形成有序。
- 时间复杂度
a. 最好情况：O(nlogn)
b. 平均情况：O(nlogn)
c. 最坏情况：O(nlogn) - 空间复杂度
O(n) - 稳定
/*归并排序*/
void merge_sort(int l , int r){
//判断边界
if(l >= r) return ;
//mid中点 》》1移位操作相当于除2
int mid = l + r >> 1;
//递归排左右两边
merge_sort(l , mid) , merge_sort(mid + 1 , r);
//二路归并,i,j指针分别指向两个区间的起始位置
int i = l , j = mid + 1 , k = 0;//k临时数组的下标
//当左右区间没有走完的时候
while(i <= mid && j <= r){
//如果左区间小于等于右区间的值，取左区间的值
if(q[i] <= q[j]) w[k++] = q[i++];
else w[k++] = q[j++];
}
//若左区间还有元素，全部赋值到w数组中
while(i <= mid)w[k++] = q[i++];
//若右区间还有元素，全部赋值到w数组中
while(j <= r) w[k++] = q[j++];
//将临时数组排好序的元素赋值到原数组q
for(int i = l , j = 0 ; j <k ; i++ , j++ )q[i] = w[j];
}
