第九章排序

排序：将一组杂乱无章的数据按一定的规律顺次排列起来。
数据表(datalist): 它是待排序数据元素的有限集合。

排序的时间开销: 是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。

排序算法的稳定性: 如果在元素序列中有两个元素r[i]和r[j],
它们的关键码 k[i] == k[j] , 且在排序之前, 元素r[i]排在r[j]前面。
如果在排序之后, 元素r[i]仍在元素r[j]的前面, 则称这个排序方法是稳定的, 否则是不稳定的。

算法执行时所需的附加存储: 评价算法好坏的另一标准

排序算法的存储结构

从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链式存储结构存储。

假定1：采用顺序存储结构。

1 2	int r[n+1]; //待排序记录存储在r[1]~r[n]，r[0]留做他用

假定2：将待排序的记录序列排序为升序序列。

待排序数据表的类定义
#include <iostream.h>
const int  DefaultSize = 100;
template <class T>
class Element {			//数据表元素定义
public:
    T  key;				//排序码
   // field otherdata;			//其他数据成员
    Element<T>& operator = (Element<T>& x) {
        key = x.key;  otherdata = x.otherdata;
        return this;
    }
bool operator == (Element<T>& x) 
        { return key == x.key; }	//判*this与x相等
    bool operator <= (Element<T>& x)
        { return key <= x.key; }	//判*this小于或等于x
    bool operator >= (Element<T>& x)
        { return key >= x.key; }	//判*this大于或等于x bool operator > (Element<T>& x)
        { return key > x.key; }	//判*this大于x
    bool operator < (Element<T>& x)
        { return key < x.key; }	//判*this小于x
};
template <class T>
class dataList {			//数据表类定义
private:
    Element <T>* Vector;		//存储排序元素的向量
    int maxSize; 			//向量中最大元素个数
    int currentSize; 			//当前元素个数
public:
    datalist (int maxSz = DefaultSize) :     //构造函数
        maxSize(maxSz), currentSize(0) 
        { Vector = new Element<T>[maxSize]; }
    int Length() { return currentSize; }	    //取表长度
    void Swap (Element<T>& x, Element<T>& y)
        { Element<T> temp = x;  x = y;  y = temp; }
    Element<T>& operator [](int i) 	//取第i个元素
        { return Vector[i]; } 		
    int Partition (const int low, const int high);
							//快速排序划分
};

排序方法分类

内部排序

策略不同：

插入排序（希尔排序）
交换排序（冒泡，快速排序）
选择排序（堆排序）
归并排序（二路归并）
分配排序（基数排序）

工作量不同：

简单的排序方法O(n2)
先进的排序方法O(nlogn)
基数排序O( d(n+radix ) )

内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

插入排序 (Insert Sorting)

基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上, 直到元素全部插入为止。

5种插入排序方法：
(1) 直接插入排序;
(2) 折半插入排序;
(3) 2-路插入排序;
(4) 表插入排序;
(5) 希尔排序

直接插入排序 (Insert Sort)

基本思想是 : 当插入第i (i≥1) 个元素时，前面的V[0], V[1], …, V[i-1]已经排好序。这时，用V[i]的排序码与V[i-1], V[i-2], …的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移。

关键问题(1)如何构造初始的有序序列？

解决方法：
将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。所以，大循环进行n-1次插入

关键问题(2)如何查找待插入记录的插入位置?

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

//直接插入排序的算法
void InsertSort (dataList<T>& L, int left, int right) {
//依次将元素L.Vector[i]按其排序码插入到有序表
//L.Vector[left],…,L.Vector[i-1]中,使得
//L.Vector[left]到L.Vector[i]有序。
    Element<T> temp;  int i, j;
    for (i = left+1; i <= right; i++)
        if (L[i] < L[i-1]) {
		temp = L[i];  j = i-1;	
 		do {  L[j+1] = L[j];  j--; } 
		while (j >= left && temp < L[j]);
		L[j+1] = temp;  
        }   };

