数据结构 第八章 排序技术

排序的基本概念 排序：给定一组记录的集合{r1, r2, ……, rn}，其相应的关键码分别为{k1, k2, ……, kn}，排序是将这些记录排列成顺序为{rs1, rs2, ……, rsn}的一个序列，使得相应的关键码满足ks1≤ks2≤……≤ksn（称为升序）或ks1≥ks2≥……≥ksn（称为降序）。 正序：待排序序列中的记录已按关键码排好序。 逆序（反序）：待排序序列中记录的排列顺序与排好序的顺序正好相反。 趟：在排序过程中，将待排序的记录序列扫描一遍称为一趟。通常，一次排序过程需要进行多趟扫描才能完成

排序算法的稳定性： 假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序算法的稳定性 对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而证明稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的。不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

算法的稳定性与算法的具体实现有关 冒泡排序是稳定的排序方法 5，3，3，4 如果规则是 A[i]>a[i+1]，则是稳定 如果规则是A[i]>=a[i+1]，则是不稳定的排序方法 快速排序原本是不稳定的排序方法， 但若待排序记录中只有一组具有相同关键码的记录，而选择的轴值恰好是这组相同关键码中的一个，此时的快速排序就是稳定的。

排序的分类-根据排序数据在内存中还是在外存中： 1、内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中 2、外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。 排序的分类-根据排序过程中所进行的基本操作分：

**基于比较：**基本操作——关键码的比较和记录的移动，其最差时间下限已经被证明为O（nlog2n）。 不基于比较：根据关键码的分布特征。比如，桶式排序，基数排序（多关键字排序） 基于比较的内排序

插入排序 交换排序 选择排序 归并排序 不基于比较的内排序 1.分配排序 2.桶式排序 3.基数排序

排序算法的性能 1.时间复杂性：基本操作。 内排序在排序过程中的基本操作： ⑴比较：关键码之间的比较； ⑵移动：记录从一个位置移动到另一个位置。 2.空间复杂性： 辅助存储空间。 辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。

排序算法的存储结构 从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。 假定1：采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。 int r[n+1]; //待排序记录存储在r[1]~r[n]，r[0]留做他用 假定2：将待排序的记录序列排序为升序序列。

插入类排序

插入排序的主要操作是插入， 其基本思想是： 每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。

插入类排序方法有以下两种： 直接插入排序 希尔排序

直接插入排序 基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。

如何构造初始的有序序列？ 解决方法： 将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。

如何查找待插入记录的插入位置? 解决方法： 在i-1个记录的有序区r[1] ~ r[i-1]中插入记录r[i]，首先顺序查找r[i]的正确插入位置，然后将r[i]插入到相应位置。

r[0]有两个作用：

进入循环之前暂存了r[i]的值，使得不致于因记录的后移而丢失r[i]的内容； 在查找插入位置的循环中充当哨兵。

void  insertSort (int  r[ ], int n){	
   for (i=2; i<=n; i++)   { 
       r[0]=r[i]; j=i-1;
       while (r[0]<r[j])       {  
           r[j+1]=r[j];	
	 j=j-1;	
        }
       r[j+1]=r[0];	
    }
}

性能分析 最好情况下（正序）： 比较次数：n-1 移动次数：2(n-1) 时间复杂度为O(n)。 最坏情况下（逆序或反序）： 时间复杂度为O(n2)。 平均情况下（随机排列）： 时间复杂度为O(n2)。

空间性能：需要一个记录的辅助空间。 直接插入排序算法是一种稳定的排序算法。 直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录个数较小的情况。 当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。

希尔排序 改进的依据： （1）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高； （2）由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。

基本思想： 将整个待排序记录分割成若干个子序列， 在子序列内分别进行直接插入排序， 待整个序列中的记录基本有序时，对全体记录进行直接插入排序。

分割待排序记录的目的?

减少待排序记录个数； 使整个序列向基本有序发展。 如何分割? 子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。

