最简洁的快速排序

最简洁的快速排序
直接上代码

1. void a_swap(int *a, int *b)
   
2. {
   
3.         int tmp = *a;
   
4.         *a = *b;
   
5.         *b = tmp;
   
6. }
   
7. int a_partition(int a[], int p, int r)
   
8. {
   
9.         int i = p-1;
   
10.         for(int j=p; j<=r-1; j++){
    
11.                 if(a[j] < a[r]){
    
12.                         i ++;
    
13.                         a_swap(&a[i], &a[j]);
    
14.                 }
    
15.         }
    
16.         a_swap(&a[i+1], &a[r]);
    
17.         return i+1;
    
18. }
    
19. 
    
20. void a_qsort(int a[], int p, int r)
    
21. {
    
22.         if(p >= r){
    
23.                 return;
    
24.         }
    
25.         int q = a_partition(a, p, r);
    
26.         a_qsort(a, p, q-1);
    
27.         a_qsort(a, q+1, r);
    
28. }

复制代码

若需要对数组a[n]进行排序，则只需调用
a_qsort(a, 0, n-1);

1.
void a_qsort(int a[], int p, int r);
对数组a的[p, r]闭区间范围内的元素进行排序。

2.
int a_partition(int a[], int p, int r)
以a[r]为pivot，对数组a的[p, r]闭区间范围内的元素进行分区，返回值为pivot所在的位置
该函数首先将[p, r]划分为四个子区间
[p, i]: 该区间内所有的元素都小于pivot
[i+1, j]: 该区间内所有的元素都大于于pivot
[j+1, r-1]: 该区间内的元素尚未被划分
[r, r]: pivot
循环结束后有 j=r, 此时[j+1, r-1]区间为空，即所有的元素都已经完成划分。此时，只需要交换a[r]与a[i+1]，就可以保证所有小于pivot的元素都在其左边，大于pivot的元素都在其右边。

此版本的分区默认采用尾元素为pivot，并可以轻松扩展为其他方式，只需要在函数开始前，将pivot交换到尾部即可

以上程序参考自《算法导论》，个人认为是最简洁的快排实现了。

elfandi 发表于 2013-11-9 16:01
swap不用异或？- -

LZ这里可以用， 但建议不要用。 因为很多时候不知道swap会不会是针对同一个引用进行， 这样就变0 了。比如用了类似我的版本的partitioning的快排就不能了

另外包括这种swap也是。 如果a,b是同一个引用就废了。如果之前加一个判断还不如用经典的呢。
a = a + b
b = a - b;
a = a - b;

yabirthday 发表于 2020-5-3 15:58
[mw_shl_code=cpp,true]int partion(vector& nums, int left, int right) {
    int pivot = nums[left],  ...

挑个小刺，partition拼错了~

快排什么版本都见过， 我就写这种。 不见得比我简洁吧.

1. 
   
2. private void qsort(int[] a, int start, int end) {   
   
3.    if (end <= start) return; // 其实这句可有可无, 只要调用的时候不故意出错
   
4.   
   
5.    int left = start;
   
6.    int right = end;
   
7.    int pivot = a[left + (right - left) / 2];
   
8. 
   
9.    // selection
   
10.    while (left <= right) {
    
11.        while (a[left] < pivot) left ++;
    
12.        while (a[right] > pivot) right --;
    
13.        if (left <= right) {
    
14.          int tmp = a[left];
    
15.          a[left] = a[right];
    
16.          a[right] = tmp;
    
17.          left ++;
    
18.          right --;
    
19.        }
    
20.    }
    
21. 
    
22.    // divide
    
23.    if (left < end) qsort(a, left, end);
    
24.    if (right > start) qsort(a, start, right);
    
25. }
    

复制代码

同ls，敢问这代码跑过么

这种编程风格，我是面试官，我肯定把你挂了。变量名都是单个字母，看都看晕了。

ytsr 发表于 2013-11-9 16:18
这种编程风格，我是面试官，我肯定把你挂了。变量名都是单个字母，看都看晕了。

效率和可读性之间要取舍啊，最近也很犹豫这个问题。。
据说业界先写成可读性高的代码，然后改写，把长的变量名还有缩进什么的全部去掉。。

EroicaCMCS 发表于 2013-11-9 19:45
效率和可读性之间要取舍啊，最近也很犹豫这个问题。。
据说业界先写成可读性高的代码，然后改写，把长的 ...

变量名和效率没啥关系，最多是多打几个字罢了。
也不用太长，比如这里的p,r 至少也得换成 begin,end   head,tail   front, tail 之类的吧。

swap不用异或？- -

北美农民 发表于 2013-11-10 05:17
LZ这里可以用， 但建议不要用。 因为很多时候不知道swap会不会是针对同一个引用进行， 这样就变0 了。比如 ...

赞