一、插入排序
基本思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列，直到全部记录插入完成
直接插入排序
时间复杂度：最好O(n):表中元素有序，最坏O(n2):表中元素逆序
空间复杂度：O(1)
稳定性：稳定，总是插入到相同元素的后面
适用性：顺序、链式(从前往后查找指定元素位置)
代码
void InsertSort(ElemType A[],int n) //下标：1~n,0为哨兵
{
int i,j;
for(i = 2;i <= n;i++)
{
if(A[i] < A[i-1]) //若待排元素大于前面已排元素，说明有序，无需挪动
{
A[0] = A[i]; //哨兵
for(int j = i-1;A[j] > A[0];j--) //在已排序列中寻找位置
{
A[j+1] = A[j];//边比较边移动元素
}
A[j+1] = A[0];//插入操作，注意：下标需要加1
}
}
}
折半插入排序 小数据量性能好
时间复杂度：最好O(n):表中元素有序，最坏O(n2):表中元素逆序
- 虽然折半插入排序可以O(logn)的复杂度找到插入位置，但挪动元素仍为O(n)，因此时间复杂度仍为O(n2)
- 数据量较小时性能好
空间复杂度：O(1)
稳定性：稳定，总是插入到相同元素的后面
适用性：仅顺序
代码
void InsertSort(ElemType A[],int n)
{
int i,j,low,high,mid;
for(int i = 2;i <= n;i++)
{
if(A[i] < A[i-1])
{
A[0] = A[i]; //哨兵
low = 1,high = i - 1;//设置折半查找范围
while(low <= high)
{
mid = (low + high) / 2;
if(A[mid] > A[0]) high = mid - 1;//查找左半子表
else low = mid + 1; //查找右半子表，注意：相等时查找右半子表是为了保证排序的稳定性
}
//循环后low位于high右边
for(j = i - 1;j >= low;j--) //统一后移元素，腾出位置
{
A[j + 1] = A[j];
}
A[low] = A[0]; //插入操作
}
}
}
希尔排序 重点掌握思想且会手动模拟
时间复杂度：最坏O(n2)
空间复杂度：O(1)
稳定性：不稳定
反例：2 2 1 第一趟排序后1 2 2
适用性：仅顺序
代码
void ShellSort(ElemType A[],int n)
{
int dk,i,j;
for(dk = n/2;dk >= 1;dk = dk / 2) //增量变化(无统一规定)
{
for(i = dk + 1;i <= n;i++)
{
if(A[i] < A[i - dk])
{
A[0] = A[i]; //哨兵
for(j = i - dk;j > 0 && A[0] < A[j];j = j - dk)
{
A[j + dk] = A[j]; //边查找边后移
}
A[j + dk] = A[0]; //插入，注意：下标为j + dk
}
}
}
}
二、交换排序：每次排序能确定一个元素的最终位置
冒泡排序
时间复杂度：最好O(n),最坏O(n2)
最好情况：元素基本有序
最坏情况：元素逆序
空间复杂度：O(1)
稳定性：稳定
当i>j且A[i] = A[j]时，不会发生交换，因此是稳定的
适用性：顺序、链式
代码
void BubbleSort(LL A[],int n)
{
int i,j;
bool flag = false; //表示本趟冒泡是否发生交换
for(i = 1;i <= n - 1;i++) //表示每趟交换的左端点，单个元素无需交换，故n-1
{
flag = false;
for(j = n;j > i;j--) //从右往左依次交换
{
if(A[j] < A[j-1]) //逆序则两两交换
{
flag = true;
swap(A[j],A[j-1]);
}
}
if(flag == false) return;//若本趟遍历没有发生交换，说明已经有序
}
}
快速排序 基于分治法 出选择，给出某趟排序的结果
特点：基于分治法；平均性能最优的内部排序算法；每次确定一个元素最终位置
时间复杂度：最好O(nlogn)，最坏O(n2)
- 快排是所有内部排序算法中平均性能最优的排序算法
- 快排的时间性能主要取决于划分操作的好坏
- 最好情况：每次均匀划分，logn个序列，每个序列遍历一次 O(nlogn)
- 最坏情况：序列基本有序或逆序，每次划分出长度为n-1和1的序列 O(n2)
空间复杂度：最好O(logn)，最坏O(n)
- 快排是递归的，因此需要系统栈来保存每层调用的信息，其容量与递归调用的最大深度有关
稳定性：不稳定
反例：2 2 1 一趟排序后：1 2 2
适用性：仅顺序结构
代码
标准版
void QuickSort(ElemType A[],int low,int high)
{
if(low < high)
{
int pivotpos = Partition(A,low,high);
QuickSort(A,low,pivotpos - 1);
QuickSort(A,pivotpos + 1,high);
}
}
int Partition(ElemType A[],int low,int high)
{
ElemType pivot = A[low];//将当前表中第一个元素设为枢纽，进行划分
while(low < high)
{
while(low < high && A[high] >= pivot) high--;
A[low] = A[high];//将比枢纽小的元素移动到左端
while(low < high && A[low] <= pivot) low++;
A[high] = A[low];//将比枢纽大的元素移动到右端
}
A[low] = pivot;//枢纽元素存放到最终位置
return low;//返回枢纽的最终位置
}
简洁版
void Quick_Sort(LL a[],int low,int high)
{
if(low < high)
{
int l = low,r = high,pivot = a[low];
//划分操作
while(l<r)
{
while(l < r && a[r] >= pivot) --r;
a[l] = a[r];
while(l < r && a[l] <= pivot) ++l;
a[r] = a[l];
}
a[l] = pivot;
Quick_Sort(a,low,l-1);
Quick_Sort(a,l+1,high);
}
return;
}
三、选择排序
基本思想：每趟排序中在后面n-i+1个待排元素中选取关键字最小的元素，作为有序子序列的第i个元素，直至n-1趟做完。
简单选择排序
时间复杂度：始终O(n2)
空间复杂度：O(1)
稳定性：不稳定
反例：2 2 1 第一趟排序后1 2 2
适用性：顺序、链式(仅交换结点信息)
代码
void SelectSort(ElemType A[],int n) //A[0 ~ n-1]
{
for(int i = 0;i < n - 1;i++) //共进行n-1趟排序
{
int Min = i;//记录最小值下标
for(int j = i+1;j < n;j++) //在A[i ~ n-1]中选择最小值
{
if(A[j] < A[Min]) Min = j;//更新最小元素位置
}
if(Min != i) swap(A[Min],A[i]); //共移动3次元素
}
}
堆排序：时间复杂度始终O(nlogn)，空间复杂度只需O(1)，优于快排的地方
时间复杂度：始终为O(nlogn)
建堆时间为O(n)，之后有n-1次调整操作，每次调整时间复杂度为O(h)
空间复杂度：O(1)
稳定性：不稳定
反例：1 2 2 3，最终排序结果为3 2 2 1
适用性：顺序
代码
标准版
建立大根堆
void HeadAdjust(ElemType A[],int k,int len) //将元素k为根的子树进行调整
{
A[0] = A[k]; //A[0]暂存子树的根结点
for(int i = 2*k;i <= len;i = i * 2) //沿k较大的子结点向下筛选
{
if(i+1 <= len && A[i+1] > A[i]) ++i;//选择较大的子结点
if(A[0] >= A[i]) break;//若符合堆得要求，筛选结束
else
{
A[k] = A[i];//否则将子结点上浮至双亲结点
k = i;//修改根结点的下标，以便继续向下筛选
}
}
A[k] = A[0];//被筛选结点放入最终位置
}
void BuildMaxHeap(ElemType A[],int len)
{
for(int i = len / 2;i >= 1;i--) //i=[i/2] ~ 1反复调整根
{
HeadAdjust(A,i,len);
}
}
void HeapSort(ElemType A[],int len)
{
BuildMaxHeap(A,len);
for(int i = len;i >= 1;i--)
{
print(A[1]);
swap(A[1],A[i]);
//输出并交换堆顶元素
HeapAdjust(A,1,i - 1);//调整，把剩余i-1个元素整理成堆
}
}
简洁版
建立小根堆并排序
void HeapAdjust(LL a[],int k,int len)
{
a[0] = a[k];
for(int i = 2*k;i<=len;i*=2)
{
if(i < len && a[i] > a[i+1]) ++i;
if(a[0] < a[i]) break;
else
{
a[k] = a[i];
k = i;
}
}
a[k] = a[0];
}
void HeapSort(LL a[],int len)
{
for(int i = len/2;i>=1;i--)
{
HeapAdjust(a,i,len);
}
for(int i = len;i>=1;i--)
{
cout<<a[1];
if(i>1) cout<<' ';
swap(a[1],a[i]);
HeapAdjust(a,1,i-1);
}
}
四、归并排序 基于分治法
时间复杂度：始终O(nlogn)
空间复杂度：O(n)
稳定性：稳定
适用性：顺序、链式
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int a[N],tmp[N],n;
void merge_sort(int a[],int l,int r)
{
if(l>=r) return;//区间元素个数不大于1，不需要排序
int mid = l+r>>1;
merge_sort(a,l,mid),merge_sort(a,mid+1,r);//折半拆分一个区间
int i = l,j = mid+1,k = 0;
while(i<=mid && j<=r) //合并后的两个序列一定是有序的，双指针算法进行选择
{
if(a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while(i<=mid) tmp[k++] = a[i++];//两个序列长度可能不一致，因此把剩余的加入临时数组
while(j<=r) tmp[k++] = a[j++];
for(int i=l,j=0;i<=r;i++,j++) //排序完毕，将临时数组赋值给原数组，区间[l,r]排序完成
{
a[i] = tmp[j];
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
merge_sort(a,0,n-1);
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
五、基数排序 稳定 基于关键字各位的大小进行比较 多关键字排序思想
主要步骤
设长度为n的线性表中每个结点的关键字由d元组组成，基数为r。通常采用链式基数排序
- 分配：开始时，把Q0~Qr-1各个队列置成空队列，然后依次遍历线性表中的每个结点，若结点的关键字为k,则把该关键字放入Qk队列中
- 收集：把Q0~Qr-1各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表
- 共进行d趟分配和收集
时间效率
共进行d趟分配和收集，一趟分配需要O(n),一趟收集需要O(r),故时间复杂度为O(d(n+r))，与序列初始效率无关
空间效率
一趟排序需要r个队列，空间复杂度为O(r)