Implementation: Quick Sort 2014-08-19

 #include <stdio.h>

 void print(int *a, int start , int end);

 void quick_sort(int *a, int start, int end) {

     if (start +  >= end) return;

     int pv = a[start];

     int p = start, q = end;

     for (;;) {

         while (++p < end   && a[p] < pv);

         while (--q > start && a[q] > pv);

         if (p > q) {

             break;

         }

         int t = a[p];

         a[p] = a[q];

         a[q] = t;

     }

     a[start] = a[p-];

     a[p-] = pv;

     // print(a, start, end);

     quick_sort(a, start, p-);

     quick_sort(a, p, end);

 }

 void print(int *a, int start , int end) {

     for (int i=start; i<end; i++) {

         printf("%d ", a[i]);

     }

     printf("\n");

 }

 int main() {

     int a[] = {};

     int len = sizeof(a) / sizeof(int);

     quick_sort(a, , len);

     for (int i=; i<len; i++) {

         printf("%d ", a[i]);

     }

     return ;

 }

快排还是很容易写错的，记得编程珠玑上说，在提出后的十几年时间少有正确的实现，不断尝试感觉这个实现可以作为自己的模板了，或许可以再加上一个随机化选择的过程。

函数对a[start, end)范围内的数进行一个非降序排序，这个界限划分符合STL的习惯，发现这种半开区间的表示方法确实非常好用

先选取a[start]作为一个哨兵，对剩下的a(start, end)范围内数进行一个比较交换工作，这样从前到后和从后到前的过程就对称了（现在都是开边界了）

设 p = start， q=end为初始状态

在交换过程中

while (++p < end && a[p] < pv);
while (--q > start && a[q] > pv);

首先对下标进行一个自增/自减，这里每次检测都进行这个过程（即使&&后面的条件不满足，防止两个下标在等值处不能移动造成死循环）

当退出循环时，可以确定p指向的是第一个比哨兵值（a[start]）大的元素的下标（有可能这个下标是end，但我们不会直接用它来取值，所以没关系），因而a[p-1]肯定比哨兵值来的小，于是把哨兵值和a[p-1]做一个交换。此时原来的数组已经以a[p-1]为界限被划分成了两部分，a[start, p-1) < a[p-1] < a[p, end)。这样进行一个递归调用即可。

quick_sort(a, start, p-1);
quick_sort(a, p, end);

今天是8月6日，一晃，一年过去了。虽然说上面的方法比较快（采用了双指针），但是练习理解的话还是参照《算法导论》里讲快排的那部分来的比较容易

size_t partition(vector<int>& nums, size_t start, size_t end) {

    if (start >= end) {

        return start;

    }

    int pv = nums[end - ];

    size_t div = start;

    for (size_t i=start; i<end - ; i++) {

        if (nums[i] < pv) {

swap(nums[i], nums[div++]);

        }

    }

    swap(nums[end - ], nums[div]);

    return div;

}

void quick_sort(vector<int>& nums, size_t start, size_t end) {

    if (start >= end) {

        return;

    }

    size_t div = partition(nums, start, end);

    quick_sort(nums, start, div);

    quick_sort(nums, div+, end);

}

partition 函数中[start,div)区间是比pv小的，[div,i)区间是大于等于pv的,[i, end-1)部分是未知大小的（如果区间截止未知大于等于开始未知，则认为这个区间为空），只要记住这个就可以非常稳定的写出代码，不会如第一种要注意太多细节问题。

巴特西

Implementation: Quick Sort 2014-08-19

最新文章

热门文章