快速排序

Reducto 发布于2019-08-14 15:11 / 661人阅读

摘要：快速排序，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序以达到整个序列有序的目的。

概述

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(nlogn)次比较。事实上，快速排序通常明显比其他Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，并且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。

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

形象图示：

步骤

选择一个基准元素，通常选择第一个元素或者最后一个元素

通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值均比基准值大

此时基准元素在其排好序后的正确位置

然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

实例

原始数据：

3 5 2 6 2

选择 3 作为基准

第一轮

从右往左找比3小的，2符合，将2和3对调
2 5 2 6 3
对调一次，查找的方向反向，从左向右找比3大的，5符合，对调
2 3 2 6 5
再从右往左找比3小的，2符合，对调
2 2 3 6 5
一轮结束

第二轮

对 [2 2] 采用同上的方式进行，得到
2 2 3 6 5

第三轮

对 [6 5] 采用同上的方式进行，得到
2 2 3 5 6

最终结果

2 2 3 5 6

代码实现(Java)

package com.coder4j.main.arithmetic.sorting;

public class Quick {

    private static int mark = 0;

    /**
     * 辅助交换方法
     * 
     * @param array
     * @param a
     * @param b
     */
    private static void swap(int[] array, int a, int b) {
        if (a != b) {
            int temp = array[a];
            array[a] = array[b];
            array[b] = temp;
            // 找到符合的，对调
            System.out.println("对调" + array[a] + "与" + array[b] + ",得到");
            for (int i : array) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    /**
     * 新一轮分隔
     * 
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partition(int array[], int low, int high) {
        int base = array[low];
        mark++;
        System.out.println("正在进行第" + mark + "轮分隔，区域：" + low + "-" + high);
        while (low < high) {
            while (low < high && array[high] >= base) {
                high--;
                System.out.println("从右往左找比" + base + "小的，指针变动：" + low + "-" + high);
            }
            swap(array, low, high);
            while (low < high && array[low] <= base) {
                low++;
                System.out.println("从左往右找比" + base + "大的，指针变动：" + low + "-" + high);
            }
            swap(array, low, high);
        }
        return low;
    }

    /**
     * 对数组进行快速排序，递归调用
     * 
     * @param array
     * @param low
     * @param heigh
     * @return
     */
    private static int[] quickSort(int[] array, int low, int high) {
        if (low < high) {
            int division = partition(array, low, high);
            quickSort(array, low, division - 1);
            quickSort(array, division + 1, high);
        }
        return array;
    }

    /**
     * 快排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        return quickSort(array, 0, array.length - 1);
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

测试输出结果：

正在进行第1轮分隔，区域：0-4
对调2与3,得到
2 5 2 6 3 
从左往右找比3大的，指针变动：1-4
对调3与5,得到
2 3 2 6 5 
从右往左找比3小的，指针变动：1-3
从右往左找比3小的，指针变动：1-2
对调2与3,得到
2 2 3 6 5 
从左往右找比3大的，指针变动：2-2
正在进行第2轮分隔，区域：0-1
从右往左找比2小的，指针变动：0-0
正在进行第3轮分隔，区域：3-4
对调5与6,得到
2 2 3 5 6 
从左往右找比6大的，指针变动：4-4
最终结果
2 2 3 5 6

经测试，与实例中结果一致。

GPU服务器云服务器快速排序快速排序函数快速排序算法 php快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65414.html

快速排序就这么简单

摘要：快速排序的介绍来源百度百科快速排序由在年提出。快速排序是面试出现的可能性比较高的，也是经常会用到的一种排序，应该重点掌握。前面一个章节已经讲了递归了，那么现在来看快速排序就非常简单了。快速排序就这么简单从前面已经讲解了冒泡排序、选择排序、插入排序了，本章主要讲解的是快速排序，希望大家看完能够理解并手写出快速排序的代码，然后就通过面试了！如果我写得有错误的地方也请大家在评论下指出。 ...

Faremax 2019-08-15 14:54 评论0 收藏0
算法之旅 | 快速排序法

摘要：今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法快速排序法平均时间复杂度为。快速排序法的原理快速排序是一种划分交换排序，它采用分治的策略，通常称其为分治法。 HTML5学堂-码匠：前几期算法之旅跟大家分享了冒泡排序法和选择排序法，它们都属于时间复杂度为O(n^2)的慢排序。今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法—— 快速排序法 [ 平均时间复杂度为O (n l...

AlanKeene 2019-08-22 11:11 评论0 收藏0
Javascript实现冒泡排序与快速排序以及对快速排序的性能优化

摘要：实现快速排序介绍通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。冒泡排序介绍重复遍历要排序的元素列，依次比较两个相邻的元素，前一个元素若比后一个元素大则互换位置。以升序排序为例，最大的元素会在第一次遍历后冒泡到数组的末端。假如数组...

dadong 2019-08-23 15:08 评论0 收藏0
怎样测试程序的平均性能

标准库中的sort函数，是快速排序算法的典型实现。算法将含有n个元素的序列排序，平均需要 O(n log n) 时间。上周，我提出了测试一个程序的性能比测试其功能更难这个观点。确认程序的性能达到标准以及确定标准的含义都十分困难。接下来，我会继续讨论标准库中的sort(排序)函数。sort函数实现了快速排序算法，快速排序算法平均可以在 O(n log n) 时间内对含有n个元素的序列进行排序...

mochixuan 2019-05-29 16:19 评论0 收藏0