9.1.1 前提

排序算法前提条件:

(1)N至少是10000个数据起步的，那么排序算法的效率就十分重要。

(2)函数头统一规范格式:x_sort，X为排序算法名称，统一默认参数为两个，待排元素放在数组ElemenType中，可以是任意类型，可比较大小即可。正整数N为要排序的元素个数，可以是任意一种数据结构，只要能排序即可，比如字符串，无特别说明，这里指的是整数。

(3)只基于比较的排序，定义好的符号，<=>。

(4)内部排序:假设内存空间充分大，所有数据都可以一次性的被导入到内存空间中，那么所有的排序过程是在内存空间中一次性完成的。

外部排序:如果内存空间2GB，如果对10TB的数据进行排序，那么内部排序就不可能了，待完善。

(5)稳定性:比如要把学生名单做排序，有两个学生都叫小明AB，在排序之前，有一个相对的位置，那么在完成排序之后，即使它俩重名，但是俩学生AB的顺序保持不变。如果一个排序算法，能够保证这个相对顺序不改变，那么这种排序算法就是稳定的，否则不稳定。

(6)非常重要的一点，每一种算法都有其存在的理由，没有任何一种算法是在任何一种情况下都是最快最好的，当数据具有某种特征后，这一种算法可能是最好的，但数据换了特征后，这一种算法可能就不适配了，另一种算法可能就是最好的。当一种算法能被写进教材，它的存在肯定有非常重要的理由的。

9.1.2 冒泡排序 (稳定性-顺序O(N)逆序O(N^2))

假设有一堆泡泡，要把小的放在上面，从上到下比较相邻的两个泡泡，如果小的在上面，大的在下面，那就不动了，否则二者调换位置，这就完成了一趟排序，可以肯定的是，大的一定在小的下面，以后的排序，重复这个过程即可，对前面的N-1个数重复这个过程。

特殊情况:如果待排元素都放在链表中怎么办呢？

冒泡排序在数组中和链表中都没问题，因为每次是从上到下按一个方向扫描，每次交换相邻的两个元素，要注意的是，交换只在某个元素严格大于下一个元素的时候才做交换，其他情况不做交换。那么也保证了这个冒泡排序算法的稳定性。

/*
冒泡排序
时间复杂度-最好的情况(顺序-T=O(N)):一开始泡泡都是从小到大排好序的,从始至终都不需要执行任何一次的交换,
但无论如何都得从上到下扫描一遍整个序列,可以从if(flag=0)break跳出。
时间复杂度-最坏的情况(逆序-T=O(N^2)不可接受):整个是逆序的,一开始最大的泡泡在最上面,必须要走完N-1趟排序,两两元素不断的做交换.
*/
void Buddle_Sort(ElementType A[], int N){

	/*
	P指最后一个元素的位置.
	当i = P - 1,P - 1跟P比较一下做最后一次交换,那么这就完成了一趟冒泡.
	*/
	for(P = N - 1; P >= 0; P--){
		/*
		如果运气比较好,在中间某一步的时候已经有序了,那么程序是不知道的,
		不管是不是交换,那么每次都需要比较一下.
		如何知道swap从头到尾在这一趟排序中从来没有被执行过,这个序列就是完全有序的,不用再往下做了.
		*/
		flag = 0;
		/* 一趟冒泡 */
		for(i = 0; i < P; i++){
			if(A[i] > A[i + 1]){
				Swap(A[i], A[i + 1]);
				/* 标识发生了交换 */
				flag = 1;
			}
		}
		/* 全程无交换 */
		if(flag == 0){
			break;
		}
	}

}

9.1.3 插入排序 (对比希尔排序)(稳定性-顺序O(N)逆序O(N^2))

摸牌，某张牌摸到之后，和已经摸到的牌相比较，大的牌依次往后放，新牌插入对应位置。

只要严格的比前面的牌小的时候，才移位，其他不移位，这样也保证插入排序是稳定的。

/*
插入排序
时间复杂度-最好的情况(顺序-T=O(N)):一开始所有牌都是从小到大排好序的,任何一张牌都不需要移动,
但无论如何都得从上到下扫描一遍整个序列,即需要把所有的牌都摸上来。
时间复杂度-最坏的情况(完全逆序-T=O(N^2)不可接受):每次循环,所有的牌都要向后错一位,一共做了N-1次循环.
*/
void InsertionSort(ElementType A[], int N){

	int P, i;
	ElementType Tmp;
	/*
	不是从第0张牌开始,而是从第一张牌开始,默认第0张牌已经在手中了.
	*/
	for(P = 1; P < N; P++){
		/* 取出未排序序列中的第一个元素*/
		Tmp = A[P];
		/*
		从最后一张牌往前对比
		比如当Q大于J时,for就停止.
		*/
		for(i = P; && A[i - 1] > Tmp; i--){
			/*依次与已排序序列中元素比较并右移*/
			A[i] = A[i - 1];
		}
		/* 放进合适的位置 */
		A[i] = Tmp;
	}

}

9.1.4 时间复杂度下界 (逆序对)

这里默认元素是从小到大排序的前提。

(1)两个元素呆错位置，就把这对元素或者这对元素的下标称作逆序对。

(2)上述一共9个逆序对。

(3)冒泡排序与插入排序的共同特点:每次交换两个相邻元素的时候，正好消掉一个逆序对。

因为这里有9个逆序对，所以这两种算法都必须用9次元素交换才能消掉。

(4)插入排序的时间复杂度不仅跟元素的个数N有关，而且跟序列中逆序对的个数I有关。

无论如何，都要把整个的元素从头到尾扫描一遍，至少是O(N)复杂度的，另外，操作次数是跟序列中逆序对的个数I成正比的。

如果序列中逆序对的个数I非常少，换言之，如果序列基本有序，则插入排序简单且高效，如果逆序对的个数比如跟元素的个数N是同一个数量级的，甚至比N还要小，那么整个算法的时间复杂度是线性的，O(N)这个数量级。

(1)逆序对的平均个数是O(N^2)数量级的，不管是冒泡排序还是插入排序，平均时间复杂度是跟逆序对的个数有关系的。

(2)通过(1)看定理。Ω(欧米伽)指的下界，时间复杂度Ω(N^2)，限制是任何仅以交换相邻两元素来排序的算法。要咋办呢，看(3)。

(4)上述(3)的目标。如果每次交换都是相邻两个元素的话，那么每次消去不止一个逆序对是做不到的。

如果想做到这一点，那么每次交换的两个元素相隔比较远，跳着交换，那么就有希望说在一次交换中就同时消掉了好几个逆序对，这样就会快起来。