快速排序算法--Java实现

作者: Sivin | 来源:发表于2016-03-26 02:36 被阅读6910次

    标签(空格分隔): 数据结构与算法


    原理:

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

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

    [ 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;
    1. 2和6比较,2比6小. 我们应该将这个元素放到基准元素的左边,怎么做呢,我们将这个元素和大于基准的第一个元素交换一下就行了,然后将n加1.
      2 8 1 7 3 5 9 ------------ n=1;
    1. 1和6比较,1比6小 ,交换1和8的位置,n加1.
      2 1 8 7 3 5 9 ------------- n=2;
    1. 7和6比较,7比6大,不做任何变化
      2 1 8 7 3 5 9 ------------- n=2;
    1. 3和6比较,3比6小,交换8和3的位置,n加1
      2 1 3 7 8 5 9-------------- n=3;
    1. 5和6比较,5比6小,交换5和7的位置,n加1.
      2 1 3 5 8 7 9-------------- n=4;
    1. 9和6比较,9比6小,不做任何变化
      2 1 3 5 8 7 9-------------- n=4;
    1. 最终结果:表明小于或等于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

    相关文章

      网友评论

        本文标题:快速排序算法--Java实现

        本文链接:https://www.haomeiwen.com/subject/xesdlttx.html