算法原理：利用分治思想

对数组A[p…r]进行快速排序的三步分治过程：
一、分解：
数组 A[p…r]被划分为两个(可能为空)子数组 A[p…q-1]和 A[q+1…r]，使得A[p…q – 1]中的每一个元素都小于等于 A[q]，而 A[q]也小于等于 A[q+1…r]中的每个元素其中，计算下标 q也是划分过程的一部分。
算法的关键部分是Partition过程，它实现了对子数组A[p…r]的原址重排
二、解决
通过递归调用快速排序，对子数组 A[p…q-1]和 A[q+1…r]进行排序。
三、合并
因为子数组都是原址排序的，所以不需要合并操作:数组 A[p…r]已经有序

伪代码实现

快排主入口

代码实现：

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

分片

代码实现：这里实现稍微有一点点不同，我是从0开始的，伪代码里面的i是从1开始

public static int partition(int [] a, int p, int r) {
        int pivot = a[r];
        int i = p;  // 从0开始的

        for (int j = p; j  r; j++) {
            if (a[j]  pivot) {
                exchange(a, i, j);
                i++;
            }
        }
        exchange(a, i, r);
        return i;
    }

快速排序执行流程

1、从数组中选择一个轴点元素 (pivot)
假设每次选择最后一个位置的元素为轴点(算法导论上就是这样)
2、利用pivot将数组分割成两个子数组将小于pivot的元素放到pivot前面(左侧)
将大于pivot的元素放在pivot后面(石侧)
等于pivot的元素放哪边都可以(算法导论放在左边)
3、对子数组重复进行1 2步操作直到数组不能再分割 (子数组中只剩下一个元素）

快速排序的本质:逐渐将每一个元素都转换成轴点元素，直到子数组只剩下一个元素而无法转换

Java完整代码实现

public class QuickSort {
    private static void exchange(int[] a, int largest, int i) {
        int temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
    }

    public static int partition(int [] a, int p, int r) {
        int pivot = a[r];
        int i = p;  // 从0开始的

        for (int j = p; j  r; j++) {
            if (a[j]  pivot) {
                exchange(a, i, j);
                i++;
            }
        }
        exchange(a, i, r);
        return i;
    }

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

    public static void main(String[] args) {
        int arr [] = new int[]{1, 5, 7, 3, 4, 10, 9, 8, 6};
        quickSort(arr, 0, arr.length - 1);  // 这里传入值是从0开始的
        for (int a :
                arr) {
            System.out.print(a + " ");
        }
    }
}

快速排序随机化优化

已经知道快速排序在对已经排好序或者已经逆序输入进行排序，结果会不好，我们可以最输入进行随机化一下。但是目前，我感觉使用场景不多，不过可以试试，随机化后就打乱了原始有序或逆序的情况，避免快排的最坏情况。

总结

对于n个输入，时间复杂度为：O(nlogn)，空间复杂度为使用原址排序。
快速排序每一轮都会确定某些元素的最终位置。
如果数据已经排好序或者已经逆序的话，原始的快排算法效率不高。一边拥有剩下的所有元素，另外一边没有元素，时间复杂度为O(n^2).
快速排序的平均运行时间更接近于其最好情况，而不是最坏情况。

ps:计划每日更新一篇博客，今日2023-04-24，日更第八天，昨日更新：
冒泡排序
选择排序
插入排序
归并排序

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

快速排序详解算法原理：利用分治思想伪代码实现快速排序执行流程 Java完整代码实现快速排序随机化优化总结

文章目录