快速排序算法（基于Java实现）

2020-12-17

字数统计: 905字 | 阅读时长≈ 3分

快速排序算法（基于Java实现）

快速排序算法的原理与代码实现：

一、快速排序算法的原理

快排算法的思想是： 如果需要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。我们遍历p到r之间的数据，将小于pivot的放到左边，将大姨pivot的放在右边，将pivot放到了中间。经过这样的操作之后，数组中的数据就被分成了三个部分了，前面的p到q-1之间的都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。

然后，根据分治、递归思想，我们可以递归排序下标从p到q-1之间的数据和q+1到r之间的数据，直到区间缩小为1，就说明所有的数据有序了。

二、快速排序算法的代码实现

package com.company;


import java.util.Arrays;

public class QuickSort2 {
    public static void quickSort(int[] a, int p, int r){
        if(p>r) return;
        int q = partition(a, p, r);
        quickSort(a, p, q-1);
        quickSort(a, q+1, r);
    }

    public static int partition(int[] a, int p, int r) {
        int i = p;
        int j = r;
        int tmp = a[p];//tmp为基数

        while (i < j) {
            while (tmp <= a[j] && i < j) {
                j--;
            }
            swap(a, i, j);
            while (tmp >= a[i] && i < j) {
                i++;
            }
            swap(a, i, j);

        }

        return i;
    }

    public static void swap(int[] a, int i, int j){
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;

    }

    public static void main(String[] args) {
        //int[] a = {10, 9, 7, 4, 3, 2, 1, 8};

        int[] a = {6, 11, 3, 9, 8};
        System.out.println("之前的排序：");
        System.out.println(Arrays.toString(a));

        quickSort(a, 0,4);
        System.out.println("之后的排序：");
        System.out.println(Arrays.toString(a));
    }
}

输出的结果为：

之前的排序：
[6, 11, 3, 9, 8]
之后的排序：
[3, 6, 8, 9, 11]

三、快速排序算法性能分析

因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。

快排也是用递归来实现的。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，**快排的时间复杂度也是 O(nlogn)**。

在快排算法中，我们通过游标 i 把 A[p…r-1]分成两部分。A[p…i-1]的元素都是小于 pivot 的，我们暂且叫它“已处理区间”，A[i…r-1]是“未处理区间”。我们每次都从未处理的区间 A[i…r-1]中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i]的位置。那么，我们只需要将 A[i]与 A[j]交换，就可以在 O(1) 空间复杂度内将 A[j]放到下标为 i 的位置。故，**快速排序是一个原地排序算法，空间复杂度为O(1)**。

本文作者： feng之锋
本文链接： http://example.com/2020/12/17/快速排序算法/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！