八大排序之快速排序

作者 : 开心源码 本文共1183个字,预计阅读时间需要3分钟 发布时间: 2022-05-12 共225人阅读

快速排序(Quick Sort)

通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录进行排序,以达到整个序列有序的目的。

枢轴(pivot)

先选取序列当中的一个关键字,想尽办法将其放在一个位置,使得它左边的值都比它小,右边的值都比它大,我们将这样子的关键字称为枢轴。

函数构成

partition
选出枢轴,将比枢轴小的数字放在左边,将比枢轴大的数字放在右边,所有坐标遍历之后,返回此时枢轴的坐标
swap
交换两个坐标的值

算法图解

以{50,10,90,30}的数组为例,以下是初次交换的过程图解

快速排序.jpeg

代码(java)实现

public class QuickSortDemo {    public static void main(String[] args) {        int[] list = {50, 10, 90, 30, 70, 40, 80, 60, 20};        quickSort(list);        for (int a : list) {            System.out.println(a);        }    }    private static void quickSort(int[] list) {        if (list == null || list.length == 0) {            return;        }        qSort(list, 0, list.length - 1);    }    private static void qSort(int[] list, int low, int high) {        if (low < high) {            int pivot = partition(list, low, high);            qSort(list, low, pivot - 1);            qSort(list, pivot + 1, high);        }    }    /**     * 我们这里以list[low]作为参考,所以肯定要先从high开始进行交换     * @param list     * @param low     * @param high     * @return     */    private static int partition(int[] list, int low, int high) {        int pivotKey = list[low];        while (low < high) {            while (low < high && list[high] >= pivotKey) {                high--;            }            swap(list, low, high);            while (low < high && list[low] <= pivotKey) {                low++;            }            swap(list, low, high);        }        return low;    }    /**     * 交换两个坐标的值     * @param list     * @param index1     * @param index2     */    private static void swap(int[] list, int index1, int index2) {        int data = list[index1];        list[index1] = list[index2];        list[index2] = data;    }}

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 八大排序之快速排序

发表回复