快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。 [1] 

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 [1]

百度百科给出来三种进阶式快排方法

方法一：

public class QuickSort

{

    public static int[] qsort(int arr[],int start,int end) {        

        int pivot = arr[start];        

        int i = start;        

        int j = end;  

        System.out.println("arr[start]=" + arr[start] +",start=" + start + ",arr[end]=" +arr[end] + ",end=" + end);

        System.out.println("=====================");

        while (i<j) {            

            while ((i<j)&&(arr[j]>pivot)) {                

                j--;            

            }            

            while ((i<j)&&(arr[i]<pivot)) {                

                i++;            

            }            

            if ((arr[i]==arr[j])&&(i<j)) {                

                i++;            

            } else {  

                System.out.println("arr[i]=" + arr[i] +",i=" + i + ",arr[j]=" +arr[j] + ",j=" + j);

                int temp = arr[i];                

                arr[i] = arr[j];                

                arr[j] = temp;            

            }  

            for (int j2 = 0; j2 < arr.length; j2++)

            {

                System.out.print(arr[j2] + " ");

            }

            System.out.println();

        }        

        if (i-1>start) arr=qsort(arr,start,i-1);        

        if (j+1<end) arr=qsort(arr,j+1,end);        

        return (arr);

    }    

    public static void main(String[] args) {        

        int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};        

        int len = arr.length-1;        

        arr=qsort(arr,0,len);        

        for (int i:arr) {            

            System.out.print(i+" ");        

        }    

    }  

}

输出结果：

arr[start]=3,start=0,arr[end]=12321,end=18

=====================

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[start]=3,start=0,arr[end]=3,end=1

=====================

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[start]=7,start=3,arr[end]=12321,end=18

=====================

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[i]=9,i=4,arr[j]=7,j=12

3 3 3 7 7 122344 4656 34 34 4656 5 6 9 8 9 343 57765 23 12321

arr[i]=7,i=4,arr[j]=6,j=11

3 3 3 7 6 122344 4656 34 34 4656 5 7 9 8 9 343 57765 23 12321

arr[i]=122344,i=5,arr[j]=7,j=11

3 3 3 7 6 7 4656 34 34 4656 5 122344 9 8 9 343 57765 23 12321

arr[i]=7,i=5,arr[j]=5,j=10

3 3 3 7 6 5 4656 34 34 4656 7 122344 9 8 9 343 57765 23 12321

arr[i]=4656,i=6,arr[j]=7,j=10

3 3 3 7 6 5 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[i]=7,i=6,arr[j]=7,j=6

3 3 3 7 6 5 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[start]=7,start=3,arr[end]=5,end=5

=====================

arr[i]=7,i=3,arr[j]=5,j=5

3 3 3 5 6 7 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[i]=7,i=5,arr[j]=7,j=5

3 3 3 5 6 7 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[start]=5,start=3,arr[end]=6,end=4

=====================

arr[i]=5,i=3,arr[j]=5,j=3

3 3 3 5 6 7 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[start]=34,start=7,arr[end]=12321,end=18

=====================

arr[i]=34,i=7,arr[j]=23,j=17

3 3 3 5 6 7 7 23 34 4656 4656 122344 9 8 9 343 57765 34 12321

3 3 3 5 6 7 7 23 34 4656 4656 122344 9 8 9 343 57765 34 12321

arr[i]=4656,i=9,arr[j]=34,j=17

3 3 3 5 6 7 7 23 34 34 4656 122344 9 8 9 343 57765 4656 12321

arr[i]=34,i=9,arr[j]=9,j=14

3 3 3 5 6 7 7 23 34 9 4656 122344 9 8 34 343 57765 4656 12321

arr[i]=4656,i=10,arr[j]=34,j=14

3 3 3 5 6 7 7 23 34 9 34 122344 9 8 4656 343 57765 4656 12321

arr[i]=34,i=10,arr[j]=8,j=13

3 3 3 5 6 7 7 23 34 9 8 122344 9 34 4656 343 57765 4656 12321

