搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 算法爱好者 > 图解排序算法(5):快速排序

图解排序算法(5):快速排序

算法爱好者 2019-11-08

http://www.cnblogs.com/chengxiao/


基本思想


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


基本步骤


1、三数取中



2、枢纽值进行分割


图解排序算法(5):快速排序


代码实现


package sortdemo;

import java.util.Arrays;

/**

 * Created by chengxiao on 2016/12/14.

 * 快速排序

 */

public class QuickSort {

    public static void main(String[] args) {

        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

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

        System.out.println("排序结果:" + Arrays.toString(arr));

    }

    /**

     * @param arr

     * @param left  左指针

     * @param right 右指针

     */

    public static void quickSort(int[] arr, int left, int right) {

        if (left < right) {

            //获取枢纽值,并将其放在当前待处理序列末尾

            dealPivot(arr, left, right);

            //枢纽值被放在序列末尾

            int pivot = right - 1;

            //左指针

            int i = left;

            //右指针

            int j = right - 1;

            while (true) {

                while (arr[++i] < arr[pivot]) {

                }

                while (j > left && arr[--j] > arr[pivot]) {

                }

                if (i < j) {

                    swap(arr, i, j);

                } else {

                    break;

                }

            }

            if (i < right) {

                swap(arr, i, right - 1);

            }

            quickSort(arr, left, i - 1);

            quickSort(arr, i + 1, right);

        }

    }

    /**

     * 处理枢纽值

     *

     * @param arr

     * @param left

     * @param right

     */

    public static void dealPivot(int[] arr, int left, int right) {

        int mid = (left + right) / 2;

        if (arr[left] > arr[mid]) {

            swap(arr, left, mid);

        }

        if (arr[left] > arr[right]) {

            swap(arr, left, right);

        }

        if (arr[right] < arr[mid]) {

            swap(arr, right, mid);

        }

        swap(arr, right - 1, mid);

    }


    /**

     * 交换元素通用处理

     *

     * @param arr

     * @param a

     * @param b

     */

    private static void swap(int[] arr, int a, int b) {

        int temp = arr[a];

        arr[a] = arr[b];

        arr[b] = temp;

    }

}


总结


快速排序是一种交换类的排序,它同样是分治法的经典体现。在一趟排序中将待排序的序列分割成两组,其中一部分记录的关键字均小于另一部分。然后分别对这两组继续进行排序,以使整个序列有序。


在分割的过程中,枢纽值的选择至关重要,本文采取了三位取中法,可以很大程度上避免分组"一边倒"的情况。快速排序平均时间复杂度也为O(nlogn)级。


图解排序算法系列





觉得本文有帮助?请分享给更多人

关注「算法爱好者」,修炼编程内功

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《图解排序算法(5):快速排序》的版权归原作者「算法爱好者」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注算法爱好者微信公众号

算法爱好者微信公众号:AlgorithmFans

算法爱好者

手机扫描上方二维码即可关注算法爱好者微信公众号

算法爱好者最新文章

精品公众号随机推荐