算法分析
设待排序元素个数为currentSize = n, 则该算法的主程序执行n-1趟。
排序码比较次数和元素移动次数与元素排序码的初始排列有关。

最好情况下，排序前元素已按排序码从小到大有序，每趟只需与前面有序元素序列的最后一个元素比较1次，总的排序码比较次数为 n-1, 元素移动次数为0。
最坏情况下, 第 i 趟时第 i 个元素必须与前面 i 个元素都做排序码比较, 并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和元素移动次数RMN分别为

KCN=n^2-2 RMN=n^2-2

注意到，在插入第 i（i＞1）个记录时，前面的 i-1 个记录已经排好序，则在寻找插入位置时，可以用折半（二分）查找来代替顺序查找，从而减少比较次数。

平均情况下排序的时间复杂度为 o(n2)。直接插入排序是一种稳定的排序方法。

折半插入排序 (Binary Insertsort)

基本思想是 : 设在顺序表中有一个元素序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的元素。在插入V[i] 时, 利用折半搜索法寻找V[i] 的插入位置

折半插入排序-关键之处：插入位置

if (temp < L[middle])	  //插入值小于中点值

 high = middle-1;	  //向左缩小区间

else low = middle+1

//折半插入排序的算法
#include "dataList.h"
template <class T> 
void BinaryInsertSort (dataList<T>& L, 
       const int left, const int right) {
//利用折半搜索, 在L.Vector[left]到L.Vector[i-1]中
//查找L.Vector[i]应插入的位置, 再进行插入。
    Element<T> temp;  
    int i, low, high, middle, k;
    for (i = left+1; i <= right; i++) {
     if (L[i] < L[i-1]) {
     temp = L[i];  low = left;  high = i-1; 
     while (low <= high) {	//折半搜索插入位置
    middle = (low+high)/2;	//取中点
if (temp < L[middle])	  //插入值小于中点值
                high = middle-1;	  //向左缩小区间
            else low = middle+1;	  //否则, 向右缩小区间
        }
        for (k = i-1; k >= low; k--) L[k+1] = L[k];
	                                          //成块移动,空出插入位置
	    L[low] = temp;	     //插入
    }
};

算法分析
折半搜索比顺序搜索快, 所以折半插入排序就平均性能来说比直接插入排序要快。

在插入第 i 个元素时，需要经过 [log(2) i] +1 次排序码比较, 才能确定它应插入的位置。因此，将 n 个元素(为推导方便, 设为 n=2k ) 用折半插入排序所进行的排序码比较次数为：n*log(2) n。

折半插入排序是一个稳定的排序方法。

折半插入排序的元素移动次数与直接插入排序相同，依赖于元素的初始排列

归并排序 (Merge Sort)

归并，是将两个或两个以上的有序表合并成一个新的有序表。
元素序列L1中有两个有序表Vector[left..mid]和Vector[mid+1..right]。它们可归并成一个有序表, 存于另一元素序列L2的Vector[left..right] 中。这种方法称为两路归并 (2-way merging)。
变量 i 和 j 分别是表Vector[left..mid]和Vector [mid+1..right]的检测指针。k 是存放指针。当 i 和 j 都在两个表的表长内变化时, 根据对应项的排序码的大小, 依次把排序码小的元素排放到新表 k 所指位置中；当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表中。

迭代的归并排序算法

迭代的归并排序算法就是利用两路归并过程进行排序。

其基本思想是：
设初始元素序列有 n 个元素，首先把它看成是 n 个长度为 1 的有序子序列（归并项），做两两归并，得到 [n/2] 个长度为 2 的归并项（最后一个归并项的长度为1）；再做两两归并，得到 [n/4] 个长度为 4 的归并项（最后一个归并项长度可以短些）…，如此重复，最后得到一个长度为 n 的有序序列。

两路归并算法

#include "dataList.h"
template <class T>
void merge (dataList<T>& L1, dataList<T>& L2,
            const int left, const int mid, const int right) {
//L1.Vector[left..mid]与L1.Vector[mid+1..right]是两
//个有序表, 将这两个有序表归并成一个有序表
//L2.Vector[left..right]
    int k, i, j; 
    i = left;  j = mid+1;  k = left;
		//s1, s2是检测指针, t是存放指针   
 while (i <= mid && j <= right)	   //两两比较
        if (L1[i] <= L1[j]) 
            L2[k++] = L1[i++];
        else 
            L2[k++] = L1[j++];
    while (i <= mid) L2[k++] = L1[i++];
		//若第一个表未检测完,复制
    while (j <= right) L2[k++] = L1[j++];
		//若第二个表未检测完,复制
};

一趟归并排序的算法

设L1.Vector[0..n-1]中 n 个记录已经分为一些长度为 len 的归并项，将这些归并项两两归并成长度为2len的归并项, 结果放到L2[ ]中。
如果n不是2len的整数倍，则一趟归并到最后，可能遇到两种情形：
剩下一个长度为len的归并项和另一个长度不足len的归并项, 可用merge算法将它们归并成一个长度小于 2len 的归并项。
只剩下一个归并项，其长度小于或等于 len, 将它直接复制到结果表中。

template <class T>
void MergePass (dataList<T>& L1, datalist<T>& L2, 
       const int len) {
    int i = 0, j, n = L1.Length();
    while (i+2*len <= n-1) {
         merge (L1, L2, i, i+len-1, i+2*len-1);
         i += 2 * len;                //循环两两归并
    }
    if (i+len <= n-1)
        merge (L1, L2, i, i+len-1, n-1);
    else for (j = i; j <= n-1; j++) L2[j] = L1[j];
};
//(两路)归并排序的主算法
template <class T> 
void MergeSort (dataList<T>& L) {
//按元素排序码非递减的顺序对表L中元素排序
    int n = L.Length();
    dataList<T> & tempList (n);		//创建临时表
    int len = 1;
    while (len < n) {
        MergePass (L, tempList, len);   len *= 2;	
	    MergePass (tempList, L, len);   len *= 2;
    }
};

在迭代的归并排序算法中, 函数MergePass()做一趟两路归并排序, 要调用merge()函数 O(n/len) 次, 函数MergeSort()调用MergePass()正好[log（2）n]次，而每次merge()要执行比较O(len)次, 所以算法总的时间复杂度为O(n*log (2) n)。
归并排序占用附加存储较多, 需要另外一个与原待排序元素数组同样大小的辅助数组。这是这个算法的缺点。
归并排序是一个稳定的排序方法。

递归归并(merge)排序

基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

void MergeSort(Type a[], int left, int right)
   {
      if (left<right) {//至少有2个元素
      int i=(left+right)/2;  //取中点
      mergeSort(a, left, i);
      mergeSort(a, i+1, right);
      merge(a, b, left, i, right);  //合并到数组b
}
   }

算法如下

   temlplate  <class type>
   void MergeSort(Type a[], int left, int right)
  {   if (1eft < right)  //至少有2个元素
       int i = (left + right ) /2; //取中点
       MergeSort(a, 1eft, i)；
       MergeSort(a, i+1, right)；
       Merge(a, b, 1eft, i, right)；//从a合并到数组b
} }    