arr[i]=122344,i=11,arr[j]=34,j=13

3 3 3 5 6 7 7 23 34 9 8 34 9 122344 4656 343 57765 4656 12321

arr[i]=34,i=11,arr[j]=9,j=12

3 3 3 5 6 7 7 23 34 9 8 9 34 122344 4656 343 57765 4656 12321

arr[i]=34,i=12,arr[j]=34,j=12

3 3 3 5 6 7 7 23 34 9 8 9 34 122344 4656 343 57765 4656 12321

arr[start]=23,start=7,arr[end]=9,end=11

=====================

arr[i]=23,i=7,arr[j]=9,j=11

3 3 3 5 6 7 7 9 34 9 8 23 34 122344 4656 343 57765 4656 12321

arr[i]=34,i=8,arr[j]=23,j=11

3 3 3 5 6 7 7 9 23 9 8 34 34 122344 4656 343 57765 4656 12321

arr[i]=23,i=8,arr[j]=8,j=10

3 3 3 5 6 7 7 9 8 9 23 34 34 122344 4656 343 57765 4656 12321

arr[i]=23,i=10,arr[j]=23,j=10

3 3 3 5 6 7 7 9 8 9 23 34 34 122344 4656 343 57765 4656 12321

arr[start]=9,start=7,arr[end]=9,end=9

=====================

3 3 3 5 6 7 7 9 8 9 23 34 34 122344 4656 343 57765 4656 12321

arr[i]=9,i=9,arr[j]=9,j=9

3 3 3 5 6 7 7 9 8 9 23 34 34 122344 4656 343 57765 4656 12321

arr[start]=9,start=7,arr[end]=8,end=8

=====================

arr[i]=9,i=7,arr[j]=8,j=8

3 3 3 5 6 7 7 8 9 9 23 34 34 122344 4656 343 57765 4656 12321

arr[i]=9,i=8,arr[j]=9,j=8

3 3 3 5 6 7 7 8 9 9 23 34 34 122344 4656 343 57765 4656 12321

arr[start]=122344,start=13,arr[end]=12321,end=18

=====================

arr[i]=122344,i=13,arr[j]=12321,j=18

3 3 3 5 6 7 7 8 9 9 23 34 34 12321 4656 343 57765 4656 122344

arr[i]=122344,i=18,arr[j]=122344,j=18

3 3 3 5 6 7 7 8 9 9 23 34 34 12321 4656 343 57765 4656 122344

arr[start]=12321,start=13,arr[end]=4656,end=17

=====================

arr[i]=12321,i=13,arr[j]=4656,j=17

3 3 3 5 6 7 7 8 9 9 23 34 34 4656 4656 343 57765 12321 122344

arr[i]=57765,i=16,arr[j]=12321,j=17

3 3 3 5 6 7 7 8 9 9 23 34 34 4656 4656 343 12321 57765 122344

arr[i]=12321,i=16,arr[j]=12321,j=16

3 3 3 5 6 7 7 8 9 9 23 34 34 4656 4656 343 12321 57765 122344

arr[start]=4656,start=13,arr[end]=343,end=15

=====================

arr[i]=4656,i=13,arr[j]=343,j=15

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 57765 122344

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 57765 122344

arr[start]=343,start=13,arr[end]=4656,end=14

=====================

arr[i]=343,i=13,arr[j]=343,j=13

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 57765 122344

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 57765 122344

第二种方法：

public class QuickSort2

{

