首页 > 代码库 > Implementation: Quick Sort 2014-08-19
Implementation: Quick Sort 2014-08-19
1 #include <stdio.h> 2 3 void print(int *a, int start , int end); 4 5 void quick_sort(int *a, int start, int end) { 6 if (start + 1 >= end) return; 7 int pv = a[start]; 8 int p = start, q = end; 9 for (;;) {10 while (++p < end && a[p] < pv);11 while (--q > start && a[q] > pv);12 if (p > q) {13 break;14 }15 int t = a[p];16 a[p] = a[q];17 a[q] = t;18 }19 20 a[start] = a[p-1];21 a[p-1] = pv;22 23 // print(a, start, end);24 25 quick_sort(a, start, p-1);26 quick_sort(a, p, end);27 }28 29 void print(int *a, int start , int end) {30 for (int i=start; i<end; i++) {31 printf("%d ", a[i]);32 }33 printf("\n");34 }35 36 int main() {37 int a[] = {2};38 39 int len = sizeof(a) / sizeof(int);40 quick_sort(a, 0, len);41 42 for (int i=0; i<len; i++) {43 printf("%d ", a[i]);44 }45 return 0;46 }
快排还是很容易写错的,记得编程珠玑上说,在提出后的十几年时间少有正确的实现,不断尝试感觉这个实现可以作为自己的模板了,或许可以再加上一个随机化选择的过程。
函数对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);
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。