一、概述

最近在看一些面试题，发现很多面试过程中都会要求手写疾速排序，查阅一些博客发现他人写的并不是特地分明而且也很难记住，所以为了更好的把握这个算法，所以在这篇文章中，将本人的学习过程记录下来，你将学习到疾速排序算法和应用 Java 如何实现疾速排序。

疾速排序是一种基于分而治之的排序算法，其中：
1、通过从数组中抉择一个核心元素将数组划分成两个子数组，在划分数组时，将比核心元素小的元素放在左子数组，将比核心元素大的元素放在右子数组。
2、左子数组和右子数组也应用雷同的办法进行划分，这个过程始终继续到每个子数组都蕴含一个元素为止。
3、最初，将元素组合在一起以造成排序的数组。

核心元素（pivot element)：有的中央翻译为：枢轴元素、基元，基准元素，我这里就叫做核心元素

二、疾速排序算法的工作原理

1、抉择核心元素

抉择不同地位的核心元素，疾速排序就有不同的变体，比方能够抉择：第一个元素、最初一个元素以及左端、右端和核心地位上的三个元素的中值作为核心元素，在这里，咱们将抉择数组的最初一个元素作为核心元素。

2、重新排列数组

当初重新排列数组，将比核心元素小的放在右边，比核心元素大的放在左边。

重新排列数组的办法如下：
1、指针固定在核心元素上，将核心元素与从第一个索引开始的元素进行比拟。

2、如果该元素大于核心元素，则为该元素设置第二指针。

3、当初将核心元素与其余元素进行比拟，如果达到的元素小于核心元素，则将较小的元素和上次找到的较大元素替换地位。

4、同样，反复该过程以将下一个更大的元素设置为第二指针，并且将其和另一个较小的元素替换地位。

5、该过程始终进行到达到倒数第二个元素为止。

6、最初将核心元素与第二个指针指向的元素替换地位。

3、划分子数组

再次别离为左子局部和右子局部抉择了核心元素，并且反复步骤2，子数组被宰割，直到每个子数组只有一个元素，至此，该数组曾经通过疾速排序算法升序排好序了。

4、疾速排序可视化插图阐明

能够借助以下插图理解疾速排序算法的工作原理。

三、疾速排序算法伪代码

1、伪代码阐明

quickSort(array, leftmostIndex, rightmostIndex)  if (leftmostIndex < rightmostIndex)    pivotIndex <- partition(array,leftmostIndex, rightmostIndex)    quickSort(array, leftmostIndex, pivotIndex - 1)    quickSort(array, pivotIndex, rightmostIndex)partition(array, leftmostIndex, rightmostIndex)  set rightmostIndex as pivotIndex  storeIndex <- leftmostIndex - 1  for i <- leftmostIndex + 1 to rightmostIndex  if element[i] < pivotElement    swap element[i] and element[storeIndex]    storeIndex++  swap pivotElement and element[storeIndex+1]return storeIndex + 1

四、Java 实现疾速排序

Java 实现疾速排序的代码如下：

public class QuickSort {    public static int partition(int[] array, int low, int high) {        // 取最初一个元素作为核心元素        int pivot = array[high];        // 定义指向比核心元素大的指针，首先指向第一个元素        int pointer = low;        // 遍历数组中的所有元素，将比核心元素大的放在左边，比核心元素小的放在右边        for (int i = low; i < high; i++) {            if (array[i] <= pivot) {                // 将比核心元素小的元素和指针指向的元素替换地位                // 如果第一个元素比核心元素小，这里就是本人和本人替换地位，指针和索引都向下一位挪动                // 如果元素比核心元素大，索引向下挪动，指针指向这个较大的元素，直到找到比核心元素小的元素，并替换地位，指针向下挪动                int temp = array[i];                array[i] = array[pointer];                array[pointer] = temp;                pointer++;            }            System.out.println(Arrays.toString(array));        }        // 将核心元素和指针指向的元素替换地位        int temp = array[pointer ];        array[pointer] = array[high];        array[high] = temp;        return pointer;    }    public static void quickSort(int[] array, int low, int high) {        if (low < high) {            // 获取划分子数组的地位            int position = partition(array, low, high);            // 左子数组递归调用            quickSort(array, low, position -1);            // 右子数组递归调用            quickSort(array, position + 1, high);        }    }    public static void main(String[] args) {        int[] array = {6,72,113,11,23};        quickSort(array, 0, array.length -1);        System.out.println("排序后的后果");        System.out.println(Arrays.toString(array));    }}

排序过程的后果如下：

[6, 72, 113, 11, 23][6, 72, 113, 11, 23][6, 72, 113, 11, 23][6, 11, 113, 72, 23][6, 11, 23, 72, 113][6, 11, 23, 72, 113]排序后的后果[6, 11, 23, 72, 113]

从这个排序后果咱们能够晓得整个排序过程。

五、疾速排序的复杂性

1、工夫复杂度

• 最坏的状况复杂度[Big-O] ：
  当抉择的核心元素是最大或最小的元素时产生，这种状况导致核心元素位于已排序数组的最末端，一个子数组始终为空，而另一个子数组蕴含元素，因而，仅在此子数组上调用quicksort，疾速排序算法对于扩散的数据具备更好的性能。
• 最好的状况复杂度[Big-O] ：
  当核心元素始终是两头元素或凑近两头元素时，会产生这种状况。

• 均匀复杂度[Big-O] ：
  在不呈现上述条件时产生。

  2、空间复杂度

  疾速排序的空间复杂度为O(log n)。

六、疾速排序的利用

在以下状况下应用Quicksort算法

• 编程语言适宜递归
• 工夫复杂度很重要
• 空间复杂性很重要