快速排序
快速排序 是随机选中其中一个元素，进行元素筛选 一遍一遍将小于这个元素的放在左边，把大于元素的放在右边
之后两边再分别随机选择出来一个而元素继续上述操作
- 选出对比元素，可以固定可以随机 可能会影响效率
- 小的放在左边，大的放在右边
- 持续递归
- 拼接返回
动态图
理解实例
简易方便理解版本的快排
利用集合来演示快排
这个效率不会很好，但是很适合我们来理解快速排序的思路
public static ArrayList<Integer> quickSort(ArrayList<Integer> arr) { if (arr == null || arr.size() <= 1) { return arr; } int leader = arr.get(0); //存放左右的结果 ArrayList<Integer> left = new ArrayList<>(); ArrayList<Integer> right = new ArrayList<>(); for (int i = 1; i < arr.size(); i++) { //根据左右条件添加 if (arr.get(i) <= leader) { left.add(arr.get(i)); } else { right.add(arr.get(i)); } } //递归 ArrayList<Integer> leftResult = quickSort(left); ArrayList<Integer> rightResult = quickSort(right); // 合并 ArrayList<Integer> result = new ArrayList<>(); result.addAll(leftResult); result.add(leader); result.addAll(rightResult); return result; }
标准版本
标准版的思路和简易版本有一定区别
这里是有两个指针一个指向前面 一个指向后面。根据选出的值来从右往左找小于这个数的值移动，之后从左边找大于值的数移动到右边，每一次交换两个数分别放在左右两边，直到左右指针相遇 就将这个数值放在相遇点，直到有序为止。
图解
重复这个过程一直到有序为止，
我们只需要编写一个定位方法，第一次就按照上图来讲low位置的左右两边交换好
之后只需要出去中位，左右递归就可以排序好数列了，至此百万数字秒级排序的快速排序思路完成
代码实现
package com.hyc.algorithm.sort; import java.util.ArrayList; /** * @projectName: DataStructure * @package: com.hyc.algorithm.sort * @className: QuickSort * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2022/4/3 23:30 * @version: 1.0 */ public class QuickSort { public static void main(String[] args) { //ArrayList<Integer> arr = new ArrayList<>(); //arr.add(3); //arr.add(1); //arr.add(9); //arr.add(2); //arr.add(6); //arr.add(8); //arr.add(7); //arr.add(5); //System.out.println(quickSort(arr)); //int[] arr = {3, 1, 9, 2, 6, 8, 7, 5}; int[] test = new int[8000000]; //测试数据 for (int i = 0; i < 8000000; i++) { test[i] = (int) (Math.random() * 800000); } long time = System.currentTimeMillis(); quickSort(test); long end = System.currentTimeMillis(); long t = ((end - time) / 1000); System.out.println("一共用时 " + t + "秒"); } //简易版本 public static ArrayList<Integer> quickSort(ArrayList<Integer> arr) { if (arr == null || arr.size() <= 1) { return arr; } int leader = arr.get(0); //存放左右的结果 ArrayList<Integer> left = new ArrayList<>(); ArrayList<Integer> right = new ArrayList<>(); for (int i = 1; i < arr.size(); i++) { if (arr.get(i) <= leader) { left.add(arr.get(i)); } else { right.add(arr.get(i)); } } //递归 ArrayList<Integer> leftResult = quickSort(left); ArrayList<Integer> rightResult = quickSort(right); // 合并 ArrayList<Integer> result = new ArrayList<>(); result.addAll(leftResult); result.add(leader); result.addAll(rightResult); return result; } //标准版快速排序 public static void quickSort(int[] arr) { quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int low, int high) { if (low >= high) { return; } //已经交换过一次 中间值的为止不会变化了 int partPoint = partition(arr, low, high); //递归左边 quickSort(arr, low, partPoint - 1); //递归右边 quickSort(arr, partPoint + 1, high); } //进行一次左右换位 public static int partition(int[] arr, int low, int high) { int leader = arr[low]; while (low < high) { while (low < high && arr[high] >= leader) { //从右边寻找第一个小于leader的数字 high--; } // 交换值 arr[low] = arr[high]; while (low < high && arr[low] <= leader) { //从左边找到第一个大于leader的数字 low++; } arr[high] = arr[low]; } arr[low] = leader; return low; } }
效率版
思路和标准版一致
//速度优化之后的快速排序 public static void optimizeQuickSort(int[] arr, int low, int high) { int l = low; int r = high; int pivot = arr[l + r / 2]; int temp = 0; while (l < r) { while (arr[l] < pivot) { l += 1; } while (arr[r] > pivot) { r -= 1; } if (l >= r) { break; } temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; if (arr[l] == pivot) { r -= 1; } if (arr[r] == pivot) { l += 1; } } //防止栈溢出 if (l == r) { l += 1; r -= 1; } //防止栈溢出，当low指针0 r = 0 的时候就不许要排序递归左边了， if (low < r) { quickSort(arr, low, r); } //当 高位大于 左边指针的时候 就需要向右边递归了 if (high > l) { quickSort(arr, l, high); } }