//MergeSort(a, i+1, right)
template<class T>
void merge(T C[], T d[] ,int l, int m , int r)
{//把c[l:m],c[m+1,r]归并到d[l,r]
    int: i=l,  //第—段的游标
           j=m+1, //第二段的游标
           k=l;     //结果的游标
  //只要段中存在i和j,则不断进行归并
 while ((i<=m)&&(j<=r))
    if c[i]<=c[j]   d[k++]=C[i++]：
    else d[k++]=C[j++]：
 //考虑余下的部分
 if (i>m)  for (int q=j; q<=r;q++)
                   d[k++]=c[q]；
 else for(int q=i ;q<=m；q++)
            d[k++]=c[q]；}

T(n)=a*(nlog n)

递归的链表归并排序

与快速排序类似，归并排序也可以利用划分为子序列的方法递归实现。
算法的思路是：

首先把整个待排序序列划分为两个长度大致相等的部分，分别称之为左子表和右子表。对这些子表分别递归地进行排序，然后再把排好序的两个子表进行归并。
图示：待排序元素序列的排序码为 { 21, 25, 49, 25*,16, 08 }，先是进行子表划分，待到子表中只有一个元素时递归到底。再实施归并，逐步退出递归调用的过程。

//静态链表的两路归并算法
#include "staticList.h"
template <class T>
int ListMerge (staticLinkedList<T>& L, int s1, int s2) {
//两个有序链表中第一个结点的下标分别为s1和s2
//将它们归并, 得到一个有序链表, 并返回其第一个
//结点的下标。L[0]是工作单元。
    int k = 0,  i = s1,  j = s2; 
    while (i != 0 && j != 0)		//做两两比较
        if (L[i].key <= L.[j].key)		//i所指排序码小
         { L[k].link = i;  k = i;  i = L[i].link; }
        else
            { L[k].link = j;  k = j;  j = L[j].link; }
	    if (i == 0) L[k].link = j;	//i链检测完, j链接上
	    else L[k].link = i;		//j链检测完, i链接上
	    return L[0].link;		//返回结果链头指针
};

