简单排序
概述
void X_Sort(ElementType A[], int N)
//X表示排序方法的名字 A[]是输入的数组 N是元素个数- 简单起见，默认从小到大的整数排序
- N是正整数，排序数的个数
- 只讨论基于比较的排序
- 只讨论内部排序，所有排序是在内存里一次性完成的
- 稳定性：任意两个相等数据排序前后相对位置不变
- 没有一种排序是任何情况下都表现好的
冒泡排序
从上到下，相邻两个元素根据大小关系交换位置，第一次排序后最大的数会落到最底层，然后对于n-1个数继续重复上述过程
void Bubble_Sort(ElementType A[],int N)
{
for ( R=N-1; P>=0; P--){
flag = 0;
for(i=0; i<P; i++){
if(A[i]>A[i+1]){
Swap(A[i],A[i+1]);
flag = 1;
}
}
if ( flag == 0 ) break;
}
}- 最好情况O(N)
- 最坏情况O(N^2)
- 稳定
插入排序
void Insertion_Sort(ElementType A[],int N)
{
for(p=1;p<N;p++){
Tmp=A[p];
for(i=p;i>0 && A[i-1]>Tmp;i--)
A[i] = A[i-1];
A[i] = Tmp;
}
}- 最好情况O(n)
- 最坏情况O(N^2)
- 稳定性
时间复杂度下界
- 逆序对
- 交换两个相邻元素正好消去一个逆序对
- 插入排序 T(N,I)=O(N+I) I表示逆序对；如果序列基本有序，则插入排序简单且高效
- 定理：任意N个不同元素组成的序列平均有N(N-1)/4个逆序对
- 定理：任何以交换相邻两元素来排序的算法，其平均时间复杂度为Ω(N^2)
- 这意味着想要提高效率，必须每次消去不止一个逆序对
希尔排序
思想
- 5-间隔排序
- 然后在5-间隔排序的基础上进行3-间隔排序
- 最后做插入排序
- 定义一个增量序列，对每个增量进行增量-间隔排序
- 三间隔有序序列还保持了五间隔的性质
希尔增量序列
不停的除二，向下取整
void Shell_sort(ElementType A[], int N)
{
for ( D-N/2; D>0; D/=2){ //希尔增量序列
for（P=D; P<N; P++）{ //插入排序
Tmp = A[P];
for(i=p;i>=D && A[i-D]>Tmp;i-=D)
A[i]=A[i-D];
A[i] = Tmp;
}
}
}seita(N^2)
由于增量元素不互质，则小增量可能根本不起任何作用
更多增量序列
- Hibbard增量序列 最坏情况seita(N^3/2)
- Sedgewick增量序列
堆排序
选择排序
扫描数组，将最小元换到最后的位置
最坏情况下换n-1次，但是扫描需要的时间很久，时间复杂度为seita（N^2）
接下来的问题就在于如何找到最小元
算法1
实际上堆排序就是对选择排序的一个改进，在如何找到最小元这个位置改变
void Heap_Sort(ElementType A[],int N)
{
BuildHeap(A);
for ( i=0;i<N;i++ )
TmpA[i] = DeleteMin(A);
for ( i=0;i<N;i++)
A[i] = TmpA[i];
}时间复杂度为NlogN，但是需要额外的N的空间
算法2
建立一个最大堆，然后把根节点换到当前最后的位置，最后位置往前移动1，循环上述过程
平均比较次数 2NlogN-O（NloglogN）
实际上其实不如Sedgewick增量序列的希尔序列
归并排序
有序子列归并
时间复杂度为O(N)
递归算法
- 分而治之 O(NlogN)
- 稳定算法
非递归算法
在外排序非常有用
转载：https://blog.csdn.net/five_zzxxdd/article/details/105917055
查看评论