数据结构（超详细讲解！！）第二十八节 排序

1.排序的几个基本概念

排序就是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

数据表(Data List)? ：待排序的数据对象的有限集合。

关键字(Key)：数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。

主关键字（Primary Key） ：若此关键字可以唯一地标识一个记录，则称此关键字为主关键字

次关键字（Secondary Key） ：用以识别若干记录的关键字为次关键字。

当数据元素只有一个数据项时，其关键字即为该数据项。

排序分类：

（1）增排序和减排序： ? ? ? ? ? ?

如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排序。 ?

（2）稳定排序和不稳定排序： ?? ? ? ?

假设Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri领先于Rj（即i<j）。若在排序后的序列中Ri仍领先于Rj，即那些具有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之，若Rj领先于Ri，则称所用的方法是不稳定的。

(3) 内部排序与外部排序： ? ?

在排序中，若数据表中的所有记录的排列过程都是在内存中进行的，称为内部排序。 ? ?

由于待排序的记录数量太多，在排序过程中不能同时把全部记录放在内存，需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过程，称为外部排序。 ? ?

在外部排序情况下，只有部分记录进入内存，在内存中进行内部排序，待排序完成后再交换到外部存储器中加以保存。然后再将其它待排序的记录调入内存继续排序。这一过程需要反复进行，直到全部记录排出次序为止。显然，内部排序是外部排序的基础。

区分标准：排序过程是否全部在内存进行。

2.排序算法的效率分析

时间效率 —— 排序速度（即排序所花费的全部比较次数和移动次数，一般都按平均时间复杂度进行估算；对于那些受数据表中记录的初始排列及记录数目影响较大的算法，按最好情况和最坏情况分别进行估算。 ）

空间效率 —— ?占内存辅助空间的大小（若排序算法所需的辅助空间不依赖问题的规模n，即空间复杂度是O(1) ，则称排序方法是就地排序，否则是非就地排序。）

稳 定 性 —— 若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。

3.插入排序

基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。

1.直接插入排序(Insert Sort)

基本思想：当插入第i个对象时，前面的R[1],R[2],…,R[i-1]已经排好序，此时，用R[i]的关键字与R[i-1], R[i-2],…的关键字顺序进行比较，找到插入位置即将R[i]插入，原来位置上的对象向后顺移。

直接插入排序举例：

void InsertionSort(int * pData, int n)
{   int temp;
    for(int i= 1 ;i<n;i++) 
    {      temp = pData[i];	
            for (int j = i-1 ; j >= 0 && temp < pData[j] ; j--)   
                   pData[j+1] = pData[j];
	  pData[j+1] = temp;
   }
}

带哨兵直接插入排序举例：

void InsertionSort(int * pData,int n)
{   for(int i= 2 ;i<=n;i++) 
    {      pData[0] = pData[i];	
            for (int j = i-1 ;pData[0] < pData[j] ; j--)   
                   pData[j+1] = pData[j];
	  pData[j+1] = pData[0];
   }
}

算法中引入附加记录pData[0]有两个作用： 其一是进入查找循环之前，它保存了pData[i]的副本，使得不至于因记录的后移而丢失pData[i]中的内容； 其二是在for循环“监视”下标变量j是否越界，一旦越界（即j<1），pData[0]自动控制for循环的结束，从而避免了在for循环内的每一次都要检测j是否越界（即省略了循环条件j>=1）。 ?因此，把pData[0]称为“监视哨”。

算法分析：

若初始时关键字递增有序（正序），这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。总的移动次数为2（n-1)。

若初始时关键字递减有序（反序），这是最坏情况。这时的记录比较和移动次数分别为：

空间效率： O（1）

稳 ?定 ?性：稳定

直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。

2.折半插入排序

在已形成的有序表中折半查找，并在适当位置插入，把原来位置上的元素向后顺移。

优点：比较的次数大大减少。

时间效率：虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为O(n2) 。

空间效率：O（1） 稳定性：稳定