    public static int[] qsort(int arr[],int start,int end) {        

        int i=start+1,j=end;

        int key=arr[start];

        if(start==end) return (arr);

        System.out.println("arr[start]=" + arr[start] +",start=" + start + ",arr[end]=" +arr[end] + ",end=" + end);

        System.out.println("=====================");

        /*从i++和j--两个方向搜索不满足条件的值并交换

         *

         *条件为：i++方向小于key，j--方向大于key

         */

        while(true)

        {

            while(arr[j]>key)j--;

            while(arr[i]<key&&i<j)i++;

            System.out.println("arr[i]=" + arr[i] +",i=" + i + ",arr[j]=" +arr[j] + ",j=" + j);

            if(i>=j)break;

            int temp = arr[i];                

            arr[i] = arr[j];                

            arr[j] = temp;

            if(arr[i]==key)

            {

                j--;

            }else{

                i++;

            }

        }

        for (int j2 = 0; j2 < arr.length; j2++)

        {

            System.out.print(arr[j2] + " ");

        }

        System.out.println();

        /*关键数据放到‘中间’*/

        System.out.println("arr[start]=" + arr[start] +",start=" + start + ",arr[j]=" +arr[j] + ",j=" + j);

        int temp = arr[start];                

        arr[start] = arr[j];                

        arr[j] = temp;

        for (int j2 = 0; j2 < arr.length; j2++)

        {

            System.out.print(arr[j2] + " ");

        }

        System.out.println();

        if(start<i-1)

        {

            qsort(arr, start, i-1);

        }

        if(j+1<end)

        {

            qsort(arr, j+1, end);

        }

        return arr;  

    }    

    public static void main(String[] args) {        

        int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};        

        int len = arr.length-1;        

        arr=qsort(arr,0,len);        

        for (int i:arr) {            

            System.out.print(i+" ");        

        }    

    }

}

以start位置的数字为key值，从start+1开始进行快排最终获取start位置数字所在的位置进行交换，最终达成数据的快速排序。

输出结果：

arr[start]=3,start=0,arr[end]=12321,end=18

=====================

arr[i]=3,i=1,arr[j]=3,j=2

arr[i]=3,i=1,arr[j]=3,j=1

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[start]=3,start=0,arr[j]=3,j=1

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[start]=3,start=2,arr[end]=12321,end=18

=====================

arr[i]=7,i=3,arr[j]=3,j=2

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[start]=3,start=2,arr[j]=3,j=2

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[start]=7,start=3,arr[end]=12321,end=18

=====================

arr[i]=9,i=4,arr[j]=7,j=12

arr[i]=7,i=4,arr[j]=6,j=11

arr[i]=122344,i=5,arr[j]=7,j=11

arr[i]=7,i=5,arr[j]=5,j=10

arr[i]=4656,i=6,arr[j]=7,j=10

arr[i]=7,i=6,arr[j]=7,j=6

3 3 3 7 6 5 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[start]=7,start=3,arr[j]=7,j=6

3 3 3 7 6 5 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[start]=7,start=3,arr[end]=5,end=5

=====================

arr[i]=5,i=5,arr[j]=5,j=5

3 3 3 7 6 5 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[start]=7,start=3,arr[j]=5,j=5

3 3 3 5 6 7 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[start]=5,start=3,arr[end]=6,end=4

=====================

arr[i]=6,i=4,arr[j]=5,j=3

3 3 3 5 6 7 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[start]=5,start=3,arr[j]=5,j=3

3 3 3 5 6 7 7 34 34 4656 4656 122344 9 8 9 343 57765 23 12321

arr[start]=34,start=7,arr[end]=12321,end=18

=====================

arr[i]=34,i=8,arr[j]=23,j=17

arr[i]=4656,i=9,arr[j]=34,j=17

arr[i]=34,i=9,arr[j]=9,j=14

arr[i]=4656,i=10,arr[j]=34,j=14

arr[i]=34,i=10,arr[j]=8,j=13

arr[i]=122344,i=11,arr[j]=34,j=13

arr[i]=34,i=11,arr[j]=9,j=12

arr[i]=34,i=12,arr[j]=34,j=12

3 3 3 5 6 7 7 34 23 9 8 9 34 122344 4656 343 57765 4656 12321

arr[start]=34,start=7,arr[j]=34,j=12

3 3 3 5 6 7 7 34 23 9 8 9 34 122344 4656 343 57765 4656 12321

arr[start]=34,start=7,arr[end]=9,end=11

=====================

