1 插入排序
1.1 直接插入排序
基本原理:
将第n个数插入已经排序好的,长度为n-1的序列中。从n-1长度的序列中查找出待插入的元素应该插入的位置;给插入元素腾出空间。
操作方法:
从第2个数开始遍历到第n个数。插入第i个数时,先与第i-1个数进行比较。因为前i-1个数已经为有序序列,如果i-1号数数值小于第i号数,则仍然有序,无需操作。否则,先将第i号数暂存于A[0]出。然后从第i-1号位开始,从后往前进行比较,如果A[j]>A[0],则A[j]后移一位。当A[j]<=A[0]时,将A[0]中暂存的数值插入第j+1号位。
void InsertSort(int A[], int n)
{
int i,j;
for(i=2;i<=n;i++)
if(A[i]<A[i-1]){
A[0]=A[i];
for(j=i-1;A[j]>A[0];j--) A[j+1]=A[j];
A[j+1]=A[0];
}
}
1.2 折半插入排序
基本原理:
将第n个数插入已经排序好的,长度为n-1的序列中。使用折半查找的方法找出待插入的位置,然后移动插入元素之后的元素。
操作方法:
与直接插入排序法类似,将第二层for循环中逐个元素进行比较的操作更改为折半查找。
void InsertSort2(int A[],int n)
{
int i,j,low,mid,high;
for(i=2;i<=n;i++){
low=1;high=i-1;
A[0]=A[i];
while(low<=high){
mid = (low+high)/2;
if(A[0]<A[mid]) low=mid+1;
else high=mid-1;
}
for(j=i-1;j>=high+1;j--) A[j+1]=A[j];
A[high+1] =A[0];
}
}
1.3 希尔排序
基本原理:
先将序列表分割为若干个形如L[i,i+d,……,i+kd]的子表,分别进行插入排序,当整个表中元素已经基本有序时,再对全体记录进行一次直接插入排序。
操作方法:
先取一个小于n的步长d,将表中的元素分为d1组,所有距离为d1的倍数的记录存放于同一组中,在各组中进行直接插入排序;然后取第二个步长,重复操作,直到所取到的d1为1,再进行直接插入排序。
void ShellSort(int A[],int n)
{
int dk,i,j;
for(dk=n/2;dk>=1;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[j]>A[0];j-=dk) A[j+dk]=A[j];
A[j+dk]=A[0];
}
}
}
2 交换排序
2.1 冒泡排序
基本原理:
将n个元素两两进行比较,将两个数按升序进行排序,从第1个数遍历到第n个数后,能将n个数中最大的数置于第n位。按照此方法循环操作n-1次,每次减少一位已经排列好的数字。
操作方法:
一层for循环从0开始遍历到n-1;二层for循环n-1开始遍历到i+1,如果A[j]>A[j+1],则交换两数的序号。
void BubbleSort(int A[],int n)
{
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
if(A[j]<A[j-1]){
int t=A[j];
A[j]=A[j-1];
A[j-1]=t;
}
}
2.2 快速排序
基本思想:
在序列中任意取一个元素p作为基准,通过一趟排序将排序表划分为两个部分,p左边的元素均小于p,p右边的元素均大于等于p。然后分别递归地对两个子表进行上述操作,知道每个部分只有一个元素或者为空。
实现方法:
假设划分函数已经完成。在QuickSort函数中调用划分函数,返回划分位置p,然后分别递归p的左边序列和p的右边序列。
在Partition函数中,取序列中第一位数作为p。将第high位数与p对比,如果A[high]>p,则指针前移high–;否则,将A[high]位数放置于第low位。将第low位数与p进行对比,如果A[low]<p,则指针后移,low++;否则,将第low位数放置于第high位。每一次while循环都会交换一次how和high位处的数。While循环结束后将p填入空缺的low号位,返回low。
int Partition(int A[],int low,int high)
{
int p=A[low];
while(low<high){
while(low<high&&A[high]>p) high--;
A[low]=A[high];
while(low<high&&A[low]<p) low++;
A[high]=A[low];
}
A[low]=p;
return low;
}
void QuickSort(int A[],int low,int high)
{
if(low<high){
int p=Partition(A,low,high);
QuickSort(A,low,p);
QuickSort(A,p+1,high);
}
}
3 选择排序
3.1 简单选择排序
基本原理:
从n个数中选出最小的数放置于第1号位。循环操作n-1次,每次减少一位已经放置好的数字。
操作方法:
一层for循环从0遍历到n-1,将第1位数暂存为min值。二层for循环从i+1遍历到n-1,将每个数分别与min值进行对比,如果A[j]<A[min],则替换min的数值。到第二层for循环执行完成后,再交换A[min]和A[i]的数值。
void SelectSort(int A[],int n)
{
int i,j;
for(i=0;i<n-1;i++){
int min =i;
for(j=i+1;j<n;j++)
if(A[j]<A[min]) min=j;
if(min != i){
int t=A[i];
A[i] = A[min];
A[min]=t;
}
}
}
3.2 堆排序
基本思想:
在排序过程中,将序列视为一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点的内在关系,在当前无序区中选择关键字最大的元素。
堆:(1)树的形状必须为完全二叉树
(2)每一个结点的键必须要大于它的所有结点的键
实现方法:
(1)构建堆,为给定数组构造一个大根堆
由于堆是完全二叉树,所以可以使用数组来实现堆,按照从上到下、从左到右的顺序来记录堆的元素。非叶子结点的键会在后[n/2]个位置。数组中,对于父母位置i来说,子女会占据2i和2i+1两个位置。
(2)删除最大键,将剩下的数组构建成堆;即,将最大值换到最末尾的位置,将剩下的部分构建成堆
void AdjustDown(int A[],int k,int len)
{
A[0]=A[k];
for(int i=k*2;i<=len;i*=2){
if(i<len &&A[i+1]>A[i]) i++;
if(A[i]<=A[0]) break;
else{
A[k]=A[i];
k=i;
}
}
A[k]=A[0];
}
void HeapSort(int A[],int len)
{
for(int i=len/2;i>0;i--)
AdjustDown(A,i,len);
for(int j=len;j>1;j--){
int t=A[1];
A[1]=A[j];
A[j]=t;
AdjustDown(A,1,j-1);
}
}
4 归并排序
基本思想:
将长度为n的序列表分为n个长度为1的有序序列表,再将n个有序序列表合并为1个长度为n的有序序列表。
实现方法:
MergeSort函数:将序列分成两个序列,两个序列再分别递归调用MergeSort函数,知道每个序列只有一个数时递归停止。然后调用Merge函数将有序序列合并。
Merge函数:将数组A中元素复制到B中,在从B中lowmid,mid+1high两段序列中选择较小的元素放入数组A。
void Merge(int A[],int low,int mid,int high)
{
int B[N];
int i,j,k;
for( i=low;i<=high;i++) B[i]=A[i];
for( i=low,j=mid+1,k=low;i<=mid&&j<=high;k++){
if(B[i]<B[j]) A[k]=B[i++];
else A[k]=B[j++];
}
while(i<=mid) A[k++]=B[i++];
while(j<=high) A[k++]=B[j++];
}
void MergeSort(int 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);
}
}
5 时间复杂度及稳定性比较
算法 | 最优 | 最劣 | 平均 | 稳定性 |
---|
插入 | O(n) | O(n^2) | O(n^2) | 稳定 |
折半 | O(n) | O(nlogn) | O(nlogn) | 稳定 |
希尔 | | | | 不稳定 |
冒泡 | O(n^2) | O(n^2) | O(n^2) | 稳定 |
快速 | O(nlogn) | O(n^2) | O(nlogn) | 不稳定 |
选择 | O(n^2) | O(n^2) | O(n^) | 不稳定 |
堆 | O(nlogn) | O(nlogn) | O(nlogn) | 不稳定 |
归并 | O(nlogn) | O(nlogn) | O(nlogn) | 稳定 |
6 适用场景
6.1 序列顺序无影响的排序
选择排序:对任何输入而言,选择排序都是一个O(n^2)的算法;键的交换次数为O(n);
冒泡排序:对任何输入而言,冒泡排序都是一个O(n^2)的算法;
归并排序:归并排序在最坏情况下,比较次数仍然十分接近排序算法理论上能够达到的最小次数。
归并排序递归关系式: C(n)=2C(n/2)+n-1,C(1)=0
如果情况最差,n=2^k,则:
C(n)=nlog2 n -n+1
(最小次数,nlog2 n! = nlog2 n =1.44n)
最坏情况,也需要n=2^k
6.2 适用于基本有序序列
插入排序:在序列有序时,只遍历一次序列,时间复杂度O(n);
折半插入排序:类似于插入排序
6.3适用于随机顺序
快速排序:
最优:如果所有的分裂点均位于相应数组的中点,此时为最优的情况,比较次数为n,此时:
C(n)=2C(n/2)+n,C(1)=0
n=2^k时,求得:C(n)=nlog2n
最劣:当A[0…n-1]是严格的递增数组,以A[0]为中轴,从左到右的扫描会停在1号位置,从右到左的扫描会停在0号位置,然后A[0] 再与它本身进行交换,此时总比较次数为:
C(n)=(n+1)+(n)+……+3=(n+1)(n+2)/2-3=O(n^2)
平均:设分裂点可能出现在任何位置s(0<=s<=n-1):
C(n)=2nlnn=O(nlogn)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)