简单排序
概述
排序函数一般的命名：
void X_Sort(ElementType A[], int N)
X为具体的排序名称，例如：冒泡、插入、希尔等等；
A[ ] 为要排序的主体；N为要排序的数据个数。 （N是正整数）
- 大多数情况下，为简单起见，讨论从小到大的整数排序
- 只讨论基于比较的排序（即 > = < 有定义）
- 只讨论内部排序（即数据全部存在于内存内，没有内存外部的数据需要排序，相对应的为外部排序）
- 稳定性：任意两个相等的数据，排序前后的相对位置不发生改变
- 没有一种排序是任何情况下都表现最好的
冒泡排序
图示
代码 （C语言）
void Bubble_Sort(ElementType A[], int N) { for(P = N -1; P >= 0; P--) { 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; //如果全部扫描之后没有元素进行交换，则说明不需要再进行排序了，所以直接退出 } }
时间复杂度
最好情况：顺序 
最坏情况：逆序 
插入排序
图示
代码（C语言）
void InsertionSort( ElementType A[], int N ) { /* 插入排序 */ int P, i; ElementType Tmp; for ( P=1; P<N; P++ ) { Tmp = A[P]; /* 取出未排序序列中的第一个元素*/ for ( i=P; i>0 && A[i-1]>Tmp; i-- ) A[i] = A[i-1]; /*依次与已排序序列中元素比较并右移*/ A[i] = Tmp; /* 放进合适的位置 */ } }
时间复杂度
最好情况：顺序 
最坏情况：逆序 
问：给定初始序列{ 34,8,64,51,32,21 }，冒泡排序和插入排序分别需要多少次元素交换才能完成？
把心中的答案记下来，我们先往下看：
时间复杂度下界
- 对于下标i < j，如果A[ i ] > A[ j ]，则称（i，j）是一对逆序对（inversion）
- 序列{ 34,8,64,51,32,21 }中总共有九对逆序对
分别为：（34,8）（34,32）（34,21）（64,51）（64,32）（64,21）（51,32）（51,21）（32,21）
交换2个相邻元素正好消去1个逆序对
故而上面那道题目的答案是9，冒泡排序和插入排序的交换元素次数都为9次；因为序列中有9对逆序对，两个简单排序都是以交换相邻元素为主的，所以次数一致。
而如果冒泡和插入排序的元素个数为N，逆序对的个数为I，那么时间复杂度就为
如果序列基本有序，则冒泡、插入排序简单且高效。
定理
- 任意N个不同元素组成的序列平均具有N（N-1）/4个逆序对
- 任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为
（ 
指的是下界）
这一意味着：要提高算法效率，我们必须：
- 每次要消去不止1个逆序对！
- 每次交换相隔较远的2个元素！
交换相隔较远的2个元素就有可能一次性消去不止1个逆序对