递归的归并排序算法

template <class T>
int rMergeSort (staticLinkedlist<T>& L,
       const int left, const int right) {
//对链表L.Vector[left..right]进行排序。各个结点中
//的链域link应初始化为0，rMergeSort返回排序后
//链表第一个结点的下标，L.Vector[0]是工作单元
    if (left >= right) return left;
        int mid = (left+right)/2;
        return ListMerge (L, rMergeSort (L,left, mid),
             rMegerSort (L, mid+1,right));
};

链表的归并排序方法的递归深度为O(log2n)，元素排序码的比较次数为O(nlog2n)。
链表的归并排序方法是一种稳定的排序方法。

链表插入排序

基本思想是：在每个元素的结点中增加一个链接指针数据成员 link。
对于数组中的一组元素V[1], …, V[n], 若V[1], …
…, V[i-1]已经通过指针link, 按其排序码从小到大链接起来。现要插入V[i], i = 2, 3, …, n, 则必须在前面 i-1 个链接起来的元素当中，循链检测比较，找到V[i] 应插入的位置，把V[i] 链入，并修改相应链接指针。从而得到V[1], …, V[i]的一个通过指针排好的链表。
如此重复执行，直到把V[n]也插入到链表中排好序为止。

//用于链表排序的静态链表的类定义
const int DefaultSize = 10;	//在staticList.h文件中 
template <class T>
struct Element {			//静态链表元素类定义
    T key;				//排序码，其它信息略
    int link;				//结点的链接指针
	Element () : link(0) { } 	//构造函数
	Element (T x, int next = 0) : key(x), link(next) { }
						//构造函数	
}