应如何分割待排序记录？ 解决方法： 将相隔某个“增量”的记录组成一个子序列。 增量应如何取？ 希尔最早提出的方法是d1=n/2，di1+1=di/2。

子序列内如何进行直接插入排序？ 解决方法： 在插入记录r[i]时，自r[i-d]起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r[0]只是暂存单元，不是哨兵。当搜索位置＜0，表示插入位置已找到。 在搜索过程中，记录后移也是跳跃d个位置。 在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。

void Shellsort(int r[],int n){
  for (d=n/2; d>=1; d=d/2){
     for (i=d+1; i<=n; i++) {
	     r[0]=r[i];           
	     j=i-d;                
	     while (j>0 && r[0]<r[j])
	     { 
          		r[j+d]=r[j]; 
	          j=j-d;          
	      }
	      r[j+d]=r[0]; 
	}
  }
}

希尔排序算法的时间性能 希尔排序算法的时间性能是所取增量的函数，而到目前为止尚未有人求得一种最好的增量序列。 研究表明，希尔排序的时间性能在O(n2)和O(nlog2n)之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n1.3 ) 。

交换排序 交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。 起泡排序 基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。 如何记载一趟排序过程中交换的多个记录？ 解决方法： 设变量exchange记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。 算法描述： if （r[j]>r[j+1]）{ r[j]←→r[j+1]； exchange=j； } 如何确定起泡排序的范围？ 解决方法： 设bound位置的记录是无序区的最后一个记录，则每趟起泡排序的范围是r[1] ~ r[bound]。 在一趟排序后，从exchange位置之后的记录一定是有序的，所以bound=exchange。 算法描述： bound=exchange; for (j=1; j<bound; j++) if （r[j]>r[j+1]）{ r[j]<==>r[j+1]； exchange=j； } 如何判别起泡排序的结束？ 解决方法： 在每一趟起泡排序之前，令exchange的初值为0，在以后的排序过程中，只要有记录交换，exchange的值就会大于0。这样，在一趟比较完毕，就可以通过exchange的值是否为0来判别是否有记录交换，从而判别整个起泡排序的结束。 算法描述： while (exchange) { 执行一趟起泡排序； }

void BubbleSort(int r[ ], int n)
{	
    exchange=n; 	
    while (exchange) 
    {
        bound=exchange; 
        exchange=0；  
        for (j=1; j<bound; j++)
            if (r[j]>r[j+1]) {
                r[j]←→r[j+1]；
	      exchange=j； 
            }
     }
 }
void BubbleSort(int r[ ], int n)
{	
    change=true; bound=n;
    while (change) 
    {
        change=false;
          
        for (j=1; j<bound; j++)
            if (r[j]>r[j+1]) {
                r[j]←→r[j+1]；
	      bound=j；
	      change=true
            }
     }
 }

起泡排序的时间性能分析

int temp;
int    exchange1,exchange2;
int bound1,bound2;
exchange1=n-1; 
exchange2=0; 
while (exchange1) {
    exchange1=0;  
    bound1=exchange1;
    bound2=exchange2;
    for (int j=bound2; j<bound1; j++) 
        if (r[j]>r[j+1]){
	temp=r[j];
	r[j]=r[j+1];
	r[j+1]=temp;
	exchange1=j; 
	}
    bound1=exchange1;    
		for ( j=bound1; j>bound2; j--) 
	    if (r[j]<r[j+1]) {
		  temp=r[j];
		  r[j]=r[j+1];
		  r[j+1]=temp;
		  exchange2=j; 
	   }
		bound2=exchange2;
	 } 

快速排序的基本思想 首先选一个轴值（即比较的基准）， 通过一趟排序将待排序记录分割成独立的两部分， 前一部分记录的关键码均小于或等于轴值， 后一部分记录的关键码均大于或等于轴值， 然后分别对这两部分重复上述方法，直到整个序列有序。