快速排序的疑惑

Question

快速排序classpivot

Answer 1

你自己调试下看看代码运行的流程不就明白了。实例如下：
package test;import java.util.Arrays;public class Test {    public int[] sort(int left, int right, int[] arr) {        int l = left;
        int r = right;
        int pivot = arr[(left + right) / 2];
        int temp;
        while (l < r) {
            while (arr[l] < pivot) {
                l++;
            }
            while (arr[r] > pivot) {
                r--;
            }
            if (l >= r) {
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            if (arr[l] == pivot) {
                --r;
            }
            if (arr[r] == pivot) {
                ++l;
            }
        }
        if (l == r) {
            l++;
            r--;
        }
        if (left < r) {
            sort(left, r, arr);
        }
        if (right > l) {
            sort(l, right, arr);
        }
        return arr;
    }    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 6, 3, 7, 1, 9, 4, 0};
        Test t = new Test();
        System.out.println(Arrays.toString(t.sort(0, 9, arr)));
    }
}

Answer 2

你要不怕麻烦的话，放一个数组，一行一行的手动执行过去，最后你就懂了。
我当初就没看懂，做java一年了现在也还看不懂。

Answer 3

http://zh.wikipedia.org/wiki/快速排序

Answer 4

  public static void sort(int left,int right, int[] arr){          int l=left;  //左边从第几个开始排序  (0代表第一个)
          int r=right; //右边排序到底多少个 (同样是索引,比如3代表排序到第四个数,后面的就不排序了)
          int pivot=arr[(left+right)/2];//取中间的数出来
          int temp=0;
          while(l<r){//这里l<r 是说左边的数大于右边的数  也就是排序的位置是从左往右的
                while(arr[l]<pivot)    l++; //从arr[l]开始与中间数开始比较 如果比中间数小那么继续 并l+1 
                while(arr[r]>pivot)    r--;//从arr[r]开始与中间数开始比较 如果比中间数大 那么继续 并 r-1 
                if(l>=r) break; //如果l>=r 循环中断  跳出循环 最外层的while循环 （ while(l<r)）;
                temp=arr[l]; //这里是对于arr[l]>=pivot进行处理 也就是从左往右第一次出现arr[l]大于中间的数pivot的数 并把这个数赋值给temp  这里temp就是arr[l]的值了
                arr[l]=arr[r];// 同上  这里的arr[r]也就是从右往左第一次出现arr[r]要<=中间的数pivot的数 并把这个数赋值给arr[l] 这里arr[l]的值就是arr[r]的值了
                arr[r]=temp;//最后再把temp的值赋值给arr[r] 因为temp的值已经是arr[l]了  所以这里arr[r]的值就变成了arr[l]的值       也就是根据上两行代码把arr[l]和arr[r]的值交换了
                if(arr[l]==pivot)  --r;//这里是如果arr[l]也就是换之前的arr[r]的值 如果等于中间的数pivot 那么就把 r-1 因为arr[l]和pivot是相等的 那么这两个数就都是一样的了 并把循环的范围缩小了一点
                if(arr[r]==pivot)  ++l;//原理同上
          }
          if(l==r){
                 l++;
                 r--; 
          }
          if(left<r)  sort(left,r,arr);
          if(right>l)  sort(l,right,arr);    }