讨论记录之排序

Participants：CPP，ZY ,LF，HZP

Date：08-09-20  7:20PM<o:p></o:p>

Recorder: LF，HZP<o:p></o:p>

本次讨论重点讨论了 快速排序，推排序，基数排序，计数排序算法和比较树模型；

依次介绍各种算法，为了使得记录的完整性，加入了没有讨论的一些简单算法，如果发现错误请及时通知免得贻笑大方

由于待排序的记录数量不同，使得排序过程中设计的存储器不同，可将排序算法分为两大类：一类是内部排序，一类是外部排序；

PS：讨论完了还有橘子吃，突然感觉就进入了共产主义社会！呵呵

 直接插入排序<o:p></o:p>

算法描述：<o:p></o:p>

直接插入排序是一种简单的排序算法，它的基本操作是将一个记录插入到已排序的有序表中，从而得到一个新的、记录数加1 的有序表；

伪代码：

1. Void InsertSort( int a[])
2. {
3.     for  int i= 1 to a.size
4.     int  j = i -1;
5.     int temp = a[i];
6.     if temp< a[j]
7.     {
8.         for ( j; temp>a[j]  and j>= 0;j--)
9.         {
10.             a[j+1] = a[j];
11.         }
12.         a [j+1] = temp;
13.     }
14. }

效率分析：<o:p></o:p>

时间复杂度：首先最外层循环要执行 n-1次，因为要将待排序列依次插入有序表中；对于第n次插入，至少要比较一次，最多要比较n次，最少要移动元素0次，最多要移动元素n+2次，所以算法最好的时间复杂度为O（n）（即已经排序好的序列）最坏的时间复杂度为O（n^2）,也就是元素刚好逆序的时候；平均时间复杂度约为n²/4；

空间复杂度：只需要一个元素的辅助空间，用于元素的位置交换O(1)；

稳定性：稳定

结构复杂性和使用范围：此种排序算法适用于顺序存储结构，数组通过移动实现插入，链表这通过修改指针达到目的；适用于序列的元素不多的情况；

算法衍生：在直接插入排序中元素的移动频率和比较次数很高，有人提出用2 路插入排序算法改进；第一种：折半插入排序，利用了折半搜索算法的的思想，每次和已排好序列的中间元素比较大小这样来减少比较的次数；

希尔排序<o:p></o:p>

算法描述：<o:p></o:p>

       基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

       增量序列一般都是经验数组，没有很证明最优的选法：{……9 5 3 2 1} {… 40 13 4 1}

伪代码：

2. Void  ShellSort ( int A[], int dlta[])  // A 待排序列  dlta 增量序列
3. {
4.     for int i = 0; i<dlat.size; i++
5.        ShellInsert ( int A[], int i);  // i 为增量
6. }
7. Void ShellInsert ( int A[],int n)
8. {
9.     for  int i = 0 to i-1
10.     {
11.         for  int j = i+n; j<A.size ; j+n;
12.         {
13.             int tmp = A[j];
14.             If  tmp< A[i]
15.             {
16.                    for ( int  k = i; tmp<A[i]; k = k-n )
17.                        A [k+n] = A[k];
18.             }
19.             A[k+n] = tmp;
20.          }
21.     }
22. }

效率分析：<o:p></o:p>

       Shell排序的执行时间依赖于增量序列。
    　好的增量序列的共同特征：
　　① 最后一个增量必须为1；(否则不能保证算法的正确性)
　　② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
    　有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在n^l.25到1.6n^1.25之间。

时间复杂度：O( n^3/2  )<o:p></o:p>

       希尔排序由于直接插入排序的原因：

n         当文件基本有序时直接插入排序算法需要的比较次数和移动次数较少；

n         当n较小时，n 与 n²的差别较小，即最好时间复杂度和最坏时间复杂度的差别不大；

n         当增量大时，分组数目多，但组内元素少，这样直接插入排序速度较快，当增量小时，由于数组已经基本有序，此时直接插入排序算法也有很好的效率；

空间复杂度：<o:p></o:p>

只需要一个零时变量空间；

稳定性：不稳定

冒泡排序<o:p></o:p>

算法描述：<o:p></o:p>

基本思想：在待排序列的无序区内，如果选择最大的一个元素将其“浮出水面”，对待排序列进行n-1 次冒泡，则序列完成排序过程；这种算法是进行相邻元素进行比较，然后将较大的元素往上挪动；

伪代码：

1. Void bubbleSort(  int A[])
2. { 
3.     for  int i=0; i<A.size-1 ; i++         //n-1趟 i<A.size-1
4.     {
5.          for int j = 1; j<A.size-i ; j++
6.          if A[j] < A[j-1]
7.          {
8.              int tmp = A[j];  
9.              A[j]= A[j-1]; 
10.              A[j-1] = tmp; 
11.           }
12.      }
13. }

效率分析：<o:p></o:p>

时间复杂度：n次循环，第i次循环进行n-i次比较，比较次数不能减少，最少移动0次，当序列已经有序的时候，最多移动（3+6+9+……+3n）次；所以时间复杂都最好 最坏 平均复杂度都是一样的为O（n^2）

