原创

2021-01-05
浏览 (625)
评论 (0)

(六) 数据结构 - 快速排序

快速排序

快速排序是一种排序执行效率很高的排序算法，它利用分治法来对待排序序列进行分治排序，它的思想主要是通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比关键字小，后面一部分比关键字大，然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序。

核心思想

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码开发

实现思路

Step 1-从数组中挑选一个元素作为基准值(从左边和右边开始都可以)
Step 2-将两个变量分别指向数组的左侧和右侧（不包括基准值）
Step 3-左指向低索引
Step 4-右指向高索引
Step 5-比基准值小的放置在基准值前面
Step 6-比基准值大的放置在基准值后面(相同数据可以放置任意一边)
Step 7-递归(其中包括确定新的基准值)把小于基准值元素的子数列和大于基准值元素的子数列排序

伪代码

package com.paal.demo.c01SortingBasic;

import com.paal.demo.Sort;
import com.paal.demo.utils.SortTestHelper;

/**
 * <p/>
 * <li>title: 快速排序-基础版</li>
 * <li>@author: li.pan</li>
 * <li>Date: 2019/12/10 22:50 下午</li>
 * <li>Version: V1.0</li>
 * <li>Description: todo</li>
 */
public class QuickSort implements Sort {

    /**
     * 快速排序入口
     *
     * @param arr 数组
     */
    @Override
    public void sort(Integer[] arr) {

        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    /**
     * 递归使用快速排序,对arr[l...r]的范围进行排序
     *
     * @param arr 无序集合
     * @param l   低索引
     * @param r   高索引
     */
    public static void sort(Integer[] arr, int l, int r) {

        // 递归到底
        if (l >= r)
            return;
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    /**
     * 比基准值小的放置在基准值前面，比基准值大的放置在基准值后面(相同数据可以放置任意一边)
     * 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
     *
     * @param arr 无序数组
     * @param l   低索引
     * @param r   高索引
     * @return
     */
    private static int partition(Integer[] arr, int l, int r) {

        Integer v = arr[l];

        int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
        for (int i = l + 1; i <= r; i++)
            if (arr[i] < v) {
                j++;
                SortTestHelper.swap(arr, j, i);
            }

        SortTestHelper.swap(arr, l, j);
        return j;
    }
}
/**
     * 快速排序测试方法
     */
    @Test
    public void quickSortTest() {

        Integer[] integers0 = SortTestHelper.generateRandomArray(100, 0, 1000000);
        Integer[] integers1 = SortTestHelper.generateRandomArray(10000, 0, 1000000);
        Integer[] integers2 = SortTestHelper.generateRandomArray(100000, 0, 1000000);
        System.out.println("------------------------------随机数组--------------------------------");
        System.out.println("插入排序测试1数据量为100" + SortTestHelper.testSort(integers0, new InsertionSort()));
        System.out.println("插入排序测试2数据量为10000" + SortTestHelper.testSort(integers1, new InsertionSort()));
        System.out.println("插入排序测试3数据量为100000" + SortTestHelper.testSort(integers2, new InsertionSort()));
        System.out.println("归并排序优化测试1数据量为100" + SortTestHelper.testSort(integers0, new MergeSortOptimize()));
        System.out.println("归并排序优化测试2数据量为10000" + SortTestHelper.testSort(integers1, new MergeSortOptimize()));
        System.out.println("归并排序优化测试3数据量为100000" + SortTestHelper.testSort(integers2, new MergeSortOptimize()));
        System.out.println("快速排序测试1数据量为100" + SortTestHelper.testSort(integers0, new QuickSort()));
        System.out.println("快速排序测试2数据量为10000" + SortTestHelper.testSort(integers1, new QuickSort()));
        System.out.println("快速排序测试3数据量为100000" + SortTestHelper.testSort(integers2, new QuickSort()));

    }

执行结果

------------------------------随机数组--------------------------------
插入排序测试1数据量为100排序时长为: 0.005s
插入排序测试2数据量为10000排序时长为: 0.089s
插入排序测试3数据量为100000排序时长为: 5.728s
归并排序优化测试1数据量为100排序时长为: 0.0s
归并排序优化测试2数据量为10000排序时长为: 0.001s
归并排序优化测试3数据量为100000排序时长为: 0.005s
快速排序测试1数据量为100排序时长为: 0.0s
快速排序测试2数据量为10000排序时长为: 0.046s
快速排序测试3数据量为100000排序时长为: 6.721s

代码优化

优化一：对于数据量较小的数组, 使用插入排序的性能反而更快, 所以可以在partition到底层数据量较小的时候, 使用插入排序替换快速排序
优化二：因为数组可能是近乎有序的数组, 所以我们可以不每次取队首的元素, 可以采取每次随机取一个元素
优化三(三路快排)：对于存在大量重复元素的数组, 我们可以不仅仅将数组分割成两部分, 而是可以将数组分割成小于V, 等于V, 大于V的三部分, 然后对小于V和大于V的两部分在进行递归排序

伪代码

package com.paal.demo.c01SortingBasic.optimize;

import com.paal.demo.Sort;
import com.paal.demo.utils.SortTestHelper;

/**
 * <p/>
 * <li>title: 快速排序优化</li>
 * <li>@author: li.pan</li>
 * <li>Date: 2019/12/10 22:50 下午</li>
 * <li>Version: V1.0</li>
 * <li>Description:
 * 优化1: 对于小规模数组, 使用插入排序,效率更佳
 * 优化2: 对于arr[l...r]可能近乎有序的数组,采用获取随机值的方式随机获取基准值位置
 * 优化3: 对于arr[l...r]可能存在大量元素的数组,可以将数组分割为小于V,等于V,大于V的三部分,然后对小于V和大于V部分进行递归
 * </li>
 */
public class QuickSortOptimize implements Sort {

    /**
     * 快速排序入口
     *
     * @param arr 数组
     */
    @Override
    public void sort(Integer[] arr) {

        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    /**
     * 递归使用快速排序,对arr[l...r]的范围进行排序
     *
     * @param arr 无序集合
     * @param l   低索引
     * @param r   高索引
     */
    private static void sort(Integer[] arr, int l, int r) {

        /**
         *  优化1: 对于小规模数组, 使用插入排序,效率更佳
         */
        if (r - l <= 15) {
            insertionSort(arr, l, r);
            return;
        }

        /**
         * 优化2: 对于arr[l...r]可能近乎有序的数组,采用获取随机值的方式随机获取基准值位置
         * (int) (Math.random() * (r - l + 1)) + l
         */
        SortTestHelper.swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);

        Integer v = arr[l];

        /**
         * 优化3: 对于arr[l...r]可能存在大量元素的数组,可以将数组分割为小于V,等于V,大于V的三部分,然后对小于V和大于V部分进行递归
         * 简称"三路快排"
         */
        int lt = l;     // arr[l+1...lt] < v
        int gt = r + 1; // arr[gt...r] > v
        int i = l + 1;    // arr[lt+1...i) == v
        while (i < gt) {
            if (arr[i] < v) {
                SortTestHelper.swap(arr, i, lt + 1);
                i++;
                lt++;
            } else if (arr[i].compareTo(v) > 0) {
                SortTestHelper.swap(arr, i, gt - 1);
                gt--;
            } else { // arr[i] == v
                i++;
            }
        }
        SortTestHelper.swap(arr, l, lt);

        sort(arr, l, lt - 1);
        sort(arr, gt, r);
    }

    // 对arr[l...r]的区间使用InsertionSort排序
    public static void insertionSort(Integer[] arr, int l, int r) {

        for (int i = l + 1; i <= r; i++) {
            Integer e = arr[i];
            int j = i;
            for (; j > l && arr[j - 1] > e; j--)
                arr[j] = arr[j - 1];
            arr[j] = e;
        }
    }
}

    /**
     * 快速排序测试优化方法
     */
    @Test
    public void quickOptimizeSortTest() {

        Integer[] integers0 = SortTestHelper.generateRandomArray(100, 0, 1000000);
        Integer[] integers1 = SortTestHelper.generateRandomArray(10000, 0, 1000000);
        Integer[] integers2 = SortTestHelper.generateRandomArray(100000, 0, 1000000);
        System.out.println("------------------------------随机数组--------------------------------");
        System.out.println("插入排序测试1数据量为100" + SortTestHelper.testSort(integers0, new InsertionSort()));
        System.out.println("插入排序测试2数据量为10000" + SortTestHelper.testSort(integers1, new InsertionSort()));
        System.out.println("插入排序测试3数据量为100000" + SortTestHelper.testSort(integers2, new InsertionSort()));
        System.out.println("归并排序优化测试1数据量为100" + SortTestHelper.testSort(integers0, new MergeSortOptimize()));
        System.out.println("归并排序优化测试2数据量为10000" + SortTestHelper.testSort(integers1, new MergeSortOptimize()));
        System.out.println("归并排序优化测试3数据量为100000" + SortTestHelper.testSort(integers2, new MergeSortOptimize()));
        System.out.println("快速排序测试1数据量为100" + SortTestHelper.testSort(integers0, new QuickSort()));
        System.out.println("快速排序测试2数据量为10000" + SortTestHelper.testSort(integers1, new QuickSort()));
        System.out.println("快速排序测试3数据量为100000" + SortTestHelper.testSort(integers2, new QuickSort()));
        System.out.println("快速排序测试1数据量为100" + SortTestHelper.testSort(integers0, new QuickSortOptimize()));
        System.out.println("快速排序测试2数据量为10000" + SortTestHelper.testSort(integers1, new QuickSortOptimize()));
        System.out.println("快速排序测试3数据量为100000" + SortTestHelper.testSort(integers2, new QuickSortOptimize()));

        System.out.println("------------------------------近乎有序的数组--------------------------------");
        Integer[] integers00 = SortTestHelper.generateNearlyOrderedArray(100, 10);
        Integer[] integers11 = SortTestHelper.generateNearlyOrderedArray(10000, 100);
        Integer[] integers22 = SortTestHelper.generateNearlyOrderedArray(100000, 1000);
        System.out.println("插入排序测试1数据量为100" + SortTestHelper.testSort(integers00, new InsertionSort()));
        System.out.println("插入排序测试2数据量为10000" + SortTestHelper.testSort(integers11, new InsertionSort()));
        System.out.println("插入排序测试3数据量为100000" + SortTestHelper.testSort(integers22, new InsertionSort()));
        System.out.println("归并排序优化测试1数据量为100" + SortTestHelper.testSort(integers00, new MergeSortOptimize()));
        System.out.println("归并排序优化测试2数据量为10000" + SortTestHelper.testSort(integers11, new MergeSortOptimize()));
        System.out.println("归并排序优化测试3数据量为100000" + SortTestHelper.testSort(integers22, new MergeSortOptimize()));
        System.out.println("快速排序测试1数据量为100" + SortTestHelper.testSort(integers00, new QuickSort()));
        System.out.println("快速排序测试2数据量为10000" + SortTestHelper.testSort(integers11, new QuickSort()));
        System.out.println("快速排序测试3数据量为100000" + SortTestHelper.testSort(integers22, new QuickSort()));
        System.out.println("快速排序测试1数据量为100" + SortTestHelper.testSort(integers00, new QuickSortOptimize()));
        System.out.println("快速排序测试2数据量为10000" + SortTestHelper.testSort(integers11, new QuickSortOptimize()));
        System.out.println("快速排序测试3数据量为100000" + SortTestHelper.testSort(integers22, new QuickSortOptimize()));

        Integer[] integers000 = SortTestHelper.generateRandomArray(100, 0, 10);
        Integer[] integers111 = SortTestHelper.generateRandomArray(10000, 0, 100);
        Integer[] integers222 = SortTestHelper.generateRandomArray(100000, 0, 1000);
        System.out.println("------------------------------大量重复的数组--------------------------------");
        System.out.println("插入排序测试1数据量为100" + SortTestHelper.testSort(integers000, new InsertionSort()));
        System.out.println("插入排序测试2数据量为10000" + SortTestHelper.testSort(integers111, new InsertionSort()));
        System.out.println("插入排序测试3数据量为100000" + SortTestHelper.testSort(integers222, new InsertionSort()));
        System.out.println("归并排序优化测试1数据量为100" + SortTestHelper.testSort(integers000, new MergeSortOptimize()));
        System.out.println("归并排序优化测试2数据量为10000" + SortTestHelper.testSort(integers111, new MergeSortOptimize()));
        System.out.println("归并排序优化测试3数据量为100000" + SortTestHelper.testSort(integers222, new MergeSortOptimize()));
        System.out.println("快速排序测试1数据量为100" + SortTestHelper.testSort(integers000, new QuickSort()));
        System.out.println("快速排序测试2数据量为10000" + SortTestHelper.testSort(integers111, new QuickSort()));
        System.out.println("快速排序测试3数据量为100000" + SortTestHelper.testSort(integers222, new QuickSort()));
        System.out.println("快速排序测试1数据量为100" + SortTestHelper.testSort(integers000, new QuickSortOptimize()));
        System.out.println("快速排序测试2数据量为10000" + SortTestHelper.testSort(integers111, new QuickSortOptimize()));
        System.out.println("快速排序测试3数据量为100000" + SortTestHelper.testSort(integers222, new QuickSortOptimize()));

    }

执行结果

------------------------------随机数组--------------------------------
插入排序测试1数据量为100排序时长为: 0.001s
插入排序测试2数据量为10000排序时长为: 0.08s
插入排序测试3数据量为100000排序时长为: 5.66s
归并排序优化测试1数据量为100排序时长为: 0.0s
归并排序优化测试2数据量为10000排序时长为: 0.005s
归并排序优化测试3数据量为100000排序时长为: 0.003s
快速排序测试1数据量为100排序时长为: 0.0s
快速排序测试2数据量为10000排序时长为: 0.045s
快速排序测试3数据量为100000排序时长为: 6.748s
快速排序测试1数据量为100排序时长为: 0.0s
快速排序测试2数据量为10000排序时长为: 0.004s
快速排序测试3数据量为100000排序时长为: 0.033s
------------------------------近乎有序的数组--------------------------------
插入排序测试1数据量为100排序时长为: 0.0s
插入排序测试2数据量为10000排序时长为: 0.001s
插入排序测试3数据量为100000排序时长为: 0.097s
归并排序优化测试1数据量为100排序时长为: 0.0s
归并排序优化测试2数据量为10000排序时长为: 0.0s
归并排序优化测试3数据量为100000排序时长为: 0.0s
快速排序测试1数据量为100排序时长为: 0.0s
快速排序测试2数据量为10000排序时长为: 0.031s
快速排序测试3数据量为100000排序时长为: 3.459s
快速排序测试1数据量为100排序时长为: 0.0s
快速排序测试2数据量为10000排序时长为: 0.0s
快速排序测试3数据量为100000排序时长为: 0.008s
------------------------------大量重复的数组--------------------------------
插入排序测试1数据量为100排序时长为: 0.0s
插入排序测试2数据量为10000排序时长为: 0.039s
插入排序测试3数据量为100000排序时长为: 5.454s
归并排序优化测试1数据量为100排序时长为: 0.0s
归并排序优化测试2数据量为10000排序时长为: 0.0s
归并排序优化测试3数据量为100000排序时长为: 0.0s
快速排序测试1数据量为100排序时长为: 0.0s
快速排序测试2数据量为10000排序时长为: 0.034s
快速排序测试3数据量为100000排序时长为: 7.021s
快速排序测试1数据量为100排序时长为: 0.0s
快速排序测试2数据量为10000排序时长为: 0.001s
快速排序测试3数据量为100000排序时长为: 0.005s

正文到此结束

所属分类：排序算法

本文标签： 数据结构
版权声明： 本站原创文章，于2021年01月05日由匠人李发布，转载请注明出处

热门推荐

Flink消费Kafka指定offset的五种方式

浏览(2,357) 评论(0)
Flink中Time&Window

浏览(1,658) 评论(0)
Spark Shuffle运行原理

浏览(1,646) 评论(0)
Java Future详解与使用

浏览(1,568) 评论(1)
维度建模之代理键

浏览(1,562) 评论(0)
任务提交SparkSubmit源码解析

浏览(1,539) 评论(3)
Flink窗口起始时间计算

浏览(1,498) 评论(0)
Flink动态表 (Dynamic Table)

浏览(1,437) 评论(0)
Flink Table API & SQL概念和通用API

浏览(1,429) 评论(0)
Hive SQL常用日期转换

浏览(1,399) 评论(0)

相关文章

Loading...