简单选择排序：
/*
在未排序的序列中选出最小的元素和序列的首位元素交换，接下来在剩下的未排序的序列中再
选出最小的元素与序列的第二位元素交换
*/
#include<cstdio>
#include<iostream>
using namespace std;
int num[10]={9,24,5,2,3,1,6,8,10,7};
void sort(int n)
{
int minn;
for(int i=0;i<n-1;i++)
{
minn=i;
for(int j=i+1;j<n;j++)
{
if(num[j]<num[minn])
{
minn=j;
}
}
swap(num[i],num[minn]);
}
}
int main()
{
sort(10);
for(int i=0;i<10;i++)
{
printf("%d ",num[i]);
}
return 0;
}
堆排序：
/*
利用最大堆输出堆顶元素，即最大值，将剩余元素重新生成最大堆，继续输出堆顶元素，重
复这个过程，直到全部元素都输出。
*/
#include<cstdio>
#include<iostream>
using namespace std;
int num[10]={9,24,5,2,3,1,6,8,10,7};
void adjust(int i,int n)
{
int child,temp;
//将第i个依次跟后面的比较找到它应该放置的位置
for(temp=num[i];(2*i+1)<n;i=child)
{
child=(2*i+1);
if(child!=n-1&&num[child]<num[child+1])child++;//选取最大的元素
if(temp<num[child])num[i]=num[child];
else break;
}
num[i]=temp;
}
void heapsort(int n)
{
//建立最大堆
for(int i=(n-1)/2;i>=0;i--)
{
adjust(i,n);
}
//从最后一个元素开始，每一个跟num[0]交换 ，换完之后继续调整
for(int i=(n-1);i>0;i--)
{
swap(num[i],num[0]);
adjust(0,i);
}
}
int main()
{
heapsort(10);
for(int i=0;i<10;i++)
{
printf("%d ",num[i]);
}
return 0;
}
简单插入排序：
/*
将待排序的一组序列分为已经排好序的和未排序的两个部分，初始状态时，已排序序列只包
含第一个元素，此后将未排序序列中的元素逐一插入到已排好序的序列中。经过n-1次插入
后，未排序序列中元素个数为0，则排序完成。
*/
#include<cstdio>
#include<iostream>
using namespace std;
int num[10]={9,24,5,2,3,1,6,8,10,7};
void sort(int n)
{
int tmp;
for(int i=0;i<n;i++)
{
tmp=num[i];
int j;
for(j=i;j>0&&tmp<num[j-1];j--)
{
num[j]=num[j-1];
}
num[j]=tmp;
}
}
int main()
{
sort(10);
for(int i=0;i<10;i++)
{
printf("%d ",num[i]);
}
return 0;
}
希尔排序：
/*
将待排序的一组元素按照一定的间隔分成若干个序列，分别进行插入排序。开始时间隔比较
大，在每一轮排序中间隔逐渐减小，直到间隔变为"1",也就是最后一次进行了简单排序
*/
#include<cstdio>
#include<iostream>
using namespace std;
int num[10]={9,24,5,2,3,1,6,8,10,7};
int incre[4]={5,3,1};
void sort(int n,int m)//m指incre中包含m个增量
{
int increment,tmp;
for(int i=0;i<m;i++)
{
increment=incre[i];
for(int j=increment;j<n;j+=increment)
{
tmp=num[j];
for(int k=j;k-increment>=0;k-=increment)
{
if(tmp<num[k-increment])num[k]=num[k-increment];
else break;
num[k-increment]=tmp;
}
}//结束一趟排序
}
}
int main()
{
sort(10,3);
for(int i=0;i<10;i++)
{
printf("%d ",num[i]);
}
return 0;
}
冒泡排序：
/*
一共进行n-1次循环，在第k次循环中，对从第一到第n-k个元素从前往后进行比较，每次比较
相邻的两个元素，如果前一个元素大于后一个元素，则两者交换位置，否则位置保持不变。
*/
#include<cstdio>
#include<iostream>
using namespace std;
int num[10]={9,24,5,2,3,1,6,8,10,7};
void sort(int n)
{
bool flag;
for(int i=n-1;i>=0;i--)
{
flag=false;
for(int j=0;j<i;j++)
{
if(num[j]>num[j+1])
{
swap(num[j],num[j+1]);
flag=true;
}
}
if(flag==false)break;
}
}
int main()
{
sort(10);
for(int i=0;i<10;i++)
{
printf("%d ",num[i]);
}
return 0;
}
快速排序：
/*
将未排序元素根据基准分为两个子序列，其中一个子序列的记录均大于基准，而另一个子序
列均小于基准，然后递归的对这两个子序列用类似的方法进行排序
*/
#include<cstdio>
#include<iostream>
using namespace std;
int num[10]={9,24,5,2,3,1,6,8,10,7};
void qsort(int low,int high)
{
int pivot=num[low];
int left=low,right=high;
if(low>=high)return;
swap(num[low],num[right]);//将基准与最后一个元素交换
while(1)
{
while(low<high&&pivot>=num[low])low++;
while(low<high&&pivot<=num[high])high--;
if(low<high)swap(num[low],num[high]);
else break;
}
swap(num[low],num[right]);//将基准换到正确的位置上
qsort(left,low-1);
qsort(low+1,right);
}
int main()
{
qsort(0,9);
for(int i=0;i<10;i++)
{
printf("%d ",num[i]);
}
return 0;
}
归并排序：
/*
将大小为n的序列看成n个长度为1的序列，接下来，两个相邻的序列两两进行归并操作，
继续归并，最后剩下一个长度为N的序列
*/
#include<cstdio>
#include<iostream>
#include<stdlib.h>
using namespace std;
int num[10]={9,24,5,2,3,1,6,8,10,7};
int tmp[10];
void merge(int start,int mid,int end)
{
int *tmp = (int *)malloc((end-start+1)*sizeof(int)); // tmp是汇总2个有序区的临时区域
int i = start; // 第1个有序区的索引
int j = mid + 1; // 第2个有序区的索引
int k = 0; // 临时区域的索引
while(i <= mid && j <= end)
{
if (num[i] <= num[j])
tmp[k++] = num[i++];
else
tmp[k++] = num[j++];
}
while(i <= mid)//剩余元素
tmp[k++] = num[i++];
while(j <= end)
tmp[k++] = num[j++];
// 将排序后的元素，全部都整合到数组a中。
for (i = 0; i < k; i++)
num[start + i] = tmp[i];
free(tmp);
}
void msort(int left,int right)
{
if(left<right)
{
msort(left,(left+right)/2);
msort((left+right)/2+1,right);
merge(left,(left+right)/2,right);
}
}
int main()
{
msort(0,9);
for(int i=0;i<10;i++)
{
printf("%d ",num[i]);
}
return 0;
}
| 排序方法 | 平均时间复杂度 | 最坏情况下时间复杂度 | 额外空间复杂度 | 稳定性 | |
| 简单选择排序 | O(N^2) | O(N^2) | O(1) | 不稳定 | |
| 直接插入排序 | O(N^2) | O(N^2) | O(1) | 稳定 | |
| 冒泡排序 | O(N^2) | O(N^2) | O(1) | 稳定 | |
| 希尔排序 | O(N^d) | O(N^2) | O(1) | 不稳定 | |
| 堆排序 | O(Nlog2N) | O(Nlog2N)O(1) | 不稳定 | ||
| 快速排序 | O(Nlog2N) | O(N^2) | O(1) | 不稳定 | |
| 归并排序 | O(Nlog2N) | O(Nlog2N) | O(N) | 稳定 | |