空间复杂度：只需要一个零时变量空间；O（1）

稳定性：稳定

算法衍生：<o:p></o:p>

       如果对冒泡算法进行改进，可以设定一个标记为，标记这一趟排序是否进行了交换，若没有交换则整个算法结束；这种情况下，最好只要进行一次遍历，（已经有序）也就是O（n）的时间复杂度，空间复杂度为0；若待排序列为逆序，则达到最坏时间复杂度和空间复杂度。如上面分析；

快速排序（讨论重点）<o:p></o:p>

算法描述：<o:p></o:p>

基本思想：每一趟排序将待排记录分为两部分，其中一部分的关键字小于另一部分的所有关键字，然后分别对两部分进行排序；

伪代码：

1. Void QuickSort ( int A[], int low, int high )
2. {
3.     If  (low < high)
4.     {
5.       pivotLoc = partition(A,low,high);
6.       QuickSort(A,low,pivotLoc-1);
7.       Quicksort(A,pivot+1,high);
8.     }  
9. }
10. Int partition(int A[], int low, int high)
11. {
12.     Pivotkey = A[low];
13.     While(low<high)
14.     {
15.        while(low<high and A[high] > =pivotkey ) { high--; }
16.        A[low] = A[high];
17.        While(  low<high  and A[low] <= pivotkey ) { low++ }
18.        A[high] = A[low]
19.     }
20.     A[low] = pivotkey;
21.     Return low;
22. }

效率分析：<o:p></o:p>

快速排序的中心思想是分治法和递归

快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。

时间复杂度：最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
    　因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：
               Cmax = n(n-1)/2=O(n²)
    　如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。此时退化为冒泡排序；

在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：
        0(nlgn)

空间复杂度：快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。

稳定性：不稳定

算法衍生：<o:p></o:p>

算法改进：<o:p></o:p>

A.        改进中枢元素的选取方法：

a)         平均法：采用low high 和中间元素的平均值作为中枢值

b)        中间元素法：采用low high，和中间元素之中 元素值处于中间的值为中枢值

c)        随即法：随机选取序列中的一个元素值作为中枢值；

B.        与其他排序算法想结合：由于在待排序列元素数目较少的情况下，直接插入排序有其很好的优势，所以可以将直接插入算法与快速排序想结合，即当待排序列数目小于特定值时就采用直接插入算法。当然也可以考虑其他简单算法结合；

比较树：（为什么O(nlgn) 是比较排序算法的最好时间复杂度）

这个我描述不清楚，这个大家参考 算法导论2nd 165页 

我想说的时通过比较树模可以证明任意一个比较排序算法在最坏情况下，都需要做O(nlgn)次比较，也就是说这个比较排序算法的最好时间复杂度的下届；

       尝试论述比较树模型：对于任意可比较序列，这个序列不同的排序可能性总共是n! ,而比较树就是一个包含了所有可能的树模型！（树形状就不画了！）对于任何一种排序的可能性，都有一条路径表达这种关系！

       形状考虑一颗高度为h，具有m个可达叶节点的决策树，它对应于对n个元素所做的比较排序。因为n个输入元素共有n!种排列，每一一种都作为一个叶子节点出现在树中，故有n！<= L 。又由于一颗高为h的二叉树中，叶子的数目不多于2^h ，则有

 n！<= L<= 2^h ，

取对数，得到 h>= lg(n!) = O(nlgn)  #

快速排序的思想应用：线性时间内选择第k大的元素<o:p></o:p>

伪代码：

1. Int RandomSelect (A,p,r,i )
2. {  if p== r
3.       Return;
4.    q = RandomPartition(A,p,r);
5.    k = q-p+1;
6.    if k==i
7.           then return A[i];
8.    else i<k
9.           return RandomSelect(A,p,q-1,i);
10.    else
11.           return RandomSelect( A,q+1,r,i-k)；
12. }

简单注释：和快速排序一样，RandomPartition(A,p,r) 是对待排序列进行划分，返回值为中枢元素的位置（q），中枢位置前的元素都小于中枢值，中枢位置后的元素都大于中枢值，换句话说,q位置的元素就是第q大的元素。这样如果k恰好等于q，则返回，如果q<k;则说明第k大的元素在q元素后面的第k-q个位置上，如果q>k，则在第k大元素在前面的第k个位置。

现在需要证明的是这个过程是线性时间的：证明见算法导论p111；

简单选择排序<o:p></o:p>

算法描述：<o:p></o:p>

每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

伪代码：

Void SelectSort( int A[] )

{ for int i= 0 to A.size

      j = SelectMin(A,i+1);  // 选择i后面最小的元素

       A[i] 与 A[j] 交换   

}

效率分析：<o:p></o:p>

时间复杂度：无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数也是O(n²)

       待排序列如果是已经排好序的，则移动次数为0.，如果是逆序的，则每次都需要交换，也就是移动次数为3（n-1）<o:p></o:p>

空间复杂度：如果需要交换则为O（1），否则为0

稳定性：不稳定

结构复杂性和使用范围：直接选择排序的用处不大，他的用处主要是用于引出树形排序和堆排序

堆排序<o:p></o:p>

算法描述：n个关键字序列K_l，