快速排序算法--Java实现

标签（空格分隔）： 数据结构与算法

---

原理：

对于任意一个无序数组，我们随机的选一个元素作为基准元素（例如：数组中的最后一个或者第一个元素, 然后我们将数组中的剩余元素分别与基准元素进行比较，将小于或等于基准元素的数据放在基准元素的左边,将大于基准元素的数据放在基准元素的右边，当全部比较完成之后,基准元素在数组中的位置就确定了下来。然后，在分别对左边数组和右边的数组递归的进行上面的操作，直到每一个元素的位置都唯一确定下来。

例如:我们对下面的数组进行快速排序

[ 8 2 1 7 3 5 9 6 ]

算法步骤分析：

1.选取数组中的最后一个元素6最为基准元素
2.遍历剩下所有数据8 2 1 7 3 5 9

我们使用一个变量n,记录小于基准元素的个数，比较前,我们假设所有的元素都大于或等于基准元素，即所有元素都被认为是大于基准元素的. n = start =0------------ n=0；

过程分析

1. 8 和 6比较，8大于基准元素，不做任何变化
   8 2 1 7 3 5 9 ----------- n=0;

2. 2和6比较，2比6小. 我们应该将这个元素放到基准元素的左边,怎么做呢,我们将这个元素和大于基准的第一个元素交换一下就行了,然后将n加1.
   2 8 1 7 3 5 9 ------------ n=1;

3. 1和6比较，1比6小 ，交换1和8的位置,n加1.
   2 1 8 7 3 5 9 ------------- n=2;

4. 7和6比较，7比6大，不做任何变化
   2 1 8 7 3 5 9 ------------- n=2;

5. 3和6比较，3比6小，交换8和3的位置,n加1
   2 1 3 7 8 5 9-------------- n=3;

6. 5和6比较，5比6小，交换5和7的位置,n加1.
   2 1 3 5 8 7 9-------------- n=4;

7. 9和6比较，9比6小，不做任何变化
   2 1 3 5 8 7 9-------------- n=4;

8. 最终结果:表明小于或等于6的元素共有4个
   2 1 3 5 8 7 9 6 ----------- n=4;

也就是说,6这个基准元素应该放到原数组中下标索引为4的位置上（数组从0开始下表）.
即它可能应该类似这样的存放:
[ 2 1 3 5 6 8 7 9 ]
但是如何实现这样的操作呢？
事实上只要将6这个元素与此时数组[ 2 1 3 5 8 7 9 6 ]中的第4个元素8的交换位置即可.
结果如下：
[ 2 1 3 5 ] 6 [ 7 9 8 ]
这样我们就区分出了两个数组，比 6 小的[ 2 1 3 5 ]和不小于6的[ 7 9 8 ]，当然这个两个数组的顺序不一定是正确的，但是基准元素所在的位置一定是正确的，然后我们在分别对左右两数组做同样的操作，依次类推下去，最后确定每一个元素所在的位置，这样整个数组就完成了排序。

    /**
     * 拆分数组
     * @param arr   要拆分的数组
     * @param start 数组拆分的起始索引 （从0开始）
     * @param end   数组拆分的结束索引
     */
    public static int partArr(int[] arr, int start, int end) {

        //选取基准元素，这里我们以最后一个位置，作为基准

        int base = arr[end];
        //记录，比基准元素小的变量，这里我们假设要比较的元素都不小于基准元素，这样通过比较
        //就把小于基准元素的数据全部找到，n=start表示的就是默认没有小于基准元素。
        int n = start;

        //基准元素不参与遍历比较
        for (int i = start; i < end; i++) {
            if (arr[i] < base) {
                //将小于基准元素的放到基准的左边
                if (i != n)
                    exchangeE(arr, i, n);
                n++;
            }
        }
        //遍历完成之后，将基准元素放到应该的位置上
        exchangeE(arr, n, end);
        return n;
    }

    /**
     * 交换数组中指定位置的两个元素
     *
     * @param array
     * @param index1
     * @param index2
     */
    public static void exchangeE(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

根据拆分的结果，进行在拆分，由于原理一样，因此我们使用递归调用的思想

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

        //递归调用的结束条件,开始要拆分的数组就剩下一个元素的时候
        if(end-start<1)
            return;
        int part = partArr(arr, start, end);
        //三种情况下的继续拆分
        if(part==start)
            recurPartiton(arr,part+1,end);
        else if(part ==end)
            recurPartiton(arr,start,end-1);
        else{
            recurPartiton(arr,start,part-1);
            recurPartiton(arr,part+1,end);
        }
    }

最后封装测试:

    public static void main(String[] args) {
        int[] arr = {8, 2, 1, 4,6,7, 3, 5, 9, 6,11,19,13,55,67,32,22};

        quickSort(arr);


        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr){

        recurPartiton(arr,0,arr.length-1);

    }

完整代码测试案例

package com.sivin.test;

import java.util.Arrays;
public class main {
    /**
     * 拆分数组
     * @param arr   要拆分的数组
     * @param start 数组拆分的起始索引 （从0开始）
     * @param end   数组拆分的结束索引
     */
    public static int partArr(int[] arr, int start, int end) {

        //选取基准元素，这里我们以最后一个位置，作为基准

        int base = arr[end];
        //记录，比基准元素小的变量，这里我们假设要比较的元素都不小于基准元素，这样通过比较
        //就把小于基准元素的数据全部找到，n=start表示的就是默认没有小于基准元素。
        int n = start;

        //基准元素不参与遍历比较
        for (int i = start; i < end; i++) {
            if (arr[i] < base) {
                //将小于基准元素的放到基准的左边
                if (i != n)
                    exchangeE(arr, i, n);
                n++;
            }
        }
        //遍历完成之后，将基准元素放到应该的位置上
        exchangeE(arr, n, end);
        return n;
    }

    /**
     * 交换数组中指定位置的两个元素
     *
     * @param array
     * @param index1
     * @param index2
     */
    public static void exchangeE(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

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

        //递归调用的结束条件,开始要拆分的数组就剩下一个元素的时候
        if(end-start<1)
            return;
        int part = partArr(arr, start, end);
        //三种情况下的继续拆分
        if(part==start)
            recurPartiton(arr,part+1,end);
        else if(part ==end)
            recurPartiton(arr,start,end-1);
        else{
            recurPartiton(arr,start,part-1);
            recurPartiton(arr,part+1,end);
        }
    }


    public static void main(String[] args) {
        int[] arr = {9,8,7,3,4,1,2,3};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr){
        recurPartiton(arr,0,arr.length-1);
    }
}

测试结果如下:

测试结果1.png
测试结果2.png