排序算法之快速排序

零、说明

<待更新>

一、先写测试代码

#include <assert.h>
void quicksort(int *arr, int len) {
}

int main() {
  int data[] = {3, 55, -4, 12, -73, 127, 6, 19, 1, 8};
  quicksort(data, sizeof(data) / sizeof(int));
  // test
  assert(data[0] == -73);
  assert(data[1] == -4);
  assert(data[2] == 1);
  assert(data[3] == 3);
  assert(data[4] == 6);
  assert(data[5] == 8);
  assert(data[6] == 12);
  assert(data[7] == 19);
  assert(data[8] == 55);
  assert(data[9] == 127);
  return 0;
}

二、实现Wikipedia的算法

找到Wikipedia的伪代码

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1 )
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] < pivot then
            i := i + 1
            swap A[i] with A[j]
    if A[hi] < A[i + 1] then
        swap A[i + 1] with A[hi]
    return i + 1

可以看到，quicksort的参数和我写的不同，Wikipedia的quicksort可以指定开始元素和结束元素。我认为，一般不需要指定开始元素，把这个三个参数的函数命名为_quicksort，代码实现照抄Wikipedia即可，变量名也保持和这个伪代码相同，除了把A改为arr。
完成代码如下：

include <assert.h>

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

int partition(int *arr, int lo, int hi) {
  int pivot = *(arr + hi);
  int i = lo - 1;
  for (int j = lo; j <= hi - 1; j++) {
    if (*(arr + j) < pivot) {
      i++;
      swap(arr + i, arr + j);
    }
  }
  if (*(arr + hi) < * (arr + i + 1)) {
    swap(arr + i + 1, arr + hi);
  }
  return i + 1;
}

void _quicksort(int *arr, int lo,  int hi) {
  if (lo < hi) {
    int p = partition(arr, lo, hi);
    _quicksort(arr, lo, p - 1);
    _quicksort(arr, p + 1, hi);
  }
}

void quicksort(int *arr, int len) {
  _quicksort(arr, 0, len - 1);
}

int main() {
  int data[] = {3, 55, -4, 12, -73, 127, 6, 19, 1, 8};
  quicksort(data, sizeof(data) / sizeof(int));
  // test
  assert(data[0] == -73);
  assert(data[1] == -4);
  assert(data[2] == 1);
  assert(data[3] == 3);
  assert(data[4] == 6);
  assert(data[5] == 8);
  assert(data[6] == 12);
  assert(data[7] == 19);
  assert(data[8] == 55);
  assert(data[9] == 127);
  return 0;
}

三、性能测试

四、算法优化说明

目前这个代码有两个地方可以改进。
1、接口设计
要排序的数组元素只能为int类型，不能支持更多类型。本文不会对此方面改进，因为本文主要关注算法，而非软件封装，如果你想做，可以参考qsort支持多数据类型的C语言排序](https://www.jianshu.com/p/8ed18338adac)。
2、算法优化
有以下优化思路

• 改进算法
• 把递归转化为迭代
• 和其它排序算法配合

五、算法改进

<待更新>

六、把递归改为迭代

<待更新>

七、和插入排序结合

<待更新>

参考文献

https://en.wikipedia.org/wiki/Quicksort
dietlibc
The GNU C Library (glibc)

相关文章

排序算法之插入排序和希尔排序（shell sort）