java快速排序法

Java评论867字数 2602阅读模式

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

java快速排序法-图片1

1、快速排序思想及原理

事实上,快速排序是堆冒泡排序的一种改进。
它的基本思想是:通过一趟排序将要排序的数据分割为两部分,第一部分所有数据比第二部分的所有数据小,按照这种思路将两部分数据再次分别进行快速排序,可以使用递归完成,最终使得整个数据序列有序。

具体来讲,在待排数据中找一个基准数据(通常取第一个数),接下来将待排数据中比基准数据小的放在待排数据的左侧,将比待排数据中比基准数据大的放在待排数据右侧。此时,左右两个分区的元素相对有序,接着采用上述思路继续对左右两个分区继续排序,直到各分区只有一个元素位置。这里用到了一个典型的分治思想。

下面我们用图解的方式来演示这个排序过程:

假设下面这个数组是待排序数组:

(6, 1, 2, 7, 9, 3, 4, 5, 10, 8)

按照快速排序的思想,首先得把这组数分成相互独立的两部分,其中一部分比中的数比另一部分的数都小。如何实现这一步呢?

方法其实很简单:首先选取待排序数组的第一个数为基准数,也就是6,然后分别从初始序列“(6,1,2,7,9,3,4,5,10,8)”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即j=10),指向数字8。

java快速排序法-图片2

首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。哨兵j一步一步地向左挪动(即j--),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。

java快速排序法-图片3

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列为(6, 1, 2, 5, 9, 3, 4, 7, 10, 8)。

接下来开始哨兵j继续向左挪动(再友情提醒,每次必须是哨兵j先出发)。他发现了4(比基准数6要小,满足要求)之后停了下来。哨兵i也继续向右挪动的,他发现了9(比基准数6要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列为(6, 1, 2, 5, 4, 3, 9, 7, 10, 8)。

java快速排序法-图片4

哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。3比6小所以我们将基准数6和3进行交换。交换之后的序列为(3, 1, 2, 5, 4, 6, 9, 7, 10, 8)。

java快速排序法-图片5

此时第一趟排序结束,我们已经把待排序数组分成了以6为基准,左边一列序列,右边一序列,左边序列的数比右边序列的数都小。不过此时左右两部分中的数各自的排序仍然是混乱的,还要继续排序。

快速排序的排序过程已经通过上面的图解讲解清楚了,接下来左右两部分的数据继续按照快速排序的方式来排序。

下面举例说明:

待排序列依次为3、5、7、2、11、6、1、3、8、4、10、12。

步骤:
1、选取一个基准数,一般选第0个元素3。
2、将比基准数小的移动到左侧,比基准数大的移动到右侧,相等的不移动,此时基准数位置为K。
3、对左右两侧重复步骤1和步骤2,直到左右侧细分到只有一个元素。
快排的难点也就是在第2步,怎么移动各个数据?
  a、首先从数列的右边开始往左找,设下标为i,也就是i--操作,找到第一个比基准数小的值,让他与基准数交换;
  b、接着开始从左往右找,设下标为j,也就是j++,找到第一个比基准数大的值,让他与基准数交换位置;
  c、重复1和2,直到i和j相遇时结束,最后基准值所在位置为k。

2、java快排代码

public class FastSort {
    public static void main(String[] args) {
        int[] array = new int[] { 3, 5, 7, 2, 11, 6, 1, 3, 8, 4, 10, 12 };

        fastSort(array, 0, array.length - 1);
        print(array);
    }

    private static void fastSort(int[] array, int l, int r) {
        if (l > r) {
            return;
        }

        int low = l;
        int high = r;
        int key = array[l];
        while (low < high) {
            for (;; high--) {
                if (high <= low) {
                    break;
                }
                if (array[high] < key) {
                    array[low] = array[high];
                    break;
                }
            }

            for (;; low++) {
                if (high <= low) {
                    break;
                }
                if (array[low] > key) {
                    array[high] = array[low];
                    break;
                }
            }
        }
        if (low == high) {
            array[low] = key;
        }

        // print(array);

        fastSort(array, 0, low - 1);
        fastSort(array, low + 1, r);

    }

    private static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }

    }

}

3、快排的特点及性能

快排是在冒泡排序之上改进而来的,冒泡排序每次只能交换相邻的两个元素,而快排则是跳跃式的交换,交换距离很大,总的比较次数和交换次数少了很多,速度也快了很多。
快排的平均时间复杂度为O(nlogn),事实上,大多数情况下,排序速度要快于这个时间复杂度。快排实际上是采用的一种分而治之的思想,把问题分解为一个个的小问题去逐一解决,最终在把结果组合起来。
快排因为递归调用,所以空间复杂度为O(logn)。
快排是一种不稳定的排序算法,在经过排序后,等值的元素的相对位置可能发生改变。
快排基本上被认为是相同数量级中所有排序算法中平均性能最好的。

4、快排的适用场景

快排由于相对简单而且性能不错,所以快排适用于几乎绝大多数场合。

本文已通过「原本」原创作品认证,转载请注明文章出处及链接。

Java最后更新:2022-11-20
夏日阳光
  • 本文由 夏日阳光 发表于 2018年9月6日
  • 本文为夏日阳光原创文章,转载请务必保留本文链接:https://www.pieruo.com/2.html
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证