template <class T>
class staticLinkedList {		//静态链表的类定义
public:
	staticLinkedList (int sz = DefaultSize) {
        maxSize = sz;  n = 0; 
        Vector = new Element<T>[sz];
    }
	Element<T>& operator [](int i) {return Vector[i];}
private:
	Element<T> *Vector;		//存储元素的向量
	int maxSize;	     		//最大元素个数
    int n;				//当前元素个数
};
//链表插入排序的算法
#include "staticList.h"
const T maxData;		//排序码集合中的最大值
template <class T>
int insertSort (staticLinkedList<T>& L) {
//对L.Vector[1],...,L.Vector[n]按其排序码key排序,
//L.Vector[0] 做为排序后各个元素所构成的有序循
//环链表的附加头结点使用
    L[0].key = maxData;   
    L[0].link = 1;   L[1].link = 0;
				//形成只有一个元素的循环链表
int i, pre, p;
    for (i = 2; i <= n; i++) {	
		//每趟向有序链表中插入一个结点
        p = L[0].link;			//p是链表检测指针
        pre = 0;			//pre指向p的前驱
        while (L[p].key <= L[i].key)    //循链找插入位置
            { pre = p;  p = L[p].link; }
        L[i].link = p;  L[pre].link = i;   //结点i链入
	}
};

算法分析
使用链表插入排序, 每插入一个元素, 最大排序码比较次数等于链表中已排好序的元素个数, 最小排序码比较次数为1。故总的排序码比较次数最小为 n-1，最大为n*(n-1)/2

用链表插入排序时，元素移动次数为0。但为了实现链表插入，在每个元素中增加了一个链域 link，并使用了Vector[0] 作为链表的表头结点, 用了 n 个附加域和一个附加元素。

算法在Vector[pre].key == Vector[i].key时，将Vector[i]插在Vector[pre]的后面，所以，链表插入排序方法是稳定的。

希尔排序

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

分割待排序记录的目的?

减少待排序记录个数；
使整个序列向基本有序发展

子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。

子序列划分方法
1、将排序序列分为gap个组，各组内进行直接排序。
将全部元素分为 gap 个子序列，所有距离为 gap 的元素放
在同一个子序列中。
2、然后缩小间隔 gap, 重复上述工作。直到最后取 gap == 1，
算法最后一步将所有元素放在同一个序列中排序为止。

关键问题(1)应如何分割待排序记录？

解决方法：
将相隔某个“增量”的记录组成一个子序列。
增量应如何取？
Gap的取法有多种。希尔最早提出的方法是gap1= [n/2 ] ，gap= [gap/2 ],直到gap = 1 。knuth 提出取 gap = [gap/3]+1。还有人提出都取奇数为好，也有人提出各 gap 互质为好

1
2
3

//算法描述：
for (int gap=n/2; gap>=1; gap=gap/2) 
{  以gap为增量，进行组内直接插入排序；}

关键问题(2)子序列内如何进行直接插入排序？

解决方法：
在插入记录r[i]时，自r[i-gap]起往前跳跃式（跳跃幅度为gap）搜索待插入位置。
在搜索过程中，记录后移也是跳跃gap个位置。
在整个序列中，前gap个记录分别是gap个子序列中的第一个记录，所以从第gap+1个记录开始进行插入。

//希尔排序的算法

void Shellsort (dataList<T>& L, const int left, const int right)
 { int i, j, gap = right-left+1; //增量的初始值为待排序个数
	Element<T> temp;
    do {  	gap = gap/3+1;			//求下一增量值
        		for (i = left+gap; i <= right; i++)
           	 	if (L[i] < L[i-gap]) {		//逆序
                			temp = L[i];  j = i-gap;
                			do {
                   				 L[j+gap] = L[j];  j = j-gap;
                			} while (j >= left && temp < L[j]);
               			L[j+gap] = temp;	//将vector[i]回送
           		}
    } while (gap > 1);
};
//for循环里gap换成1得到直接插入的代码

算法分析

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

交换排序

交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置

交换排序的主要算法有：

1) 起泡排序
2) 快速排序

起泡排序(Bubble Sort)

基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。
优点：每趟结束时，不仅能挤出一个最小（大）值到最前（后）面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。

基本方法是：设待排序元素序列中的元素个数为 n。顺次两两比较V[j-1].key和V[j].key。如果发生逆序，则交换V[j-1]和V[j]。

第一趟：比较A[n-2]和A[n-1],如果A[n-2]大，则交换它两。然后再比较现在的A[n-3]和A[n-2],一直到A[0]和A[1].经过第一趟，最小的值冒到了最后A[0]

