前言
本文将介绍常见的9种排序算法，围绕下面几个问题讨论每一种排序算法:
- 这个算法的思想是什么?
- 这个算法的稳定性怎样?时间复杂度是多少?
- 在什么情况下，算法出现最好情况or最坏情况?
- 这个算法的具体实现?
以下排序算法都以从小到大排序
１.冒泡排序(交换排序)
1.1算法思想:
排序每次对相邻的两个元素比较,如果它们的相对排列次序与所希望的不符，便交换它们的次序,这样,各元素就会像水中冒气泡一样通过交换它们的位置得到最终正确的位置.升序时,每次都把最大的元素放到n-i-1个元素的位置上,每次遍历的元素个数-1;
1.2 时间复杂度
最好的情况下：正序有序,则只需要比较n次，故为O(n)
最坏情况下:逆序有序,则需要比较(n-1)+(n-2)+…….+1，故为O(n*n)
1.3 稳定性
排序过程中只交换两个元素的位置,因此,当两个数相等时，是没有必要交换两个数的位置的,所以，它们相对位置并没有改变,冒泡算法是稳定的。
1.4代码实现
void BubbleSort(int a[],int n) //升序时,每次把最大的放到n-i-1个元素的位置上,每次遍历的元素个数-1;
{
int i,j,k;
for(i=0;i<n;i++){
for(j=0;j<n-i-1;j++)
{
if(a[j] > a[j+1]) //比较找本趟最大关键字.
{
k=a[j]; //a[j]和a[j+1]交换
a[j]=a[j+1];
a[j+1]=k;
}
}
}
}2.直接选择排序(选择排序)
2.1算法思想
首先在未排序序列中找到最小元素,存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小的元素,然后放到排序序列的末尾。以此类推，直到所有的元素均排序完毕,具体的做法是:选择最小的元素与未排列部分首部交换,使得序列的前面为有序。
2.2时间复杂度
最好的情况下,交换0次,但是每次都要找到最小的元素,因此大约把必须遍历N*N次,因此为O(N*N)，减少了交换次数。
2.3稳定性
由于每次都是选择未排序序列A中最小元素x与A中第一个元素交换,因此跨距离了,很可能破坏了元素间的相对位置,因此选择排序是不稳定的.
2.4代码实现
void SelectSort(int a[],int n)
{
int i,j,k,temp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++){ //升序时,每次把最小的放在最前面,每次遍历的元素-1;从前面加
if(a[k] > a[j])
{
k=j;
}
}
if(k!=i)
{
temp = a[i];
a[i]=a[k];
a[j]=temp;
}
}
}3.直接插入排序(插入排序)
3.1算法思想
将一组数据分成两组,分别将其称为有序组和待插入组,每次从待插入组中取出一个元素,与有序组的元素进行比较,并找到合适的位置,将该元素查到有序组中,就这样,每次插入一个元素,有序组增加,待插入组减少,直到待插入组元素的个数为0,当然,插入过程中涉及到了元素的移动。
3.2算法时间复杂度
最好的情况下:正序有序(从小到大),这样只需要比较n次,不需要移动,因此时间爱你复杂度为O(n);
最坏的情况下:逆序有序,这样每一个元素就需要比较n次,共有n个元素,因此实际复杂复为O(n*n)
平均情况下:O(n*n)
3.3稳定性
在插入排序中,K1是已排好序部分中的元素,当K2与K1比较时,直接插到K1的后面(没有必要插入到K1的前面,这样做还需要移动元素),因此,插入排序是稳定的.
代码实现
void InsertSort(int *num,int n){
int i = 0;
int j = 0;
int tmp = 0;
for(int i = 1;i < n;i++){
tmp = num[i]; //从待插组中取出第一个元素
j = i-1;
while(j >= 0 && tmp < num[j]) //注意判断条件为两个,j>=0为其边界限制,第二个为插入判断条件
{
num[j+1] = num[j]; //若不是合适的位置,有序组元素向后移动.
j--;
}
num[j+1] = tmp; //找到合适的位置,将元素插入.
}
}
4.快速排序(交换排序)
4.1算法思想
它是由冒泡排序改进而来的,在待排序的n个记录中取一个记录(通常取第一个记录)，把该记录放入适当位置后,数据序列被此记录划分成两部分,所有关键字比该关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归为),这个过程称为一趟快速排序。
4.2算法复杂度
最好的情况下:因为每次都将序列化分为两部分(一般二分复杂度都和logN相关),故为O(N(*logN)
最坏的情况下:基本有序时m退化为冒泡排序,几乎要比较N*N此,故为O(N*N)
4.3 稳定性
由于每次都需要和中轴元素交换,因此原来的顺序就可能被打乱,如5 3 3 4 3 8 9 10 11 会将3的顺序打乱,所以说，快速排序是不稳定的。
4.4 代码实现
void QuickSort(int a[],int low,int high){
int i=low,j=high;
if(low <high)
{
int temp=a[low];
while( i < j )
{
while(a[j] > temp && i < j){
j--;
}
a[i] = a[j];
while(a[i] <=temp && i<j){
i++;
}
a[j]=a[i];
}
a[i]=temp;
QuickSort(a,low,i-1);
QuickSort(a,i+1,high);
}
}5.归并排序
5.1算法思想:将待排序的集合一分为二,直到排序集合就剩下一个元素为止,然后不断合并两个排好序的数组.(先分割后合并)
5.2算法时间复杂度
最好的情况下:一趟归并需要n次,总共需要logN次,因此为O(N*logN)
最坏的情况下:接近于平均情况下,为O(N*logN)
说明:对长度为n的文件,需要进行logN趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlogn).
5.3 稳定性
归并排序最大的特色就是它是一种稳定的排序算法,归并过程中是不会改变元素的相对位置的。
缺点：它需要O(n)的额外空间,但是很适合于多链表排序
5.4 代码实现
int merge(int a[],int low,int mid,int high){ //对排好序的两个分组进行合并
int i=low,j=mid+1,p=0;
int *temp=(int *)malloc(sizeof(int)); //开辟临时数组存合并后的元素。
if(temp == NULL){
return -1;
}
while(i<=mid && j<=high){
temp[p++]=((a[i]<=a[j])?a[i++]:a[j++]);
}
while(i<=mid){
temp[p++]=a[i++];
}
while(j<=high){
temp[p++]=a[j++];
}
for(p=0,i=low;i<=high;i++,p++){
a[i]=temp[p];
}
free(temp);
}
void mergeSort(int a[],int low,int high)
{
int mid=(low + high)/2;
if(low < high) //说明此时只剩下一个元素，不用再分。
{
mergeSort(a,low,mid); //对左边的元素依然进行分，
mergeSort(a,mid+1,high);
merge(a,low,mid,high);
}
}
如下图所示:
6.希尔排序(插入排序)
6.1算法思想
希尔排序也是一种插入排序算法,实际上是一种分组插入方法,先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离d1的倍数的记录放在同一个组中,在各组内进行直接插入排序,然后,取第二个增量d2(
6.2 时间复杂度
最好情况:希尔排序的好坏和步长的选择有关,目前还没有得出最好的步长如何选择,因此最好情况下的算法时间复杂度不确定.
最坏情况下:O(N*logN)
平均情况下:O(N*logN)
6.3 稳定性
由于多次插入排序,我们知道一次插入排序是稳定的,不会改变ｖｘｉａｎｇｔ元素的相对顺序,但是在不同的插入排序中,相同的元素可能在各自的插入排序中移动,最后稳定性会被打乱,所以希尔排序是不稳定的.
看一个简单的例子:
以n=10的一个数组49,38,65,97,26,13,27,49,55,4为例
第一次gap = 10 /2 =5;
6.4 代码实现
//完全按照定义实现.
void shellSort1(int a[],int n){
int i,j,gap;
for(gap = n/2;gap > 0;gap/=2){
for(i=0;i<gap;i++){
for(j = i+gap;j<n;j+=gap){
if(a[j] < a[j-gap]){
int temp = a[j];
int k = j - gap;
while(k >= 0 && a[k] > temp){
a[k+gap] = a[k];
k-=gap;
}
a[k+gap] = temp;
}
}
}
}
}
//简化版的希尔排序,相当于是所有的分组同时比较,比如说当gap 为2时,第一种方法是1,3,5,7,9插入排序完，在进行2,4,6,8,10进行排序,而当前的方法是1,３排序完,接着排2,4然后又排,1,3,5，然后又是2,4,6,以此类推,所有的组同时进行。
void shellSort2(int a[],int n){
int j,gap;
for(gap = n/2;gap > 0;gap /=2){
for(j = gap;j<n;j++){
if(a[j] < a[j - gap]){
int temp = a[j];
int k = j - gap;
while(k >= 0 && a[k] > temp){
a[k+gap] = a[k];
k-=gap;
}
a[k + gap] = temp;
}
}
}
}7.堆排
7.1算法解析
- 建初始堆(以顶堆为例),这一步骤把初始化序列建成了一个满足大顶堆性质的序列,且每颗子树都满足,这个时候堆顶是本序列中最大的元素,因此将最后一个元素和堆顶元素调换,把最大值放在最终的位置上,建立好了初始堆,就保留了排序时的比较结果,后面的调整都可以再此基础上进行,加快排序效率.
- 由于每次将堆顶元素和最后一个对调,破坏了堆的性质,因此要从新向下调整,建立大顶堆(这里在初始化堆的基础上,只要将堆顶元素调到合适的位置即可).
- 调整完了之后,又将堆顶元素和未序区间的最后一个元素对调,
- 重复2,3直到堆中剩余一个元素.
7.2 算法时间复杂度
最坏情况下,接近于最好情况下,因此是一种不稳定的排序.
稳定性
堆排序需要不断的调整堆,因此它是一种不稳定的排序.
代码如下
大顶堆:
void AdjustDown(int 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 BuildMaxHeap(int A[],int len){
for(int i =len/2;i>0;i--){
AdjustDown(A,i,len); //向下调整.
}
}
void HeapSort(int A[],int len){
BuildMaxHeap(A,len);
for(int i = len; i>1;i--){
A[0] = A[1];
A[1] = A[i];
A[i] = A[0]; //堆顶和未序区间尾元素对调
AdjustDown(A,1,i-1);
}
}