基本排序算法 - 快速排序

基本排序算法 - 快速排序

快速排序基本思想

快速排序是冒泡排序的改进。它通过一轮排序将要排序的数据分为独立的两部分，其中一部分都比另外一部分小，然后分别对两部分再进行快排（可递归），直到各区间只有一个数快速排序结束。

图示与代码

public class QuickSort {public static void main(String[] args) {int[] arr = {6, 21, 5, 9, 10, 2, 16};int len = arr.length;int left = 0;int right = len - 1;System.out.println("原数组：" + Arrays.toString(arr));quickSort(arr, left, right);System.out.println("排序后：" + Arrays.toString(arr));}private static void quickSort(int[] arr, int left, int right) {int l = left;int r = right;// 基准值 midint mid = arr[(left + right) / 2];int temp = 0;while (l < r) {// 退出while时，就在mid左侧找到了大于等于mid的值的下标while (arr[l] < mid) {l++;}// 退出while时，就在mid右侧找到了小于等于mid的值的下标while (arr[r] > mid) {r--;}/*** 如果left >= right，说明mid左右两边的值* 已经左边全小于mid，右边全大于mid*/if (l >= r) {break;}// 将左边大于mid的值与右边小于mid的值交换temp = arr[l];arr[l] = arr[r];arr[r] = temp;// 交换后若 arr[l] == mid,r--前移if (arr[l] == mid) {r--;}// 交换后若 arr[r] == mid,l++后移if (arr[r] == mid) {l++;}}// 若left == right,必须left++,right--,否则会出现栈溢出if (l == r) {l++;r--;}// 左递归if (left < r) {quickSort(arr, left, r);}// 右递归if (right > l) {quickSort(arr, l, right);}}}

基本排序算法 - 快速排序

快速排序基本思想

快速排序是冒泡排序的改进。它通过一轮排序将要排序的数据分为独立的两部分，其中一部分都比另外一部分小，然后分别对两部分再进行快排（可递归），直到各区间只有一个数快速排序结束。

图示与代码

public class QuickSort {public static void main(String[] args) {int[] arr = {6, 21, 5, 9, 10, 2, 16};int len = arr.length;int left = 0;int right = len - 1;System.out.println("原数组：" + Arrays.toString(arr));quickSort(arr, left, right);System.out.println("排序后：" + Arrays.toString(arr));}private static void quickSort(int[] arr, int left, int right) {int l = left;int r = right;// 基准值 midint mid = arr[(left + right) / 2];int temp = 0;while (l < r) {// 退出while时，就在mid左侧找到了大于等于mid的值的下标while (arr[l] < mid) {l++;}// 退出while时，就在mid右侧找到了小于等于mid的值的下标while (arr[r] > mid) {r--;}/*** 如果left >= right，说明mid左右两边的值* 已经左边全小于mid，右边全大于mid*/if (l >= r) {break;}// 将左边大于mid的值与右边小于mid的值交换temp = arr[l];arr[l] = arr[r];arr[r] = temp;// 交换后若 arr[l] == mid,r--前移if (arr[l] == mid) {r--;}// 交换后若 arr[r] == mid,l++后移if (arr[r] == mid) {l++;}}// 若left == right,必须left++,right--,否则会出现栈溢出if (l == r) {l++;r--;}// 左递归if (left < r) {quickSort(arr, left, r);}// 右递归if (right > l) {quickSort(arr, l, right);}}}