第二趟：对A[1]~A[n-1]做同样的操作，第二趟结束时，整个序列的第二小元素冒到了A[1]
……
第n-1趟，比较A[n-2]和A[n-1]。

其实，在某一趟比较过程中，如果没有发生过交换，则本趟完成即可结束排序算法。所以用exchange记录是否发生过交换，如果没发生过则提前退出。

//起泡排序的算法
type  int T;
void BubbleSort (T V[], int n ) {
   bool exchange ;   int i , j ;
	for (i=1;i<n ; i++){
	exchange = false;		    	//标志为0假定未交换
	for ( j = n-1;  j >= i;  j--)     
 		if (V[j-1] > V[j]) { 	//逆序
                T temp=V[j-1];  V[j-1]=V[j]; V[j]=temp//交换
	            exchange = true;      //标志置为1,有交换
            }
if(exchange==false) return;
    }

起泡排序需要一个附加元素以实现元素值的对换。起泡排序是一个稳定的排序方法。

算法分析
第i趟对待排序元素序列V[i-1],V[i],,V[n-1]进行排序，结果将该序列中排序码最小的元素交换到序列的第一个位置(i-1)。

最多做n-1趟起泡就能把所有元素排好序。
在元素的初始已经按升序排好序时，此算法只执行n-1次排序码比较，不移动。这是最好的情形。

最坏的情形是算法执行n-1趟起泡,第i趟 (1≤ in) 做n-i次排序码比较, 执行n-i次元素交换。在最坏情形下总的排序码比较次数KCN和元素移动次数RMN为：

KCN= 1/2 * n(n-1) RMN=3/2 *n(n-1)

快速排序 (Quick Sort)

基本思想：

对于输入a[ p: r ]，按以下步骤进行排序：
(1)分解:取a中的一个元素为支点(pivot) 将a[p: r ]划分成3段::
a[p: q-1], a[q ], a[ q+1:r], 使得
a[ p:q-1]中任一元素a[q],
a[q+1: r]中任一元素 a[q]; 下标q 在划分过程中确定。
(2)递归求解:递归调用快速排序法分别对a[p:q-1]和a[q+1:r ]排序。直到每个子表的元素只剩一个或0个。此时便为有序序列了。

优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！
前提：顺序存储结构

//快速排序的算法
 #include "dataList.h"
template <class T>
void QuickSort (dataList<T>& L,  int left,  int right) 
{
//对Vector[left..right]进行排
if (left < right) {		//元素序列长度大于1时
        int pivotpos = L.Partition (left, right);    //划分
        QuickSort (L, left, pivotpos-1);
        QuickSort (L, pivotpos+1, right);
	}
}；

关键问题⑴：如何选择轴值？

选择轴值的方法：
1.使用第一个记录的关键码；
2.选取序列中间记录的关键码；
3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；
4.随机选取轴值。

选取不同轴值的后果：
决定两个子序列的长度，子序列的长度最好相等。

关键问题⑵：如何实现一次划分？

方法1：当基准点为第一个元素时，执行一次循环，关键码小于基准点的左移，关键码大于基准点的右移

方法2：是采用从两头向中间交替式逼近法；

template <class T>
int dataList<T>::Partition (const int low, const int high) {
//数据表类的共有函数
    int pivotpos = low;
    Element<T> pivot = Vector[low];//基准元素
for (int i = low+1; i <= high; i++)
 			                //检测整个序列, 进行划分
      if (Vector[i] < pivot) {
            pivotpos++;
            if (pivotpos != i)   
                Swap(Vector[pivotpos],Vector[i]);
        }				//小于基准的交换到左侧去
    Vector[low] = Vector[pivotpos];
    Vector[pivotpos] = pivot;								//将基准元素就位	
    return pivotpos;	//返回基准元素位置
};

//参考代码：一趟划分过程
int Partition( SqList &L,  int low,  int high)
{ 
    L.r[0] = L.r[low];
    pivitkey = L.r[low].key;
    while( low < high){
         while( low < high && L.r[high].key >= pivotkey)  --high;
         L.r[low] = L.r[high];
         while( low < high && L.r[low].key <= pivotkey)  ++low;
         L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];   
    return low;
}

快速排序的时间性能分析

快速排序的递归执行过程可以用递归树描述。快速排序的趟数取决于递归树的高度。

最好情况：
每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog (2) n)。

