排序 · Codelet

简单排序

选择排序

简单选择排序每次找出最小（最大）的元素，并依次排列

void selection_sort(int arr[], int length) {
  int min;
  for (int i = 0; i < length; i++) {
    min = i;
    for (int j = i + 1; j < length; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }
    swap(arr[i], arr[min]);
  }
}

简单选择排序的算法复杂度为\(O(n^2)\)

插入排序

简单插入排序假设初始序列是有序的，每次都将新元素插入到合适的位置，保持序列仍然有序

void insertion_sort(int arr[], int length) {
  for (int i = 1; i < length; i++) {
    // move arr[i] to the left
    int el = arr[i]; // cache arr[j + 1]
    for (int j = i - 1; j >= 0 && el < arr[j]; j--) {
      swap(arr[j], arr[j + 1]);
    }
  }
}

简单插入排序的算法复杂度在平均情况下为\(O(n^2)\)，但对于有序的数据，新插入的元素不需要移动，因此在这种最优情况下的复杂度为\(O(n)\)

冒泡排序

冒泡排序也是简单排序的一种，根据冒泡的方向每次找出一个最大（最小）值

void bubble_sort(int arr[], int length) {
  for (int i = 0; i < length - 1; i++) {
    for (int j = length - 1; j > i; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr[j], arr[j - 1]);
      }
    }
  }
}

冒泡排序的算法复杂度为\(O(n^2)\)

以上的排序算法实现都是稳定的

改进算法

希尔排序

希尔排序又称递减增量排序算法，算法通过一个步长将元素分组，组内的元素分别排序，然后逐步递减步长至 1，此时整个序列必然有序，希尔排序是一种改进后的插入排序

void shell_sort(int arr[], int length) {
  int gap = 1;
  while (gap < length / 3) {
    gap = gap * 3 + 1; // gap sequence: 1 4 13 40
  }
  for (; gap >= 1; gap /= 3) {
    for (int i = 0; i < gap; i++) {
      for (int j = i + gap; j < length; j += gap) {
        for (int k = j - gap; k >= 0 && arr[k + gap] < arr[k]; k -= gap) {
          swap(arr[k], arr[k + gap]);
        }
      }
    }
  }
}

通过四重循环可以很快的实现，但更常见的一个版本是通过三重循环实现的。因为在上面的算法中，i作为组内元素的偏移量，j作为组的起始位置，i和j共同完成了对arr[gap..length-1]的遍历，因此我们可以折叠这两层循环，用一层循环代替，两种实现的算法复杂度是完全一样的

void shell_sort(int arr[], int length) {
  int gap = 1;
  while (gap < length / 3) {
    gap = gap * 3 + 1; // gap sequence: 1 4 13 40
  }
  for (; gap >= 1; gap /= 3) {
    for (int i = gap; i < length; i++) {
      for (int j = i - gap; j >= 0 && arr[j + gap] < arr[j]; j -= gap) {
        swap(arr[j], arr[j + gap]);
      }
    }
  }
}

希尔排序的算法复杂度与步长序列的选取有关，一般最坏不超过\(O(n^2)\)，上述算法实现的时间复杂度为\(O(n^{3/2})\)，希尔排序不需要额外的空间，但很显然它是不稳定的排序算法

堆排序

堆是一种集合数据类型，它具有两个性质：1.堆是一棵完全二叉树 2.任意结点的值都不大于（或不小于）其子结点的值，称为小根堆（或大根堆）

堆排序可以分为两个阶段：1.建堆阶段，依次插入元素并维护堆的性质 2.提取阶段，每次从根取出最值，并调整堆，直到堆为空，堆排序是一种改进后的选择排序

在堆排序中，堆一般采用顺序表来实现，其中根元素的下标为1，左孩子下标2n，右孩子下标2n+1，双亲结点下标n/2，下标为0的元素不使用

inline int left(int i) { return i * 2; }
inline int right(int i) { return i * 2 + 1; }
inline int parent(int i) { return i / 2; }

void _build_heap(int heap[], int src[], int length) {
  for (int i = 0; i < length; i++) {
    int j = i + 1;
    int p;
    heap[j] = src[i];
    while ((p = parent(j)) > 0 && heap[p] > heap[j]) {
      swap(heap[p], heap[j]);
      j = p;
    }
  }
}

void _adjust_heap(int heap[], int size) {
  int p = 1;
  int c;
  while (left(p) <= size) {
    c = left(p);
    if (right(p) <= size && heap[right(p)] < heap[c]) {
      c = right(p);
    }
    if (heap[p] <= heap[c]) {
      break;
    }
    swap(heap[p], heap[c]);
    p = c;
  }
}

void heap_sort(int arr[], int length) {
  int* heap = new int[length + 1];
  _build_heap(heap, arr, length);
  for (int i = 0; i < length; i++) {
    arr[i] = heap[1];
    swap(heap[1], heap[length - i]);
    _adjust_heap(heap, length - i - 1);
  }
  delete[] heap;
}

上面的实现借助了一个n+1的额外空间来储存堆数据，其实堆数据可以和原数据共用同一段空间，下面是优化过的算法实现

inline int left(int i) { return i * 2 + 1; }
inline int right(int i) { return i * 2 + 2; }
inline int parent(int i) { return (i - 1) / 2; }

void _heapify(int arr[], int n, int size) {
  // max heap
  int c;
  while (left(n) < size) {
    c = left(n);
    if (right(n) < size && arr[right(n)] > arr[c]) {
      c = right(n);
    }
    if (arr[n] >= arr[c]) {
      break;
    }
    swap(arr[n], arr[c]);
    n = c;
  }
}

