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
}