APS105预习-14

Chapter 14 Sorting 排序

本节主要介绍插入排序，选择排序和冒泡排序三种基础排序算法。本节所有内容均为排升序，降序可以此类推

插入排序 Insertion Sort

插入排序在第i次迭代的时候将数组的前i个元素视为有序的，排序操作从数组下标1开始到结尾(A[top] 1<=top<length)

宏观来看，插入排序就是将元素插入至数组有序部分的正确位置。

微观来看，排序核心部分逻辑为：将A[top]的值与其之前的每一个值比较，如果该值大于A[top]，则向右挪一位，腾出一个空位。该操作结束后，将A[top]放置于空位即可。

以下是代码实现：

void insertionSort(int A[], int listLength) {
  for (int top = 1; top < listLength; top++) {
    int item = A[top];
    int i = top;
    while (i > 0 && A[i - 1] > item) {
      A[i] = A[i - 1];
      i--;
    }

    A[i] = item;
  }
}

具体实现中有一些细节值得注意：

• 内层while循环中是A[i - 1] > item而不是``A[i - 1] > A[top]。因为A[top]会在循环过程中被修改，我们需要和提前缓存的A[top]`的值做对比。