简单排序

一、前提

void X_Sort(ElementType A[], int N);

大多数情况下，为简单起见，讨论从小到大的整数排序
N是正整数
只讨论基于比较的排序（>=<有定义）
只讨论内部排序
稳定性：任意两个相等的数据，排序前后的相对位置不发生改变。
没有一种排序是任何情况下都表现最好的

二、冒泡排序

 1 void Bubble_Sort( ElementType A[], int N )
 2 { 
 3     for ( P=N-1; P>=0; P-- ) {
 4         flag = 0;
 5         for( i=0; i<P; i++ ) { /* 一趟冒泡 */
 6             if ( A[i] > A[i+1] ) {
 7                 Swap(A[i], A[i+1]);
 8                 flag = 1; /* 标识发生了交换 */
 9             }
10         }
11         if ( flag==0 ) break; /* 全程无交换 */
12     }
13 }

最好情况：顺序T = O(N)

最坏情况：逆序T = O(N²)

三、插入排序

 1 void InsertionSort( ElementType A[], int N )
 2 { /* 插入排序 */
 3      int P, i;
 4      ElementType Tmp;
 5       
 6      for ( P=1; P<N; P++ ) {
 7          Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
 8          for ( i=P; i>0 && A[i-1]>Tmp; i-- )
 9              A[i] = A[i-1]; /*依次与已排序序列中元素比较并右移*/
10          A[i] = Tmp; /* 放进合适的位置 */
11      }
12 }

最好情况：顺序T = O(N)

最坏情况：逆序T = O(N²)

四、时间复杂度下界

对于下标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个逆序对？
插入排序： T(N, I) = O( N+I )

如果序列基本有序，则插入排序简单且高效

定理：任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对。
定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度Ω（N²）。
这意味着：要提高算法效率，我们必须
- 每次消去不止1个逆序对
- 每次交换相隔比较远的2个元素

无欲速，无见小利。欲速，则不达；见小利，则大事不成。