Void  BInSort (int * pData,int n)  // 折半插入排序
{  for ( i=2；i<=n；++i )
   { pData[0] = pData [ i ]
      low=1；high=i-1；
      while (low<=high)     //  比较，折半查找插入位置
      {  m=(low+high)/2；        // 折半
         if (pData [ 0 ]< =pData [ m ])  high=m-1；
         else   low=m+1；                  // 插入点在高半区
       } // while
      for (j=i-1；j>=low；--j) pData [j+1] = pData [j]；
      pData[low] = pData[0] ；                       // 插入
    }  // for
}  // BInsertSort

算法分析：

折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。 在插入第 i 个对象时，需要经过 log2i?+1 次关键码比较，才能确定它应插入的位置。 折半插入排序是一个稳定的排序方法。

3.希尔排序 (Shell Sort)

希尔排序（Shell’s Sort）又称“缩小增量排序”（Diminishing Increment Sort）

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

例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, ?04），请写出希尔排序的具体实现过程。

算法分析：开始时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。

void ShellSort(int * pData, int n, int delta)
{
   int temp;
   for(int i= delta ;i<n; i++)  
   {  temp = pData[i];  
       for (int j = i-delta ; j >= 0 && temp < pData[j] ; j=j-delta)     
              pData[j+delta] = pData[j];
       pData[j+delta] = temp;
   }
}         

void  ShellInsert(int * pData, int n)
{ 
  for(i=0 ； i<=m-1； ++i) //m为delta数组的长度
         ShellSort(pData ，delta［i］)； 
} 

delta的取法有多种。最初 shell 提出取 delta = n/2，delta = delta/2，直到delta= 1。knuth 提出取 delta = delta/3?+1。还有人提出都取奇数为好，也有人提出各 delta 互质为好。 对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。

想要弄清排序码比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。 Knuth利用大量实验统计资料得出 : 当 n 很大时，排序码平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。

空间效率：O（1）——因为仅占用1个缓冲单元

希尔排序是一种不稳定的排序方法。

原理：关键字相同的两个对象，在排序过程中，由于所处的分组不同，会发生位置交换。

4.交换排序

基本原理：两两比较待排序的对象的关键字，如果发生逆序，则交换之，直到全部对象都排好序为止。

1.冒泡排序

基本思想： 首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两记录交换，然后比较第二个记录和第三个记录的关键字，依次类推，直到第n-1个记录和第n个记录的关键字比较完毕为止。上述过程称做第一趟冒泡排序，其结果是使得关键字最大的记录被安置到最后一个记录的位置上。 然后进行第二趟冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。 依次类推，最后只剩关键字最小的记录被安置到第1个记录的位置上。 对于n个关键字，最多需要n-1次冒泡处理。

void BubbleSorta(int a[],int n)
{  int temp;
    int flag =1 ;           /*表示冒泡过程是否存在交换的标志*/
    while (flag)
    {	int j = n-1;			
           	flag = 0; 			
  	for (int i=1; i<=j; i++)
  	{  if(a[i-1]>a[i])
	   {  temp = a[i]; a[i] = a[i-1];a[i-1] = temp; flag =1;  }
                }
	 j--;
    }
}

时间复杂度：

考虑关键字的比较次数和对象移动次数

1、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排序，关键字的比较次数为n-1，没有记录移动。

2、若初始状态是反序的，则需要进行n-1趟扫描，每趟扫描要进行n-i次关键字的比较，且每次需要移动记录三次，因此，最大比较次数和移动次数分别为

最好T(n)=O(n),最坏T(n)=O(n2),平均T(n)=O(n2)

冒泡排序算法是稳定的。

空间效率：O（1）

2.快速排序 (Quick Sort)

基本思想：任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准, ? 按照该对象的排序码大小, ? ?将整个对象序列划分为左右两个子序列： 左侧子序列中所有对象的排序码都小于基准对象的排序码， 右侧子序列中所有对象的排序码都大于或等于基准对象的排序码。 基准对象则排在这两个子序列中间。 然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止

前提：顺序存储结构

1、快速排序通过对序列不断的划分，把原始序列以划分元素为界形成两个子序列，再对子序列重复划分过程，这显然是一个递归的过程，递归的终止条件是子序列中只含有一个元素。

