插入排序
直接插入排序
1
2
3
4
5
6
7
8
9
10
| void InsertSort(ElemType A[],int n){
int i,j;
for(i=2;i<=n;i++){ //将A数组插入已排序好的序列
if(A[i]<A[i-1]){
A[0]=A[i]; //复制为哨兵
for(j=i-1;A[0]<A[j];--j) A[j+1]=A[j]; //向后挪位
A[j+1]=A[0]; //复制到插入位置
}
}
}
|
空间效率：O（1）
时间效率：最好情况O（n），最坏情况O（）
算法比较稳定，适用于顺序存储和链式存储的线性表
折半插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void InsertSort(ElemType A[],int n){
int i,j,low,high,mid;
for(i=2;i<=n;i++){
A[0]=A[i]; //将A[i]暂存A[0]
low=1;high=i-1; //设置折半查找范围
while(low<=high){ //折半查找
mid=(low+high)/2; //取中间点
if(A[mid]>A[0]) high=mid-1; //查找左半子表
else low=mid+1; //查找右半子表
}
for(j=i-1;j>high+1;--j) A[j+1]=A[j]; //统一后移元素
A[high+1]=A[0];
}
}
|
时间复杂度O（） ，是一种稳定排序方法
希尔排序
基本思想：先将待排序表分割成若干形如L[i,i+d,i+2d,…,i+kd]的特殊子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，在对整个记录进行一次直接插入排序。
1
2
3
4
5
6
7
8
9
10
11
| 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[i]插入有序增量子表
A[0]=A[i]; //暂存A[0]
for(j=i-dk;j>0&&A[0]<A[j];j-=dk)
A[j+dk]=A[j]; //记录后移，查找插入的位置
A[j+dk]=A[0]; //插入
}
}
|
空间效率：O（1）
时间效率：n在某个特定范围内，O()；最坏情况O();不稳定
交换排序
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
| void BubbleSort(ElemType A[],int n){
for(int i=0;i<n-1;i++){
bool flag =false; //表示本趟冒泡是否发生交换的标志
for(int j=n-1;j>i;j--){ //一趟冒泡过程
if(A[j-1]>A[j]){ //若为逆序
swap(A[j-1],A[j]); //交换
flag=true;
}
}
if(flag==false) return ;
}
}
|
空间效率：O（1）
时间效率：最好情况O（n），最坏情况O（）。稳定
快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void QucikSort(ELemType A[],int low,int high){
if(low<high){ //递归
int pivotpos=Partition(A,low,high);
QucikSort(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[high]<=pivot) ++low;
A[high]=A[low]; //将比枢轴大的元素移动到左端
}
A[low]=pivot; //枢轴元素怒存放到最终位置
return low; //返回存放枢轴的最终位置
}
|
空间效率：O（）
时间效率：最好情况O（），最坏情况O（）。不稳定
递归次数与每次划分后得到的分区的处理顺序无关，与各元素的初始排列有关
选择排序
简单选择排序
1
2
3
4
5
6
7
8
| void SelectSort(ElemType A[],int n){ // 每次选择最小的元素放到固定位置
for(int i=0;i<n-1;i++){
int min=i;
for(int j=i+1;j<n;j++)
if(A[j]<A[min]) min=j;
if(min!=i) swap(A[i],A[min]);
}
}
|
空间效率：O（1）
时间效率：最好情况O（n），最坏情况O（）。不稳定
堆排序
堆：父节点大于所有子节点或者小于所有子节点的完全二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void BuildMaxHeap(ElemType A[],int len){
for(int i=len/2;i>0;i--) HeadAdjust(A,i,len); //反复调整堆
}
void HeadAdjust(ElemType A[],int k,int len){
//函数HeadAdjust将元素k为根的子树进行调整
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]; //将A[i]调整到双亲结点
k=i; //继续向下筛选
}
}
A[k]=A[0]; //将筛选出的值放入最终位置
}
void HeapSort(ElemType A[],int len){
BuildMaxHeap(A,len); //初始建堆
for(int i=len;i>1;i--){
Swap(A[i],A[1]); //和堆底元素交换
HeadAdjust(A,1,i-1); //调整，把剩余元素整理成堆
}
}
|
空间效率：O（1）
时间效率：O（）。不稳定
归并排序
将两个或两个以上的有序表合并成一个新的有序表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));
void Merge(ElemType A[],int low,int mid,int high){
int i,j,k;
for(k=low;k<=high;k++)
B[k]=A[k]; //将A中所有元素复制到B中
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(B[i]<=B[j]) A[k]=B[i++]; //比较B的左右两端中的元素
else A[k]=B[j++]; //将较小值复制到A中
}
while(i<=mid) A[k++]=B[i++]; //若第一个表未检测完，复制
while(j<=high) A[k++]=B[j++]; //若第二个表未检测完，复制
}
void MergeSort(ElemType A[],int low,int high){
if(low<high){
int mid=(low+high)/2; //从中间划分两个子序列
MergeSort(A,low,mid); //对左侧子序列进行递归排序
MergeSort(A,mid+1,high); //对右侧子序列进行递归排序
Merge(A,low,mid,high); //排序
}
}
|
空间效率：O（n）
时间效率：O（）。稳定
基数排序
每次排序根据数字中的每一位进行排序
空间效率：O（r）
时间效率：O（d(n+r)）。稳定,与序列的初始状态无关
| 算法种类 |
最好情况 |
平均情况 |
最坏情况 |
空间复杂度 |
是否稳定 |
| 直接插入排序 |
O（n） |
O（） |
O（） |
O（1） |
是 |
| 冒泡排序 |
O（n） |
O（） |
O（） |
O（1） |
是 |
| 简单选择排序 |
O（） |
O（） |
O（） |
O（1） |
否 |
| 希尔排序 |
|
|
|
O（1） |
否 |
| 快速排序 |
O（） |
O（） |
O（） |
O（） |
否 |
| 堆排序 |
O（） |
O（） |
O（） |
O（1） |
否 |
| 2路归并排序 |
O（） |
O（） |
O（） |
O（n） |
是 |
| 基数排序 |
O（d(n+r)） |
O（d(n+r)） |
O（d(n+r)） |
O（r） |
是 |
