十大经典排序算法-快速排序

排序算法

编程算法

发布日期: 2020-10-23

文章字数: 1.1k

阅读时长: 4 分

前言

本文重点讲解十大经典排序算法的快速排序

要点

快速排序（Quick Sort）是对冒泡排序的一种改进。
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

基本思想

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

首先设定一个分界值，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
然后，左边和右边的数据可以独立排序，对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义，通过递归将左侧部分排好序后，再递归排好右侧部分的顺序，当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

代码实现

以下代码由java实现

public class QuickSort {

    /**
     * 快速排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr, int low, int high) {
        if (arr.length <= 0) {
            return null;
        }
        if (low < high) {
            // 调整枢纽元素位置并获取该位置
            int mid = partition(arr, low, high);
            // 对左边排序
            sort(arr, low, mid - 1);
            // 对右边排序
            sort(arr, mid + 1, high);
        }
        return arr;
    }

    /**
     * 划分数组获取枢纽元素位置
     * @param arr
     * @param low
     * @param high
     * @return
     */
    public static int partition(int[] arr, int low, int high) {
        int i = low - 1, j = high;
        // 以最后一位做为枢纽元素
        int pivot = arr[high];
        while (true) {
		    // 找从低坐标到比pivot大的值的坐标 (重点：比pivot大)
            while (i < j && arr[++i] < pivot) ;
			// 找从高坐标到比pivot小的值的坐标 (重点：比pivot小)
            while (j > 0 && arr[--j] > pivot) ;
            if (i < j) {
                swap(arr, i, j);
            } else {
                break;
            }
        }
		// 将枢纽元素换到正确的位置上
        swap(arr, i, high);
        return i;
    }

    /**
     * 交换位置
     */
    public static void swap(int[] arr, int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 3, 6, 8, 1, 2, 3, 11, 52, 32, 11, 23};
        // 初始化最高和最低两个坐标
        int low = 0, high = arr.length - 1;
		System.out.println(Arrays.toString(sort(arr, low, high)));        
    }
}

时间复杂度

快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是$O(n)$，而整个快速排序算法的时间复杂度与划分的趟数有关。
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2^n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为$O(nlog2^n)$。
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为$O(n^2)$。