如何实现快速排序

本篇内容介绍了“如何实现快速排序”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

概述

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。

算法步骤

1. 从数列中挑出一个元素，称为 "基准"（pivot）;

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

先来看一下分区操作：

原始数组：

我们把数组的第一个元素 ‘5’ 作为"基准"，然后在基准后面第一个元素的位置定义两个指针 “i”、“j” 指针“i”从左至右移动，每移动一下，需要比较“i”位置元素与基准值的大小，如果小于基准值，则执行一次“swap”，即交换“i”，“j”这两个位置的元素的值；另外，每执行一次“swap”，“j”的值加一。

ok，“j”暂时不动，“i”往后移动，当“i”移动到“1”的位置时，

此时，“1”小于基准值“5”，需要执行一次“swap”,同时"j"加一

以此类推，当“i”移动到最右侧时，结果如下：

此时我们只需要，交换“基准值”和“j”的前一个位置的值（也就是交换5 和 2），就能达到”分区“的效果，

我看可以看到所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面；

仔细观察会发现，指针“i”用来扫描数组元素，指针“j”的左侧始终时比基准小的元素，这也是为什么基准值要与“j”前一个元素交换。

至此，一轮“分区”操作完成。

我们来看整个过程：

代码：

    public static int[] sort(int[] arr) {
        return quickSort(arr, 0, arr.length - 1);
    }

    private static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //分区
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = left;
        //指针 j
        int j = pivot + 1;
        for (int i = j; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, j);
                j++;
            }
        }
        swap(arr, pivot, j - 1);
        return j - 1;
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

“如何实现快速排序”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！