2、在每次划分过程中，需要设置前后2个指针，这两个指针依次往序列中间位置移动，当指针重合时，结束本次划分。

3、划分元素(基准）的选择，将影响算法的效率。

int partition(int a[], int i, int j)
{  　　 int temp = a[i]; 		
   	while (i<j)   
   	{　while(a[j] >= temp && i < j) j--;
	       if(i < j)     a[i++] = a[j];      
	      while(a[i]<=temp && i < j) i++;
　　　　     if(i<j)   a[j--]=a[i];
	}
　　　 a[i]=temp; 	
　　　return i;  	
}

void QuickSort(int a[], int i, int j)
{  　int k;
　　if(i<j)  				 
　　{    　　	k = Partition(a, i, j); 	
		QuickSort(a, i, k-1);
　　　　　　    QuickSort(a, k+1, j);	
　　}
} 
   

算法分析：

如果每次划分对一个对象定位后, 该对象的左侧子序列与右侧子序列的长度相同, 则下 一步将是对两个长度减半的子序列进行排序, 这是最理想的情况。 在最坏的情况, 即待排序对象序列已经按其排序码从小到大排好序的情况下

时间复杂度是O(n2)

快速排序的平均时间复杂度为： O(n log2n)

平均时间复杂度是O(nlog2n)。

实验结果表明: 就平均计算时间而言, 快速排序是所有内排序方法中最好的一个。 对于 n 较大的平均情况而言, 快速排序是“快速”的, 但是当 n 很小时, 这种排序方法往往比其它简单排序方法还要慢。

快速排序是一种不稳定的排序方法。

空间效率：O（log2n）—因为算法的递归性，要用到栈空间

常见的渐进时间复杂度随问题规模n的扩大而增长且增长的速度是不同的，其大小次序如下： ? ? ? ? ? ? O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)

5.选择排序

基本原理: 从n个关键字序列中找到一个最小值，并把它放到序列首端，再从剩下的n-1个关键字中选择最小值，仍然放到这n-1个关键字的序列首端，以此类推。

1.简单选择排序

基本思想：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的纪录，并和第i（1 <=? i <=?n ）个记录交换。

void QuickSelectionSort(int a[],int n)
{       int min;					
         int temp;
         for (int i = 0;i<n-1;i++) 	
         {   min=i; 					    	   
             for (int j = i+1;j<n;j++)  
                    if(a[j] < a[min])  min=j; 
             temp = a[i]; a[i] = a[min]; 
             a[min] = temp; 
         }
}

时间复杂度:

1、无论初始状态如何，在第i 趟排序中选择最小关键字的记录，需做n-i次比较，因此总的比较次数为：

2. 当文件为正序时，移动次数为0，文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。

平均T(n)=O(n2)

直接选择排序是不稳定的排序方法。

空间效率：O（1）——交换时用到一个暂存单元

2.堆排序

堆排序(Heap Sort)借助于完全二叉树结构进行排序，是一种树型选择排序。 ? ? ? ?

在直接选择排序时，为从n个关键字中选出最小值，需要进行n-1次比较，然后又在剩下的n-1个关键字中选出次最小值，需要n-2次比较。在n-2次的比较中可能有许多比较在前面的n-1次比较中已经做过，因此存在多次重复比较，降低了算法的效率。 ? ? ? ?

堆排序方法是由J. Williams和Floyd提出的一种改进方法，它在选择当前最小关键字记录的同时，还保存了本次排序过程所产生的比较信息。

堆的定义

?n个元素序列{k1，k2，…，kn }，当且仅当满足如下性质称为堆。 ? ? ? ?

(1)这些元素是一棵完全二叉树中的结点，且对于i=1， 2，…, n， ki是该完全二叉树中编号为i的结点； ? ? ?

(2) ki≥k2i （或ki≤k2i ?） ? ? ? ? (1≤i≤n /2?) ? ? ?

(3) ki≥k2i+1(或 ki≤k2i+l ) ? ? ? ? ? ? ?(1≤i≤n /2?) ? ? ?

从堆的定义可以看出，堆是一棵完全二叉树，其中每一个非终端结点的元素均大于等于（或小于等于）其左、右孩子结点的元素值。

