7.1简单排序

前提：

• void X_Sort (ElementType A[], int N)
• 为简单起见，讨论整数大小的排序。
• N是正整数。
• 只讨论基于比较的排序。
• 只讨论内部排序。

1. 冒泡排序：
   从上到下比较相邻2个泡泡。

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[1], A[I+1]);
           flag = 1;
           }
        }
       if (flag == 0) break;
  }
}

时间复杂度： 最大是 T= O(N平方)； 最小 是T = O(N)

2. 插入排序
   打牌的时候，牌的插入过程。新牌从后往前和前边的比较，然后插入。

 void Insert_sort (ElementType A[], int N) {
         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;   //将新牌落位。
       }
}

时间复杂度 也是最大是 O(N 平方)，最小是O(N)

逆序对：对于下标i<j，如果A[i]>A[j]，则称(i,j)是 一对逆序对(inversion)。

对于插入排序和冒泡排序，T(N, I) = O( N+I ) I是逆序对的个数。

• 任意N个不同元素组成的序列平均具有 N ( N - 1 ) / 4 个逆序对。
• 任何仅以交换相邻两元素来排序的算 法，其平均时间复杂度为 Ω ( N2 )。