排序算法回顾

排序与排序算法

排序指根据键值大小对有序集合进行处理，使其变得有序的过程；

排序的最终结果可以是从小到大排列，也可以是从大到小排列，这两种排列在算法实现上没有明显区别。一般情况下，算法书都选择使用由小到大的方式介绍排序算法；

合理的排序算法的时间复杂度应小于O(n2)，理想的排序算法的时间复杂度应是O(nlogn)。

时间复杂度为O（n2）的排序算法有冒泡排序、插入排序；

时间复杂度为O(nlogn)的排序算法有快速排序、堆排序；

冒泡排序

将数列看成是从上到下，序列依次递增的一列数的排列。每次最小的数会类似于水中的气泡一样从底部往上移动。

输入：A[1...N]

输出：A[1...N],其中A[1]<=A[2]<=...<=A[N]

算法：

    for i<--1 to N-1

        for j<--N to i+1

            if A[j] < A[j-1]

                exchange(A[j], A[j-1]);

            end if

        end for

    end for

    Java版本实现：
    public static void bubbleSort（int[] A） {
        for(int i=0; i<N-1; i++) {
            for (int j=n-1; j>i; j--) {
                if (A[j] < A[j-1]) {
                    int temp = A[j];
                    A[j] = A[j-1];
                    A[j-1] = temp;
                }
            }
        }
    }


插入排序
  通过不停地寻找未排序部分的最小元素，并交换至已排序部分的末尾，实现对数列的排序。
  输入：A[1...N]
  输出：A[1...N],其中A[1]<=A[2]<=...<=A[N]
  外层循环不变式：
    阶段：i
    描述：
      1）游标i前（不包含i）的元素的集合是全集A中最小的i-1个数组成的集合；
      2）游标i前的元素是有序的；
    初始：i=1
    结束：i=N
  内层循环不变式：
    变量：k
    阶段：j
    描述：
      1）j<=k<=N
      2）k是A[j...N]中最小元素的下标
    初始：j=N k=N
    结束：j=i
    处理逻辑：
      if A[j]<A[k] then k<--j
  算法：
  for i<-1 to N
   k<-N
   for j<-N-1 to i
    if A[j]<A[k] then
     k<-j
    end if
   end for
   exchange A[i]<->A[k]
  end for


  Java版本实现
  public static void insertSort(int[] A) {
   for (int i=0; i<A.length; i++) {
    int k = A.length - 1;
    for (int j=A.length - 2; j>=i; j--)
     if (A[j]<A[k]) k=j;
    
    int temp = A[k];
    A[k] = A[i];
    A[i] = temp;
   }
  }


归并排序
  通过将两段已经排序好的数组进行归并，从而完成对整个数组的排序。
  输入：A[p..q..r]， A[p..q-1]和A[q..r]是已经排好序的两端数组
  输出：排好序的数组A[p...r]
  变形：L[1...q-p+1],其中L[1...q-p]<-A[q..q-1],L[q-p+1]<-MAX;
       R[1..r-q+2],其中R[1...r-q+1]<-A[q..r],R[r-q+1]<-MAX;
  循环不变式：
    变量：m，n
    阶段：i
    描述：
      1）集合A中，在i前的所有元素均已排序
      2）集合L中，在m前的所有元素均已处理
      3）集合R中，在n前的所有元素均已处理
    起始：i<-p
    终止：i<-r+1
    处理逻辑：
      if L[m] < R[n] then
       A[i] <- L[m++]
      else
       A[i] <- R[n++]
      end if

  算法：
  L[1...q-p]<-A[q..q-1];
  L[q-p+1]<-MAX;


  R[1...r-q+1]<-A[q..r];
  R[r-q+1]<-MAX;


  m<-1;
  n<-1;
  for i<-p to r
   if L[m] < R[n] then 
    A[i] <- L[m++]
   else
    A[i] <- R[n++]
   end if
  end for


  归并排序
  输入：A[1...N]
  输出：A[1...N],其中A[1]<=A[2]<=...<=A[N]
  算法：
    MergeSort（A，p q）
     if p>=q
      return
     r = (q+p)/2;
     MergeSort(A, p, r-1);
     MergeSort(A, r, q);
     Merge(A, p, r, q);




  Java实现
  public static void merge(int[] A, int p, int q, int r) {
   int[] L = new int[q-p+1];
   int[] R = new int[r-q+2];
   System.arraycopy(A, p, L, 0, q-p);
   System.arraycopy(A, q, R, 0, r-q+1);
   L[p-q] = Integer.MAX_VALUE;
   R[r-q+1] = Integer.MAX_VALUE;
   int m = 0;
   int n = 0;
   for (int i=p, i<=r; i++) {
    if (L[m] < R[n]) 
     A[i] = L[m++];
    else 
     A[i] = R[n++];
   }
  }


  public static void mergeSort(int[] A, int p, int q) {
   if (q <= p) return ;
   int r = (q+p)/2;
   mergeSort(A, p, r-1);
   mergeSort(A, r, q);
   merge(A, p, r, q);
  }