基础排序参考
https://blog.csdn.net/yushiyi6453/article/details/76407640
快速排序
快速排序从小到大排序：在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边，大于此数的放在右边，再对数组两边递归调用快速排序，重复这个过程。
代码实现
package quicksort;
import java.util.Random;
import java.util.Scanner;
/**
* @author WangXiaoeZhe
* @Date: Created in 2019/11/21 18:54
* @description:
*/
public class QuickSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] arr = new int[5];
for (int i = 0; i < arr.length; i++) {
arr[i] = scanner.nextInt();
}
int[] ints = quickSort(arr, 0, arr.length - 1);
for (int i = 0; i < ints.length; i++) {
System.out.println(ints[i]);
}
}
/**
*
* 普通快排
* @param arr
* @param l
* @param r
* @return
*/
private static int[] quickSort(int[] arr, int l, int r) {
int i, j, temp;
if (l > r) {
return arr;
}
temp = arr[l];
i = l;
j = r;
while (i != j) {
while (arr[j] >= temp && i < j) {
j--;
}
while (arr[i] <= temp && i < j) {
i++;
}
if (i < j) {
swap(arr, i, j);
}
}
/**
* 基准归为
*/
arr[l]=arr[i];
arr[i]=temp;
/**
* 递归
*/
quickSort(arr,l,i-1);
quickSort(arr,i+1,r);
return arr;
}
/**
* 随机快排
* @param arr
* @param l
* @param r
* @return
*/
public static int[] randomQuickSort(int[] arr, int l, int r) {
int i, j,temp;
if (l > r) {
return arr;
}
/**
* 随机快排
*/
Random random = new Random();
int tp = random.nextInt(r - l + 1) + l;
swap(arr, l, tp);
temp = arr[l];
i = l;
j = r;
while (i != j) {
while (arr[j] >= temp && i < j) {
j--;
}
while (arr[i] <= temp && i < j) {
i++;
}
if (i < j) {
swap(arr, i, j);
}
}
/**基准归位*/
arr[l] = arr[i];
arr[i] = temp;
/**递归*/
randomQuickSort(arr, l, i - 1);
randomQuickSort(arr, i + 1, r);
return arr;
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
平均时间复杂度：O（n*logn） 最坏时间复杂度：O（n^2） 空间复杂度：O（logn） 稳定