这都可以（java实现快速排序算法）java快速排序怎么排，使用 Java 实现快速排序（详解），快速排序算法java，
一、概述
最近在看一些面试题，发现很多面试过程中都会要求手写快速排序，查阅一些博客发现别人写的并不是特别清楚而且也很难记住，所以为了更好的掌握这个算法，所以在这篇文章中，将自己的学习过程记录下来，你将学习到快速排序算法和使用 Java 如何实现快速排序。
快速排序是一种基于分而治之的排序算法，其中：1、通过从数组中选择一个中心元素将数组划分成两个子数组，在划分数组时，将比中心元素小的元素放在左子数组，将比中心元素大的元素放在右子数组。2、左子数组和右子数组也使用相同的方法进行划分，这个过程一直持续到每个子数组都包含一个元素为止。3、最后，将元素组合在一起以形成排序的数组。
中心元素（pivot element)：有的地方翻译为：枢轴元素、基元，基准元素，我这里就叫做中心元素
二、快速排序算法的工作原理
1、选择中心元素
选择不同位置的中心元素，快速排序就有不同的变体，比如可以选择：第一个元素、最后一个元素以及左端、右端和中心位置上的三个元素的中值作为中心元素，在这里，我们将选择数组的最后一个元素作为中心元素。
2、重新排列数组
现在重新排列数组，将比中心元素小的放在左边，比中心元素大的放在右边。
重新排列数组的方法如下：1、指针固定在中心元素上，将中心元素与从第一个索引开始的元素进行比较。
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 pivotIndexstoreIndex <- leftmostIndex - 1for i <- leftmostIndex + 1 to rightmostIndexif element[i] < pivotElementswap 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算法
编程语言适合递归时间复杂度很重要空间复杂性很重要本文由博客群发一文多发等运营工具平台 OpenWrite 发布
版权申明
本文系作者 @河马 原创发布在河马博客站点。未经许可，禁止转载。
暂无评论数据