void heap_sort(int arr[], int length) {
  for (int i = length / 2 - 1; i >= 0; i--) {
    _heapify(arr, i, length);
  }
  for (int j = length - 1; j > 0; j--) {
    swap(arr[0], arr[j]);
    _heapify(arr, 0, j);
  }
}

堆排序在最坏情况下的算法复杂度为\(O(n log(n))\)，上述的实现不需要额外空间，它是不稳定的

分治法

归并排序

归并排序的思想是通过合并两个（或多个）已排序的子序列，从而得到更大的子序列，直到整个序列有序

void _merge(int arr[], int aux[], int low, int mid, int high) {
  copy(arr + low, arr + high + 1, aux + low);
  int i = low;
  int j = mid + 1;
  for (int k = low; k <= high; k++) {
    if (i > mid) {
      arr[k] = aux[j++];
    } else if (j > high) {
      arr[k] = aux[i++];
    } else if (aux[i] < aux[j]) {
      arr[k] = aux[i++];
    } else {
      arr[k] = aux[j++];
    }
  }
}

void _merge_sort(int arr[], int aux[], int low, int high) {
  if (low >= high) { return; }
  int mid = low + (high - low) / 2;
  _merge_sort(arr, aux, low, mid);
  _merge_sort(arr, aux, mid + 1, high);
  _merge(arr, aux, low, mid, high);
}

void merge_sort(int arr[], int length) {
  int* aux = new int[length];
  _merge_sort(arr, aux, 0, length - 1);
  delete[] aux;
}

归并排序算法的时间复杂度为\(O(n log(n))\)，但需要\(O(n)\)的额外空间，归并排序是稳定的

快速排序

快排的思想是先选择一个元素作为基准，然后将所有小于基准的元素放左边，所有大于基准的元素放右边，使基准处在最终的位置上，然后对左右子序列分别递归

int _partition(int arr[], int low, int high) {
  // invariant:
  // any arr[low+1..m] < pivot
  // any arr[m+1..i-1] >= pivot
  int pivot = arr[low];
  int m = low;
  for (int i = low + 1; i <= high; i++) {
    if (arr[i] < pivot) {
      m++;
      swap(arr[m], arr[i]);
    }
  }
  swap(arr[low], arr[m]);
  return m;
}

void _quick_sort(int arr[], int low, int high) {
  if (low < high) {
    int middle = _partition(arr, low, high);
    _quick_sort(arr, low, middle - 1);
    _quick_sort(arr, middle + 1, high);
  }
}

void quick_sort(int arr[], int length) {
  _quick_sort(arr, 0, length - 1);
}

快速排序算法的平均复杂度为\(O(n log(n))\)，但在最坏情况下（如序列有序，每次选取的基准值都为最小值）会退化为\(O(n^2)\)的复杂度

上述算法实现是不稳定的，原因是swap(arr[m], arr[i])操作会破坏arr[low+1..m]子序列中相等元素之间的相对顺序

上述算法在输入序列随机性很强时性能非常好，但对于包含大量重复元素的序列，算法会把与基准相等的元素都置于右侧，导致不均衡的划分

其实只要能达到分离元素的目的，划分算法可以有任意的实现，下面是教科书上常见的一种，不过也具有上面一样的缺点

int _partition(int arr[], int low, int high) {
  int pivot = arr[low];
  int i = low;
  int j = high;
  do {
    while (i < j && arr[j] >= pivot) { j--; }
    arr[i] = arr[j];
    while (i < j && arr[i] <= pivot) { i++; }
    arr[j] = arr[i];
  } while (i < j);
  // i == j
  arr[i] = pivot;
  return i;
}

针对重复元素的问题，我们可以采用下面这种划分算法

int _partition(int arr[], int low, int high) {
  int pivot = arr[low];
  int i = low;
  int j = high + 1;
  while (true) {
    do { i++; } while(arr[i] < pivot && i < high); // 1 2
    do { j--; } while(arr[j] > pivot && j > low);
    if (i >= j) { break; }
    swap(arr[i], arr[j]);
  }
  swap(arr[low], arr[j]); // 3
  return j;
}

有三点需要说明：

游标和基准的比较使用严格小于/大于，从而可以划分的更均衡
因为选取的是最左边的元素作基准，因此向右扫描时需要防止越界，向左扫描时其实不需要
i和j交叉之后，j反而会指向较小的元素，因此基准和j做交换

上面的算法对相等的元素会做多余的交换操作，还有继续优化的空间。事实上很多语言所提供的排序库函数都很复杂，不仅可以很好的处理重复元素，还可以针对小规模数据使用插入排序进行优化，以后有时间可以详细介绍一下

最后附上测试用例

TEST(Main, Basic) {
  int arr[10] = {1, 8, 0, 7, 2, 5, 4, 9, 3, 6};
  sort(arr, 10);
  cout << arr << endl;
}

TEST(Main, Random) {
  srandom(time(0));
  int sizes[5] = {200000, 500, 10, 1, 0};
  for (int s = 0; s < 5; s++) {
    int size = sizes[s];
    vector<int> arr;
    for (int i = 0; i < size; i++) {
      int value = random() % 100;
      arr.push_back(value);
    }
    sort(arr.data(), size);
    for (int i = 0; i < size - 1; i++) {
      if (!(arr[i] <= arr[i + 1])) {
        EXPECT_TRUE(arr[i] <= arr[i + 1]);
        break;
      }
    }
  }
}

参考资料：
[1] wikipedia - ShellSort
[2] wikipedia - HeapSort
[3] R. Sedgewick and K. Wayne Algorithms-4th - QuickSort

Codelet Keep code simple stupid

排序