9.1 简单排序(冒泡、插入)
9.1.1 概述
voidX_Sort(ElementTypeA[],intN)//sort就是排序的意思，X是排序算法的名称
//统一默认输入的参数有两个(一个是待排的元素放在一个数组里，数据类型为ElementType任意类型。另外一个是正整数N，表示的是我们要排的元素到底有多少个，默认讨论整数(从小到达)的排序)
1.N是正整数
2.只讨论基于比较的排序(>=<有定义)
3.只讨论内部排序(假设我们内存空间足够大，所有数据可以一次性导入内存空间里，然后所有的排序是在内存里面一次性完成的)
//外部排序(假设我有的内存空间有2GB，但是要求我们对10TB的数据进行排序，这个时候内部排序就不行了)
4.稳定性：任意两个相等的数据，排序先后的相对位置不发生改变
5.没有一种排序是任何情况下都表现最好
9.1.2 冒泡排序
voidBubble_Sort(ElementTypeA[],intN)
{
for(i=0; i<P;P--){
flag=0;//表示还没有执行果任何一次交换
for(i=0;i<P;i++ ){//一趟冒泡
if(A[i] >A[i+1] ){
Swap(A[i],A[i+1]);
flag=1;//要交换的时候标识变为1
}
}
if( flag==0 ) break;//全程无交换
}
}
最好情况：顺序T=O(N) 全程无交换
最坏情况：逆序T=O(N²)
冒泡排序优点：
- 所有的待排元素是放在一个单向链表里的(冒泡排序可以对数组，对单项链表都可以实现，其他排序不好实现)
- 算法稳定
9.1.3 插入排序
voidInsertion_Sort( ElementTypeA[],intN )
{
for( P=1;P<N; P++ ){
Tmp=A[P];//摸下一张牌，Tmp为临时存放的位置
for( i=P; i>0&&A[i-1] >Tmp;i--)//旧牌大
A[i] =A[i-1];//移除空位
A[i] =Tmp;//新牌落位
}
}
//最好情况：顺序T = O(N)
//最坏情况：逆序T = O(N²)
插入排序好处：
- 程序短，简单
- 比冒泡排序好在：冒泡排序是两两交换，两两元素互换的时候他要涉及到第三步。而插入排序则是每个元素向后错，最后他一次性放到他那个空位里面去(不是插入排序最主要的)
- 稳定
给定初始序列{34, 8, 64, 51, 32, 21}，冒泡排序和插入排序分别需要多少次元素交换才能完成？
冒泡9次，插入9次
对一组包含10个元素的非递减有序序列，采用插入排序排成非递增序列，其可能的比较次数和移动次数分别是？
45, 44
9.1.4 时间复杂度下界
问题：序列{34，8，64，51，32，21}中有多少逆序对？9对
逆序对的数量跟交换元素次数是一样的，也就说明了交换两个相邻元素正好消去一个逆序对！
插入排序：T(N,I) = O(N+I)
- 如果序列基本有序，则插入排序简单且非常高效
逆序对平均个数：大O(N2)数量级的，不管是冒泡排序还是插入排序，他们的平均时间复杂度是跟逆序对的个数有关系的
Ω：指的是下界
这意味着：要提高算法效率，我们必须
- 每次消去不止一个逆序对
- 每次交换相隔较远的2个元素，这样一次性就消掉了不止一个逆序对
9.2 希尔排序(by Donald Shell)
基本思路：利用了插入排序的简单，同时克服插入排序每次只交换相邻两个元素的缺点
到最后使用1-间隔的排序来保证序列有序(彻底的插入排序)。但此时这个序列已经基本有序了，大多数的逆序对已经在前面两趟5-间隔和3-间隔里面被消除掉了
重要性质：3-间隔有序的序列还保持了前面5-间隔有序的这个性质(没有把上一步的结果变坏)
希尔增量序列
- 原始希尔排序
网络异常，图片无法展示|
voidShell_Sort( ElementTypeA[],intN )
{
for(D=M/2; D>0; D/=2 ){//希尔增量序列
for( P=D; P<N; P++ ){//插入排序，D是距离(第0张牌在我手里，下一张牌从第D张牌开始摸)
Tmp=A[P];
for( i=P; i>=D&&A[i-D] >Tmp;i-=D )
A[i] =A[i-D];
A[i] =Tmp;
}
}
}
- 最坏情况：
网络异常，图片无法展示|
O是一个上界(可能达不到)
网络异常，图片无法展示|
增长速度跟N²一样快
坏例子：
网络异常，图片无法展示|
增量元素不互质，则小增量可能根本不起作用
更多的增量序列
网络异常，图片无法展示|
用Sedgewick增量序列
voidShellSort( ElementTypeA[], intN )
{ /* 希尔排序 - 用Sedgewick增量序列 */
intSi, D, P, i;
ElementTypeTmp;
/* 这里只列出一小部分增量 */
intSedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};
for ( Si=0; Sedgewick[Si]>=N; Si++ )
; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */
for ( D=Sedgewick[Si]; D>0; D=Sedgewick[++Si] )
for ( P=D; P<N; P++ ) { /* 插入排序*/
Tmp=A[P];
for ( i=P; i>=D&&A[i-D]>Tmp; i-=D )
A[i] =A[i-D];
A[i] =Tmp;
}
}
