排序算法

稳定的排序：排序前后的相对顺序不改变：排序前若Ri排在Rj之前，排序之后仍然是这样。

不稳定的排序：与稳定相反。

内部排序：待排序数据存放于计算机随即存储器之中。

外部排序：待排序数据存放于外存中。

参考书目：数据结构C语言版，严蔚敏，吴伟民

定义数据结构：

#define MAXSIZE 20

typedef int KeyType;

typedef struct{

KeyType key

InfoType info;

}RedType；

typedef struct{

RedType r[MAXSIZE];

int Length;

}SqList;

排序算法介绍：

（1）直接插入排序：讲一个记录直接插入到一个已排好的有序表中

时间复杂度：o(n^2)，比较量与移动量的时间复杂度都为：o(n^2)

空间复杂度：只要一个临时存储空间

算法：

void InsertSort(SqList &L)

{

for(i=2;i<=L.length;++i)

if LT(L.r[i].key,L.r[i-1].key){

L.r[0] = L.r[i];

L.r[i] = L.r[i-1];

for(j = i-2;LT(L.r[0].key,L.r[j].key);--j)

L.r[j+1] = L.r[j];

L.r[j+1] = L.r[0];

}

}

（2）希尔排序：shell排序

先将待排序列分成若干子序列分别进行直接插入排序，待这个序列基本有序的时候，再对全体数据进行一次直接插入排序。

（3）起泡排序：

基本思想：若逆序则交换，每次沉出一个最大值或者最小值；若一趟起泡排序无交换，则排序结束。

（4）快速排序：源于起泡排序

通过一趟排序将待排序记录分成独立的两部分，其中一部分的关键字均比另一部分大，则可分别对这两部分数据使用该办法继续排序，直到有序。

（5）选择排序：

每一趟在待排序数据中选取最小（最大）的记录作为第？？个元素

每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列的第i个元素

（6）堆排序：

把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间，然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根，把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1，并通过上移使得新得到的序列仍为二叉堆，再提取新二叉堆的第一个元素到新数组。依此类推，直到提取最后一个元素，新得到的数组就是排序后的数组。

（7）归并排序：

归并:将两个有序序列归并成一个有序序列。每一次归并的复杂度：o(m+n)

归并算法：

void Merge(RedType SR[],Redtype &TR[],int i,int m,int n)

{

for(j = m+1,k=i;i <= m,j<=n;k++)

{

if(SR[i].key<SR[j].key) TR[k]=SR[i++];

else TR[k] = SR[j++];

}

if(i<=m) TR[k++] = SR[i++];

if(j<=n) TR[k++] = SR[j++];

}

2-路归并排序：将待排序列分成[n/2]组，每组两个数据（若n为奇数，则有一组数只有一个数据），两两归并，之后继续如此归并直到有序。

一趟归并的复杂度为：o(n);需要归并的次数为o(log2(n))，故归并排序的复杂度为o(nlog2(n))

（8）基数排序：

从低位到高位依次对Kj(j=d-1，d-2，…，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd，这就是"基数排序"名称的由来

各排序算法的关系：

直接插入排序————Shell排序

起泡排序——————快速排序

选择排序——————堆排序

排序算法比较：

排序算法	平均时间	最坏情况	辅助存储
简单排序	O(n^2)	O(n^2)	O(1)
快速排序	O(nlog(n))	O(n^2)	O(log(n))
归并排序	O(nlog(n))	O(nlog(n))	O(n)
堆排序	O(nlog(n))	O(nlog(n))	O(1)
基数排序	O(d(n+rd))	O(d(n+rd))	O(rd)

就平均时间性能而言，最好的是快速排序，但快速排序的最坏时间比归并和堆排序都要差。上表中的简单排序不包括希尔排序。

快速排序、堆排序、希尔排序等时间性能好的排序算法都是不稳定的。

1.稳定性比较

插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的

选择排序、希尔排序、快速排序、堆排序是不稳定的

2.时间复杂性比较

插入排序、冒泡排序、选择排序的时间复杂性为O(n2)

其它非线形排序的时间复杂性为O(nlog2n)

线形排序的时间复杂性为O(n);

3.辅助空间的比较

线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);

4.其它比较

插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。

反而在这种情况下，快速排序反而慢了。

当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。

若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。

当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序