介绍

快速排序是由东尼·霍尔所发展的一种排序算法,该算法采用了“分治思想”,同时快速排序由于排序效率在同为O(n*logn)的几种排序方法中效率较高,因此经常被采用。

时间复杂度:

  • 最好情况:O(nlogn)
  • 平均情况:O(nlogn)
  • 最坏情况:O(n^2)

稳定性:不稳定(不稳定发生在基准元素flagarr[index+1]交换时)

额外的空间:O(logn)~O(n)

过程

  1. 从序列中将某一个元素(通常为最后一个)作为基准
  2. 大于基准的元素放在基准的右边,小于基准的元素放在基准的左边,将一个序列分为两个序列,该过程为称为分区
  3. 对于每个分区,递归执行步骤1、2,直至序列大小为0或1时跳出递归,此时排序已经完成

文字描述可能不够形象,看图示更能理解:

371-14

Java实现

/*
 * QuickSort.java:快速排序
 */
import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] a = new int[]{9, 2, 5, 6, 7, 2, 4, 5};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    //快速排序
    private static void quickSort(int[] arr, int left, int right) {
        //当左边大于或等于右边此时分区大小为0或1时跳出递归
        if (left >= right) {
            return;
        }
        int flagIndex = partition(arr, left, right);//设置基准索引
        //从左往右递归
        quickSort(arr, left, flagIndex - 1);
        quickSort(arr, flagIndex + 1, right);
    }

    //划分数组并返回基准索引
    private static int partition(int[] arr, int left, int right) {
        int flag = arr[right];//将最后一个元素设置为基准
        int index = left - 1;//左边第一个元素的前一个元素索引
        for (int i = left; i < right; i++) {
            //若小于基准则将其排到前面
            if (arr[i] <= flag) {
                swap(arr, ++index, i);
            }
        }
        swap(arr, index + 1, right);//将基准插入到正确位置
        return index + 1;//返回基准索引
    }

    //交换数组元素
    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
最后修改:2021 年 04 月 15 日 09 : 41 PM
如果觉得我的文章对你有用,请随意赞赏