8.排序
8.1概念
1.什么是排序?
排序：将一组杂乱无章的数据按一定规律顺次排列起来。即，将无序序列排成一个有序序列(由小到大或由大到小）的运算。如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言。
8.2插入排序
8.2.1直接插入排序
1.基本思想:
每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的。
2.插入方法：
在插入a[i]前，数组a的前半段(a[0]----a[i-1])是有序段，后半段(a[i]~a[n-1])是停留于输入次序的“无序段”。
-插入a[i]使a[0]~a[i-1]有序，也就是要为 a[i] 找到有序位置 j (0≤j≤i) ,将a[i]插入在a[j]的位置上。
void Insertsort (SqList &L){//对顺序表L做直接插入排序for(i=2;i<=L.length ;++i)if(L.r[i].key<L.r [i-1].key) //l“<”，需将r[i]插入有序子表{L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中L.r[i]=L.r[i-1];//r[i-1]后移for(j=i-2; L.r[0].key<L.r[j].key; --j)//从后向前寻找插入位置L.r[j+1]=L.r[j];//记录逐个后移，直到找到插入位置L.r[j+1]=L.r[0] ;//将r[0]即原r[i]，插入到正确位置}}
3.算法特点:
(1）稳定排序。
(2）算法简便，且容易实现。
(3）也适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针。
(4)更适合于初始记录基本有序(正序）的情况，当初始记录无序,n 较大时，此算法时间复杂度较高,不宜采用。
4.直接插入排序在什么情况下效率比较高?
直接插入排序在基本有序时效率较高；
在待排序的记录个数较少时，效率较高。
8.2.2折半插入排序
查找插入位置时采用折半查找法
void BlnsertSort ( SqList &L ) {for ( i = 2; i <= L.length ; ++i){//依次插入第2~第n个元素L.r[0]= L.r[i];//当前插入元素存到“哨兵”位置low = 1 ; high = i-1 ;//采用二分查找法查找插入位置while ( low <= high ) {mid = ( low + high )/2;if ( L.r[O].key < L.r[mid]. key ) high = mid -1 ;else low = mid + 1;}//循环结束，high+1则为插入位置for ( j=i-1; j>=high+1; -- j ) L.r[j+1] = L.r[j];//移动元素}}// BInsertSort
折半插入排序–算法分析:
折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快;它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第i个对象时，需要经过Llog2i」+1次关键码比较，才能确定它应插入的位置;
(1) 当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差;
(2) 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少;折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。
（1）减少了比较次数，但没有减少移动次数；
（2）平均性能优于直接插入排序
8.2.3希尔排序
1.基本思想：
先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
2.过程：
3.特点：
缩小增量多遍插入排序希尔排序法是一种不稳定的排序算法。
8.3交换排序
1.基本思想:
两两比较，如果发生逆序则交换，直到所有记录都排好序为止。
2.常见的交换排序方法:
冒泡排序，快速排序。
8.3.1冒泡排序
1.思想：
前小后大的原则，让最大的到后面去，注意注意！：直到在某一趟排序过程中没有进行过交换记录的操作,说明序列已全部达到排序要则完成排序。
例1：
例2：
void bubble_sort(SqList &L){//冒泡排序算法int m,i,j; RedType x;//交换时临时存储for(m=1; m<=n-1; m++){//总共需m趟for(j=1; j<=n-m; j++)if(L.r[j].key>L.r[j+1].key){//发生逆序x=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=x;//交换} //endif}//for}
2.特点：
优点: 每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素;
如何提高效率?
—旦某一趟比较时不出现记录交换，说明已排好序了，就可以结束本算法。
8.3.2快速排序
1.基本思想：
任取一个元素(如:第一个)为中心；所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表;对各子表重新选择中心元素并依此规则调整；直到每个子表的元素只剩一个
2.过程：
具体实现:选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。
中间数(枢轴）:可以是第一个数、最后一个数、最中间一个数、任选一个数。
3.算法分析：
时间复杂度：平均计算时间是O(nlog2n)。
实验结果表明:就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。
快速排序是一种不稳定的排序方法。
例如,一次划分后：49与49*相对位置变化。
输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法。
改变划分元素的选取方法，至多只能改变算法平均情况的下的世界性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂性总是O(n2)
8.4选择排序
8.4.1简单选择排序（直接选择排序）
1.基本思想：在待排序的数据中选出最大（小)的元素放在其最终的|业且。
2.基本操作:
首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将
它与第二个记录交换。
重复上述操作，共进行n-1趟排序后，排序结束。
3.操作规则：
最小的到前面去。
4.特点：
不稳定。
8.4.2归并排序
1.基本思想:
将两个或两个以上的有序子序列“归并”为一个有序序列。
通常采用的是2-路归并排序。
2.过程：
整个归并排序仅需 log2n 趟
3.关键问题：
二如何将两个有序序列合并成一个有序序列。
8.4.3堆排序
8.4.3.1定义
定义：若n个元素的序列{aa2… a,}满足
则分别称该序列{a1 a2… an}为小根堆和大根堆。
实质：可以看出，堆实质是满足如下性质的完全二叉树:二叉树中任一非叶子结点均小于(大于)它的孩子结点。
例：判断是什么堆
{98，77，35，62，55，14，35 ，48 }
{14，48，35，62，55，98，35，77 }
例：判断是否是堆
8.4.3.2堆排序
若在输出堆顶的最小值(最大值)后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值)…如此反复，便能得到一个有序序列，这个过程称之为堆排序。
8.4.3.3堆的调整
解决：如何在输出堆顶元素后，调整剩余元素为个新的堆?
步骤：（以大根堆为例）
输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中大者进行交换;重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
例：
8.4.3.4堆的建立
在完全二叉树中，所有以叶子结点（序号i > n/2)为根的子树是堆。依次将以序号为n/2,n/2 - 1，…1的结点为根的子树均调整为堆即可。
