Insertion Sort - 插入排序

核心：通过构建有序序列，对于未排序序列，在已排序序列中从后向前扫描(对于单向链表则只能从前往后遍历)，找到相应位置并插入。实现上通常使用in-place排序(需用到O(1)的额外空间)

  1. 从第一个元素开始，该元素可认为已排序
  2. 取下一个元素，对已排序数组从后往前扫描
  3. 若从排序数组中取出的元素大于新元素，则移至下一位置
  4. 重复步骤3，直至找到已排序元素小于或等于新元素的位置
  5. 插入新元素至该位置
  6. 重复2~5

性质：

  • 交换操作和数组中倒置的数量相同
  • 比较次数>=倒置数量，<=倒置的数量加上数组的大小减一
  • 每次交换都改变了两个顺序颠倒的元素的位置，即减少了一对倒置，倒置数量为0时即完成排序。
  • 每次交换对应着一次比较，且1到N-1之间的每个i都可能需要一次额外的记录(a[i]未到达数组左端时)
  • 最坏情况下需要~N^2/2次比较和~N^2/2次交换，最好情况下需要N-1次比较和0次交换。
  • 平均情况下需要~N^2/4次比较和~N^2/4次交换

Insertion Sort

Implementation

Python

  1. #!/usr/bin/env python
  4. def insertionSort(alist):
  5.     for i, item_i in enumerate(alist):
  6.         print alist
  7.         index = i
  8.         while index > 0 and alist[index - 1] > item_i:
  9.             alist[index] = alist[index - 1]
  10.             index -= 1
  12.         alist[index] = item_i
  14.     return alist
  16. unsorted_list = [6, 5, 3, 1, 8, 7, 2, 4]
  17. print(insertionSort(unsorted_list))

Java

  1. public class Sort {
  2.     public static void main(String[] args) {
  3.         int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
  4.         insertionSort(unsortedArray);
  5.         System.out.println("After sort: ");
  6.         for (int item : unsortedArray) {
  7.             System.out.print(item + " ");
  8.         }
  9.     }
  11.     public static void insertionSort(int[] array) {
  12.         int len = array.length;
  13.         for (int i = 0; i < len; i++) {
  14.             int index = i, array_i = array[i];
  15.             while (index > 0 && array[index - 1] > array_i) {
  16.                 array[index] = array[index - 1];
  17.                 index -= 1;
  18.             }
  19.             array[index] = array_i;
  21.             /* print sort process */
  22.             for (int item : array) {
  23.                 System.out.print(item + " ");
  24.             }
  25.             System.out.println();
  26.         }
  27.     }
  28. }

实现(C++)：

  1. template<typename T>
  2. void insertion_sort(T arr[], int len) {
  3.     int i, j;
  4.     T temp;
  5.     for (int i = 1; i < len; i++) {
  6.         temp = arr[i];
  7.         for (int j = i - 1; j >= 0 && arr[j] > temp; j--) {
  8.             a[j + 1] = a[j];
  9.         }
  10.         arr[j + 1] = temp;
  11.     }
  12. }

希尔排序

核心：基于插入排序，使数组中任意间隔为h的元素都是有序的，即将全部元素分为h个区域使用插入排序。其实现可类似于插入排序但使用不同增量。更高效的原因是它权衡了子数组的规模和有序性。

实现(C++):

  1. template<typename T>
  2. void shell_sort(T arr[], int len) {
  3.     int gap, i, j;
  4.     T temp;
  5.     for (gap = len >> 1; gap > 0; gap >>= 1)
  6.         for (i = gap; i < len; i++) {
  7.             temp = arr[i];
  8.             for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
  9.                 arr[j + gap] = arr[j];
  10.             arr[j + gap] = temp;
  11.         }
  12. }

Reference