面试官：手写一个快速排序吧（Java实现）_Java_快速排序 - 小郝不负流年

快速排序基于分治思想，它的时间平均复杂度很容易计算得到为O(NlogN)。

思路：

从数列中挑出一个元素，称为“基准”，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

实现代码：

package cn.hoscen.demo.sort;
import java.util.Arrays;
/**
* Description: 手写快速排序算法分治法 -- 升序排序
* 从数列中挑出一个元素，称为“基准”
* 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，
* 该基准是它的最后位置。这个称为分割（partition）操作。
* 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
* Created by Hoscen on 2021/3/16 21:39 with IntelliJ IDEA.
*/
public class QuickSort {
public static void main(String[] args) {
int[] arrs = {49, 38, 65, 97, 76, 13, 27, 78, 34};
// int[] arrs = {49, 38, 65};
System.out.println(Arrays.toString(arrs));
int[] sortArrs = quickSort(arrs);
System.out.println(Arrays.toString(sortArrs));
}
private static int[] quickSort(int[] arrs) {
if (arrs == null || arrs.length < 1) {
return null;
}
if (arrs.length == 1) {
return arrs;
}
if (arrs.length == 2) {
if (arrs[0] > arrs[1]) {
int tmp = arrs[0];
arrs[0] = arrs[1];
arrs[1] = tmp;
}
return arrs;
}
sort(arrs, 0, arrs.length - 1);
return arrs;
}
private static void sort(int[] arrs, int startIndex, int endIndex) {
if (startIndex < endIndex) {
int partition = partition(arrs, startIndex, endIndex);
sort(arrs, startIndex, partition - 1);
sort(arrs, partition + 1, endIndex);
}
}
/**
* sort 返回中轴下标
* Created by Hoscen on 2021/3/16 21:43
*
* @param arrs
* @param startIndex
* @param endIndex
* @return int
*/
private static int partition(int[] arrs, int startIndex, int endIndex) {
int temp = arrs[startIndex];
while (startIndex < endIndex) {
while (startIndex < endIndex && arrs[endIndex] >= temp) {
endIndex--;
}
arrs[startIndex] = arrs[endIndex];
while (startIndex < endIndex && arrs[startIndex] <= temp) {
startIndex++;
}
arrs[endIndex] = arrs[startIndex];
}
arrs[startIndex] = temp;
return startIndex;
}
}