最坏情况：
每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为 O(n^2)。

平均情况：为O(nlog (2) n)。

可以证明，函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明: 就平均计算时间而言，快速排序是内排序方法中最好的一个。

快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。

最坏情况下其排序速度退化到简单排序的水平, 比直接插入排序还慢。占用附加存储(栈)将达到O(n)。
改进办法: 取每个待排序元素序列的第一个元素、最后一个元素和位置接近正中的 3 个元素，取其排序码居中者作为基准元素。

快速排序是一种不稳定的排序方法。
对于 n 较大的平均情况而言, 快速排序是“快速”的, 但是当 n 很小时, 这种排序方法往往比其它简单排序方法还要慢。快速排序不适合对小规模的序列进行排序。

选择排序(Select Sort)

基本思想是: 每一趟 (例如第 i 趟, i = 0, 1, …, n-2) 在后面 n-i 个待排序元素中选出排序码最小的元素，作为有序元素序列的第 i 个元素。待到第 n-2 趟作完，待排序元素只剩下1个, 就不用再选了。

直接选择排序的基本步骤是：
1 在一组元素 V[i]～V[n-1] 中选择具有最小排序码的元素；
2 若它不是这组元素中的第一个元素, 则将它与这组元素中的第一个元素对调;
3 在这组元素中剔除这个具有最小排序码的元素。在剩下的元素V[i+1] ～ V[n-1]中重复执行第1、2步, 直到剩余元素只有一个为止。

//直接选择排序的算法
#include "dataList.h"
template <class T>
void SelectSort (dataList<T>& L, 
          const int left, const int right) {
    for (int i = left; i < right; i++) {
        int k = i;        //在L[i]到L[n-1]找最小排序码元素
        for (int j = i+1;  j <= right;  j++) 
            if (L[j] < L[k]) k = j;
        if (k != i) Swap (L[i], L[k]);	//交换 
    }
};

直接选择排序的排序码比较次数 KCN 与元素的初始排列无关。
设有 n 个元素，则第 i 趟从n-i个记录中挑选最小元素所需的比较次数总是 n-i-1 次。
总的排序码比较次数为 n(n-1)/2

元素移动次数与元素序列初始排列有关。正序最少RMN = 0。反序为 RMN = 3(n-1)

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

链表直接选择排序

若待排序的数据元素顺序存放于单链表中，每一趟排序先在链表中选择关键码值最大的元素，将它从链中摘下，再插入一个初始为空的新链表的首部。
当所有元素都从原链表中摘下并插入到新链表中，则新链表中元素已经有序链接起来。

//链表直接选择排序的算法
#include "staticList.h"
template <class T>
int selectSort (staticLinkedList<T>& L) {
//L.Vector[0]作为表头结点使用，L.Vector[1].data
//到L.Vector[n].data存放数据
    int f = L[0].link, p, q, r, s;  
    L[0].link = 0;
    while (f != 0) {     		//原始链表未扫描完
        p = s = f;  q = r = 0;		//s指示当前最大元素
        while (p != 0) {
        if (L[p].data > L[s].data ) { s = p;  r = q; }
                //记忆当前找到的排序码最大结点
          q = p;  p = L[p].link;
      }
        if (s == f ) f = L[f].link; 	    //结点s从链中摘下
        else L[r].link = L[s].link;
        L[s].link = L[0].link;
        L[0].link = s;
	     //结点s插入到结果链表的前端
    }
};