根据堆的定义，可以推出堆的两个性质：

1.堆的根结点是堆中元素值最大（或最小）的结点，称为堆顶元素。

2.从根结点到每个叶结点的路径上，元素的排序序列都是递减（或递增）有序的。

?堆排序的基本思想是：对一组待排序记录，首先把它们的关键字按堆定义排列成一个序列（称为初始建堆），堆顶元素为最大关键字的记录，将堆顶元素输出；然后对剩余的记录再建堆（调整堆），得到次最大关键字记录；如此反复进行，直到全部记录有序为止，这个过程称为堆排序。

1、构建堆的过程可以分为自底到顶（图7-11(a)-(e)）和自顶到底(图7-11(e)-(g))两个过程。调整完后数据的最大值被交换到了根结点的位置。

2、由于树的结点按照层次存储在数组中（假设为数组a，且含有n个元素），且在c语言中数组下标从0开始，根据完全二叉树的性质，对于结点a[i]，其对应的左右孩子为a[2*i+1]和a[2*i+2]。由于自底到顶的过程需要从二叉树中第一个非叶结点开始往前开始调整，而该结点恰为二叉树最后一个结点的父结点，所以该结点的下标应为

3、自底到顶的过程，从元素a[(n-2)/2]开始调整，按照逆序，直到调整到a[0]为止。

4、再来看自顶到底的过程，该过程可以描述为找到根结点的左右孩子的较大值，如果根结点比该结点小，则交换两个结点数据，如图7-10（f）。如果“3”还含有子结点，则需要以“3”为根继续进行调整，当往下交换到叶结点时，调整结束。而判断某个结点是否含有孩子结点的方法是检查该结点左孩子下标（2*i+1）与右孩子下标（2*i+2）是否大于n-1。

5、根据自底到顶与自顶到底调整的特点，构建堆的过程可以描述为分别以结点“4”、“8”、“1”、“3”为根结点，顺次进行自顶到底的调整。所以在实现构建堆的算法时，核心是实现进行一个以任意结点为根，进行自顶到底调整的函数。

void BuildDown(int a[], int n, int rootIndex)
{    int root = a[rootIndex];		
     int childIndex = LeftChild(rootIndex);	 	
     while(childIndex < n ) 	 	  	
     {    if (childIndex != n-1 && a[childIndex+1]>a[childIndex])  
	         childIndex++;	
          if (root < a[childIndex])
         {    a[rootIndex] = a[childIndex]; 	/*较大数据往上移动*/
               rootIndex = childIndex; 		/*设定新的根结点下标*/
	 childIndex = LeftChild(rootIndex);	/*设定新的左孩子下标*/
          }
          else
              break; 
      }
      a[rootIndex] = root;	/*将根结点置于目标位置*/
 }/*以某结点为根，进行自顶到底的调整。*/

堆排序：

对于已建好的堆，可以采用下面两个步骤进行排序： ? ? ? ?

?(1) 输出堆顶元素：将堆顶元素（第一个记录）与当前堆的最后一个记录对调。 ? ? ? ?

?(2) 调整堆：将对调之后的新完全二叉树调整为堆。 ? ? ? ?

不断地输出堆顶元素，又不断地把剩余的元素建成新堆，直到所有的记录都变成堆顶元素输出。 堆排序的算法描述如下：

void HeapSort(int a[], int n)          /*堆排序*/
{    int temp;
      for (int rootIndex = (n-2)/2 ; rootIndex >= 0 ; rootIndex-- ) 
              BuildDown(a, n, rootIndex);
      for (int i = n-1;i>0;i--)
     {   temp = a[0]; a[0] = a[i]; a[i] = temp; 
	 	BuildDown(a,i,0);	
      }
}

由于堆是一种完全二叉树的结构，n个结点的完全二叉树高度为 ，所以调整函数的复杂度为，又由于对这个调整函数的调用n次，所以堆排序的时间复杂度为?。

稳定性：堆排序是不稳定排序。

所需的空间为O(1)--用到一个临时变量temp

6.归并排序

