[数据结构与算法]常用简单排序

前言：排序所用的参数及函数形式如下：

void  X_Sort ( ElementType  A[ ],  int N );
typedef int ElementType;

为了简单起见，假设是整数数组

1.插入排序（Insertion Sort）

void InsertionSort ( ElementType A[ ], int N ) 

N个元素需要N-1趟排序，从P=1到P=N-1

void InsertionSort(ElementType A[],int N){
    int p,i,tmp;
    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^2)

最好情形：顺序，O(N);? ? ? ? ?最坏情形：逆序,O(N^2)

2.希尔排序（Shell Sort）

通过比较相邻相距一定间隔的元素来工作，各趟所用的距离随算法的进行而减少

过程：1.定义增量序列(increment sequence) h1<h2<h3....<ht(h1=1)?

2.对于k=t,t-1,t-2...1,进行hk-sort，注意一个hk-sorted file still remains hk-sorted after hk-1 sorted

序列选择：

一种流行（但是不好）的选择是Shell建议的序列：ht=[N/2],hk-1=[hk/2]

void Shellsort(ElementType A[],int N){
int i,j,tmp,increment;
for (increment=N/2;increment>0;increment/=2){
    for (i=increment;i<N;i++){/*对于每个increment都是insertion sort*/
        tmp=A[i];
        for(j=i;j>increment&&A[j-increment]>tmp;j-=increment)
            A[j]=A[j-increment];
        A[j]=tmp;
}
}
}

?使用希尔排序的最坏运行情况是O(N^2)

考虑另一种增量Hibbard增量，形如1，3，5，，，，2^k-1

虽然和Shell增量几乎相同，但这些增量间没有公因子

使用Hibbard增量的希尔排序最坏运行时间是O(N^1.5)

Tavg – Hibbard ( N ) = O ( N^5/4 )

3.堆排序（Heap sort）

优先队列可以用于花费O(NlogN)的时间进行排序，基于该想法进行的排序叫做堆排序

注意：使用堆时下标从1开始(sentinel在0处)，使用堆排序下标从0开始

算法一：

T（N）=O（NlogN）

Algorithm 1:
{
BulidHeap(H); /*O(N)*/
for (i=0;i<N;i++)
tmp[i]=DeleteMin(H); /*O(logN)*/
for(i=0;i<N;i++)
H[i]=tmp[i]; /*O(1)*/
}

由于tmp数组的使用，双倍空间花销

算法二：

避免使用第二个数组，我们将每次deletemin的元素放到堆的最后（由于每次deletemin之后堆都缩小了1所以正好可以放置最后一个元素）

void percdown(ElementType A[ ], int i,int N){
int j,tmp;
tmp=A[i];
for (j=0;j*2<N-1;j=child){
child=j*2+1; //如果从1开始child=2*i
if (child!=N-1&&A[child]>A[child+1])
child++;
if (tmp>A[child])
A[j]=A[child];
else break;
}
A[j]=tmp;
}

void Heapsort( ElementType A[ ], int N ) {
int i;
for (i=N/2-1;i>0;i--) //build heap
percdown(A,i,N);
for (i=N-1;i>0;i--){
swap(&A[i],&A[0]);
percdown(A,0,i); //模仿deletemin操作
}
}

对N个不同项的随机排列进行堆排序的平均比较次数为2N log N -?O( N log log N )

4.归并排序（Mergesort）

小学期的程设题就有用归并排序和快排的题，记得当时自己和警员在b站上搜的视频一行一行看人家写代码学的（当时半个学期没碰代码了突然让我写这种东西简直就是折磨），当时只觉得递归真难理解，现在再看看觉得好多了，果然有些东西提前接触一下还是有好处的。

算法的基本操作是合并两个已经排序的表，合并部分(Merge)需要自己写具体操作，排序部分(Msort)用递归实现，Mergesort作为Msort的驱动程序。注意归并排序需要一个额外的数组

代码如下

void Merge(ElementType A[],ElementType tmparray[],int lpos,int rpos,int rightend){
int i,leftend,tmppos;
leftend=rpos-1; i=lpos;
tmppos=lpos; //tmparray的下标
while (lpos<=leftend&&rpos<=rightend){ //main loop
    if(A[lpos]<=A[rpos])
        tmparray[tmppos++]=A[lpos++];
    else tmparray[tmppos++]=A[rpos++];
}
while(lpos<=leftend){
tmparray[tmppos++]=A[lpos++];
}
while(rpos<=rightend){
tmparray[tmppos++]=A[rpos++];
}
for(;i<=rightend;i++)
A[i]=tmparray[i];
}

void Msort(ElementType A[ ], ElementType tmparray[ ], int Left, int Right){
int center=(left+right)/2;
Msort(A,tmparray,left,center);
Msort(A,tmparray,center+1,right);
Merge(A,tmparray,left,center+1,right);
}

void Mergesort(ElementType A[ ], int N){
ElementType *tmparray;
tmparray=malloc(sizeof(ElementType)*N); 
/*在这里开数组而不在Mort里面开数组可以减少很多不必要的空间花销*/
if (tmparray!=NULL){
Msort (A,tmparray,0,N-1);
free(tmparray);
}
else FatalError( "No space for tmp array!!!" );
}

每个merge只花费O(N)的时间

总的来说以O(NlogN)的时间运行

归并排序需要线性的额外内存，并且复制数组是缓慢的。它很少用于内部排序，但对于外部排序非常有用

5.快速排序（Quicksort）

快速排序是目前实践中已知的最快的排序算法，它的平均运行时间是O(NlogN)，最坏运行时间是O（N^2）

重要的是枢纽元的选取和分割的策略

这里我们枢纽元采用三数中值分割法

void swap(ElementType *a,ElementType *a){
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}

ElementType
Median3(ElementType A[],int left,int right){
int center=(left+right)/2;
if (A[left]>A[center])
swap(&A[left],&A[right]);
if (A[left]>A[right])
swap(&A[left],%A[right]);
if (A[center]>A[right])
swap(&A[center],&A[right]);
//A[left]<=A[center]<=A[right]
swap(&A[center],&A[right-1]);
return A[right-1];
}

分割，是算法的核心。这里由于枢纽元的设定，我们只需要从left+1和right-2开始进行排序即可，下面是排序算法的核心，包括分割和递归调用

void Qsort(ElementType A[ ], int Left, int Right){
int pivot,i,j;
if(left+cutoff<=right){
pivot=Median3(A,left,right);
i=left;j=right-1;
for(;;){
while(A[++i]<pivot){}
while(A[--j]>pivot){}
if(i<j) swap(&A[i],&A[j]);
else break;
}
swap(&A[i],&A[right-1]);
Qsort(A,left,i-1);
Qsort(A,i+1,right);
}
else
    InsertionSort(A+left,right-left+1);
}

Small Array：对于很小的数组(N<=20)，快速排序不如插入排序好。而由于快排是递归的，这种小数组的排序情形经常发生，因此我们经常在快排中需要先判断数组大小，对于较小的数组使用插入排序。而我们此前使用统一接口的好处也体现出来，便于直接移植。

另外别忘了驱动程序：

void Quicksort( ElementType A[ ], int N ){
	Qsort(A,0,N-1);
}

算法分析：

最坏情形T（N）=（N^2)

平均情形T（N）=（NlogN）

6.普遍下界

任何只通过比较排序的算法在最坏情况下的计算时间必须为Ω(NlogN)