arr[i]=9,i=11,arr[j]=9,j=11

3 3 3 5 6 7 7 34 23 9 8 9 34 122344 4656 343 57765 4656 12321

arr[start]=34,start=7,arr[j]=9,j=11

3 3 3 5 6 7 7 9 23 9 8 34 34 122344 4656 343 57765 4656 12321

arr[start]=9,start=7,arr[end]=8,end=10

=====================

arr[i]=23,i=8,arr[j]=8,j=10

arr[i]=9,i=9,arr[j]=9,j=9

3 3 3 5 6 7 7 9 8 9 23 34 34 122344 4656 343 57765 4656 12321

arr[start]=9,start=7,arr[j]=9,j=9

3 3 3 5 6 7 7 9 8 9 23 34 34 122344 4656 343 57765 4656 12321

arr[start]=9,start=7,arr[end]=8,end=8

=====================

arr[i]=8,i=8,arr[j]=8,j=8

3 3 3 5 6 7 7 9 8 9 23 34 34 122344 4656 343 57765 4656 12321

arr[start]=9,start=7,arr[j]=8,j=8

3 3 3 5 6 7 7 8 9 9 23 34 34 122344 4656 343 57765 4656 12321

arr[start]=122344,start=13,arr[end]=12321,end=18

=====================

arr[i]=12321,i=18,arr[j]=12321,j=18

3 3 3 5 6 7 7 8 9 9 23 34 34 122344 4656 343 57765 4656 12321

arr[start]=122344,start=13,arr[j]=12321,j=18

3 3 3 5 6 7 7 8 9 9 23 34 34 12321 4656 343 57765 4656 122344

arr[start]=12321,start=13,arr[end]=4656,end=17

=====================

arr[i]=57765,i=16,arr[j]=4656,j=17

arr[i]=57765,i=17,arr[j]=4656,j=16

3 3 3 5 6 7 7 8 9 9 23 34 34 12321 4656 343 4656 57765 122344

arr[start]=12321,start=13,arr[j]=4656,j=16

3 3 3 5 6 7 7 8 9 9 23 34 34 4656 4656 343 12321 57765 122344

arr[start]=4656,start=13,arr[end]=12321,end=16

=====================

arr[i]=4656,i=14,arr[j]=343,j=15

arr[i]=4656,i=15,arr[j]=4656,j=15

3 3 3 5 6 7 7 8 9 9 23 34 34 4656 343 4656 12321 57765 122344

arr[start]=4656,start=13,arr[j]=4656,j=15

3 3 3 5 6 7 7 8 9 9 23 34 34 4656 343 4656 12321 57765 122344

arr[start]=4656,start=13,arr[end]=343,end=14

=====================

arr[i]=343,i=14,arr[j]=343,j=14

3 3 3 5 6 7 7 8 9 9 23 34 34 4656 343 4656 12321 57765 122344

arr[start]=4656,start=13,arr[j]=343,j=14

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 57765 122344

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 57765 122344

第三种方式：

public class QuickSort3

{

    public static void qsort(int arr[], int start, int end)