基本原理，通过对若干个有序结点序列的归并来实现排序。

所谓归并是指将若干个已排好序的部分合并成一个有序的部分。

归并排序基本思想是：将待排序列L.R[0]到L.R[n-1]看成n个长度为1的有序子序列，把这些子序列两两归并，便得到n/2个有序的子序列。然后再把这n/2个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列。上述每次的归并操作，都是将两个子序列归并为一个子序列，这就是“二路归并”，类似地还可以有“三路归并”或“多路归并”。

两路归并的基本思想：

设有两个有序表A和B，对象个数分别为al和bl，变量i和j分别是两表的当前指针。设表C是归并后的新有序表，变量k是它的当前指针。i和j对A和B遍历时，依次将关键字小的对象放到C中，当A或B遍历结束时，将另一个表的剩余部分照抄到新表中。

void Merge(int a[], int s1, int e1, int s2, int e2, int b[])
{/*分组a[s1]-a[e1]与分组a[s2]-a[e2]合并，合并借用辅助数组b，合并完后，分组a[s1]-a[e2]有序*/
	int k = s1 ;  int i = s1;
  	while ((s1<=e1) && (s2<=e2))    /*当2分组都不为空时*/
  	{	if(a[s1] <= a[s2]) 	b[k++] = a[s1++];
		else			b[k++] = a[s2++];         }
           	while (s1 <= e1) b[k++] = a[s1++]; 	
                 /* 若s1分组有剩余数据，则直接移动到辅助数组*/
  	while (s2 <= e2) b[k++] = a[s2++];  	
                 /* 若s2分组有剩余数据，则直接移动到辅助数组*/ 
            k--;
 	 while (k >= i)  { a[k] = b[k]; k--; }	/*把数据拷贝到原序列*/
}
/*对数组a中的数据a[i]-a[j]进行归并排序，排序用到辅助空间b*/
void MergeSort(int a[], int i, int j, int b[])
{
  int k ;
  if (i<j) 	/*当分组内数据个数大于1时，才需要排序*/
  {
              k=(i+j)/2;  			/*找到分组中点*/
	 MergeSort(a, i, k, b); 	/*对左半段进行归并排序*/
	 MergeSort(a,  k+1, j, b); 	/*对右半段进行归并排序*/
	 Merge(a, i, k, k+1, j, b);  	/*合并左右两段*/
  }
}

算法复杂性分析：

归并排序在第i 趟归并后，有序子序列长度为2i，因此, 对于具有n个记录的序列来说，必须做log2n趟归并，每趟归并所花的时间为O(n)。所以，归并排序算法的时间复杂度为O(nlog2n)，辅助数组所需的空间为O(n)。

归并排序是稳定的排序方法。

【例】初始序列为｛23，56，42，37，15，84，72，27，18｝用归并排序法排序。

【解】排序后的结果为：｛15，18，23，27，37，42，56，72，84｝，整个归并过程如下所示。

7.基数排序

基数排序是和前面所述各类排序方法完全不同的一种排序方法。基数排序(Radix Sort)是一种借助于多关键字排序的思想对单逻辑关键字进行排序的方法，即先将关键字分解成若干部分，然后通过对各部分关键字的分别排序，最终完成对全部记录的排序。

例：初始关键字： 25 ?37 ?98 ?12 ?50 ?24 ? 89 ? 65 ? 42 ? 17

基数排序的执行时间取决于记录关键字Ki的最大位数k。基数排序算法对待排序列中的记录共进行k趟分配和收集过程。每趟排序，分配时间为O(n)，收集时间为O(m)，因此一趟基数排序的时间为O(n+m)。经过k趟排序的总时间为O(k*(n+m))。一般情况下，当n很大，k较小时，此算法很有效。

?基数排序需要额外设置存放m个队列指针的数组，因此空间复杂度为O(n+m)。 ? 从排序的稳定性看，基数排序是一种稳定的排序方法。

各种内部排序方法的比较

对基本有序的情况，可选用直接插入、堆排序、冒泡排序、归并排序等方法； ? ? ?

在基本无序的情况下，最好选用快速排序、希尔排序。