堆排序 (Heap Sort)

利用堆及其运算, 可以很容易地实现选择排序的思路。
堆排序分为两个步骤
根据初始输入数据，利用堆的调整算法 siftDown( ) 形成初始堆; 通过一系列的元素交换和重新调整堆进行排序。
为了实现元素按排序码从小到大排序，要求建立最大堆。

大根堆：对应的完全二叉树中，任意一个节点的关键字都大于或等于它的孩子节点的关键字。

//最大堆的向下调整算法
template <class T>
siftDown (dataList<T>& L, const int start, const int m){
//私有函数: 从结点start开始到m自上向下比较, 
//如果子女的值大于双亲的值, 则相互交换, 将一
//个集合局部调整为最大堆。
    int i = start;  int j = 2*i+1;	 //j是i的左子女
	Element<T> temp = L[i];	 //暂存子树根结点
    while (j <= m) {		   	 //逐层比较
        if (j < m && L[j] < L[j+1]) j++;
 					  //让j指向两子女中的大者
	    if (temp >= L[j]) break;	 //temp排序码大不调整
        else {			    //否则子女中的大者上移
            L[i] = L[j];
		  i = j;  j = 2*j+1;  	    //i下降到子女位置
        }
    }
	L[i] = temp;		    //temp放到合适位置
};

基于初始堆进行堆排序

最大堆堆顶具有最大值，将L.Vector[0]与L.Vector[n-1]对调,
再对前面的n-1个元素, 使用堆的调整算法siftDown(L, 0, n-2)，重新建立最大堆。
依次对调L.Vector[0]和L.Vector[n-2]，再调用siftDown(L, 0, n-3), 对前面的n-2个元素重新调整…。
如此反复执行，最后得到全部排序好的元素序列。这个算法即堆排序算法。

堆排序的算法

template <class T>
void HeapSort (dataList<T>& L) {
//对表L.Vector[0]到L.Vector[n-1]进行排序, 使得表
//中各个元素按其排序码非递减有序
    int i, n = L.length();
    for (i = (n-2)/2; i >= 0; i--) 	//将表转换为堆
        siftDown (L, i, n-1);	
    for (i = n-1; i >= 0; i--) {		//对表排序
        L.Swap(0, i);  siftDown (L, 0, i-1);
    }
};

堆排序分析

对高度为h的堆，一次“筛选”所需进行的关键字比较的次数至多为2(h-1)。
对n个关键字，建成高度为h=[ log(2) n +1] 的堆，所需关键字比较次数不超过4n
调整“堆顶”n-1 次，总共进行的关键字比较的次数不超过：2n*([log (2) n])

因此，堆排序的时间复杂度为O(nlogn)。
空间复杂度为O(1)，不稳定。

数据结构经典算法启示

在操作系统中，将多个进程放在一个队列中，每个进程有一个优先级，总是出队优先级最高的进程执行。
采用优先队列，用堆来实现！

锦标赛排序、基数排序没整理。以后用到了再说.

矿大计算机学院资源共享计划·博客

数据结构笔记（第九章）

第九章排序

插入排序 (Insert Sorting)

直接插入排序 (Insert Sort)

折半插入排序 (Binary Insertsort)

归并排序 (Merge Sort)

链表插入排序

希尔排序

交换排序

起泡排序(Bubble Sort)

快速排序 (Quick Sort)

选择排序(Select Sort)

堆排序 (Heap Sort)

第九章 排序

插入排序 (Insert Sorting)

直接插入排序 (Insert Sort)

折半插入排序 (Binary Insertsort)

归并排序 (Merge Sort)

链表插入排序

希尔排序

交换排序

起泡排序(Bubble Sort)

快速排序 (Quick Sort)

选择排序(Select Sort)

堆排序 (Heap Sort)

第九章排序