    {

        int i = start, j = end;

        int key = arr[start];

        System.out.println("arr[start]=" + arr[start] +",start=" + start + ",arr[end]=" +arr[end] + ",end=" + end);

        System.out.println("=====================");

        while (i < j)

        {

            /* 按j--方向遍历目标数组，直到比key小的值为止 */

            while (j > i && arr[j] >= (key))

            {

                j--;

            }

            if (i < j)

            {

                System.out.println("arr[i]=" + arr[i] +",i=" + i + ",arr[j]=" +arr[j] + ",j111=" + j);

                /* targetArr[i]已经保存在key中，可将后面的数填入 */

                arr[i] = arr[j];

                i++;

            }

            for (int j2 = 0; j2 < arr.length; j2++)

            {

                System.out.print(arr[j2] + " ");

            }

            System.out.println();

            /* 按i++方向遍历目标数组，直到比key大的值为止 */

            while (i < j && arr[i] <= (key))

            /*

             * 此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，

             * 那么这个小于等于的作用就会使下面的if语句少执行一亿次。

             */

            {

                i++;

            }

            if (i < j)

            {

                System.out.println("arr[i]=" + arr[i] +",i=" + i + ",arr[j]=" +arr[j] + ",j2222=" + j);

                /* targetArr[j]已保存在targetArr[i]中，可将前面的值填入 */

                arr[j] = arr[i];

                j--;

            }

            for (int j2 = 0; j2 < arr.length; j2++)

            {

                System.out.print(arr[j2] + " ");

            }

            System.out.println();

        }

        /* 此时i==j */

        arr[i] = key;// 应加判断

        for (int j2 = 0; j2 < arr.length; j2++)

        {

            System.out.print(arr[j2] + " ");

        }

        System.out.println();

        /* 递归调用，把key前面的完成排序 */

        if(start<i-1) qsort(arr, start, i - 1);

        /* 递归调用，把key后面的完成排序 */

        if(j+1<end) qsort(arr, j + 1, end);

        // 两个递归应加判断

    }

    public static void main(String[] args) {        

        int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};        

        int len = arr.length-1;        

        qsort(arr,0,len);        

        for (int i:arr) {            

            System.out.print(i+" ");        

        }    

    }

}

第三种方法更像是一种层层推进式的冒泡算法

从左边第一个数字开始 一个数字一个数字找出它应该属于的位置 保证这个数字所在的位置左边都是小于等于自己的数 右边都是大于等于自己的数字 以此一步一步推进 最终得出正确顺序的数组来

输出结果：

arr[start]=3,start=0,arr[end]=12321,end=18

=====================

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[start]=3,start=1,arr[end]=12321,end=18

=====================

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[start]=3,start=2,arr[end]=12321,end=18

=====================

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

3 3 3 7 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[start]=7,start=3,arr[end]=12321,end=18

=====================

arr[i]=7,i=3,arr[j]=6,j111=11

3 3 3 6 9 122344 4656 34 34 4656 5 6 7 8 9 343 57765 23 12321

arr[i]=9,i=4,arr[j]=6,j2222=11

3 3 3 6 9 122344 4656 34 34 4656 5 9 7 8 9 343 57765 23 12321

arr[i]=9,i=4,arr[j]=5,j111=10

3 3 3 6 5 122344 4656 34 34 4656 5 9 7 8 9 343 57765 23 12321

arr[i]=122344,i=5,arr[j]=5,j2222=10

3 3 3 6 5 122344 4656 34 34 4656 122344 9 7 8 9 343 57765 23 12321

3 3 3 6 5 122344 4656 34 34 4656 122344 9 7 8 9 343 57765 23 12321

3 3 3 6 5 122344 4656 34 34 4656 122344 9 7 8 9 343 57765 23 12321

3 3 3 6 5 7 4656 34 34 4656 122344 9 7 8 9 343 57765 23 12321

arr[start]=6,start=3,arr[end]=5,end=4

=====================

arr[i]=6,i=3,arr[j]=5,j111=4

3 3 3 5 5 7 4656 34 34 4656 122344 9 7 8 9 343 57765 23 12321

3 3 3 5 5 7 4656 34 34 4656 122344 9 7 8 9 343 57765 23 12321

3 3 3 5 6 7 4656 34 34 4656 122344 9 7 8 9 343 57765 23 12321

arr[start]=4656,start=6,arr[end]=12321,end=18

=====================

arr[i]=4656,i=6,arr[j]=23,j111=17

3 3 3 5 6 7 23 34 34 4656 122344 9 7 8 9 343 57765 23 12321

arr[i]=122344,i=10,arr[j]=23,j2222=17

3 3 3 5 6 7 23 34 34 4656 122344 9 7 8 9 343 57765 122344 12321

arr[i]=122344,i=10,arr[j]=343,j111=15

3 3 3 5 6 7 23 34 34 4656 343 9 7 8 9 343 57765 122344 12321

3 3 3 5 6 7 23 34 34 4656 343 9 7 8 9 343 57765 122344 12321

3 3 3 5 6 7 23 34 34 4656 343 9 7 8 9 4656 57765 122344 12321

arr[start]=23,start=6,arr[end]=9,end=14

=====================

arr[i]=23,i=6,arr[j]=9,j111=14

3 3 3 5 6 7 9 34 34 4656 343 9 7 8 9 4656 57765 122344 12321

arr[i]=34,i=7,arr[j]=9,j2222=14

3 3 3 5 6 7 9 34 34 4656 343 9 7 8 34 4656 57765 122344 12321

arr[i]=34,i=7,arr[j]=8,j111=13

3 3 3 5 6 7 9 8 34 4656 343 9 7 8 34 4656 57765 122344 12321

arr[i]=34,i=8,arr[j]=8,j2222=13

3 3 3 5 6 7 9 8 34 4656 343 9 7 34 34 4656 57765 122344 12321

arr[i]=34,i=8,arr[j]=7,j111=12

3 3 3 5 6 7 9 8 7 4656 343 9 7 34 34 4656 57765 122344 12321

arr[i]=4656,i=9,arr[j]=7,j2222=12

3 3 3 5 6 7 9 8 7 4656 343 9 4656 34 34 4656 57765 122344 12321

arr[i]=4656,i=9,arr[j]=9,j111=11

3 3 3 5 6 7 9 8 7 9 343 9 4656 34 34 4656 57765 122344 12321

arr[i]=343,i=10,arr[j]=9,j2222=11

3 3 3 5 6 7 9 8 7 9 343 343 4656 34 34 4656 57765 122344 12321

3 3 3 5 6 7 9 8 7 9 23 343 4656 34 34 4656 57765 122344 12321

arr[start]=9,start=6,arr[end]=9,end=9

=====================

arr[i]=9,i=6,arr[j]=7,j111=8

3 3 3 5 6 7 7 8 7 9 23 343 4656 34 34 4656 57765 122344 12321

3 3 3 5 6 7 7 8 7 9 23 343 4656 34 34 4656 57765 122344 12321

3 3 3 5 6 7 7 8 9 9 23 343 4656 34 34 4656 57765 122344 12321

arr[start]=7,start=6,arr[end]=8,end=7

=====================

3 3 3 5 6 7 7 8 9 9 23 343 4656 34 34 4656 57765 122344 12321

3 3 3 5 6 7 7 8 9 9 23 343 4656 34 34 4656 57765 122344 12321

3 3 3 5 6 7 7 8 9 9 23 343 4656 34 34 4656 57765 122344 12321

arr[start]=343,start=11,arr[end]=34,end=14

=====================

arr[i]=343,i=11,arr[j]=34,j111=14

3 3 3 5 6 7 7 8 9 9 23 34 4656 34 34 4656 57765 122344 12321

arr[i]=4656,i=12,arr[j]=34,j2222=14

3 3 3 5 6 7 7 8 9 9 23 34 4656 34 4656 4656 57765 122344 12321

arr[i]=4656,i=12,arr[j]=34,j111=13

3 3 3 5 6 7 7 8 9 9 23 34 34 34 4656 4656 57765 122344 12321

3 3 3 5 6 7 7 8 9 9 23 34 34 34 4656 4656 57765 122344 12321

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 57765 122344 12321

arr[start]=34,start=11,arr[end]=34,end=12

=====================

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 57765 122344 12321

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 57765 122344 12321

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 57765 122344 12321

arr[start]=57765,start=16,arr[end]=12321,end=18

=====================

arr[i]=57765,i=16,arr[j]=12321,j111=18

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 122344 12321

arr[i]=122344,i=17,arr[j]=12321,j2222=18

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 122344 122344

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 57765 122344

3 3 3 5 6 7 7 8 9 9 23 34 34 343 4656 4656 12321 57765 122344 

快速排序

原文：https://www.cnblogs.com/tiantanglw/p/12483599.html