常见排序算法之快速排序

文章目录

1、概述

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2、代码实现

快速排序的方式有两种，主要的区别就是选择基准值的不同，但是他们的核心思想都是一样的，只是说我们在代码的是线上有一些区别

梳理核心思想：

选择一个基准值（我们这里选择的是 (头+尾)/2 的值）然后将基准值左边的数据和右边的数据进行位置的交换（不符合规范的数字）在基准值的右边，用同样的方式再选择出一个基准值，然后重复2步骤。同理左边也重复2然后不断地递归循环，直到剩下的数字不能再分为止

个人觉得，道理虽然简单，但是代码实现还是有一定的困难的，需要注意很多其他的点

public class QuickSortTest01 {public static void main(String[] args) {int[] arr = {1, 23, 5, 6,3, 3, 52, 1};quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}public static void quickSort(int[] arr, int left, int right) {int l = left;int r = right;//1.将中间的那个值设置为基准值int pivot = arr[(left + right) / 2];int temp;while (l < r) {//2.如果右边的数字比我们的基准值大，说明符合要求，那么我们就将下标前移while (arr[r] > pivot) {r--;}//3.如果左边的数字比我们的基准值小，说明符合要求，那么我们就将下标后移while (arr[l] < pivot) {l++;}//4.因为前面在移动下标，为了避免移动过头，需要设置对应的跳出while循环if (l >= r) {break;}//5.拿到我们两个不符合的数字，并且完成交换temp = arr[r];arr[r] = arr[l];arr[l] = temp;//6.这两条语句，目的是为了让与基准值相同的数据，不断地向中间靠拢//一旦这两条if语句中有一条被执行了，那么上面地while循环就会有一个不会被执行到// 每一次的交换数字都是为一个不符合规范的数字，一个与基准值相同的数字，继而达到了基准值向中间靠拢的目的if(arr[l] == pivot) {r--;}if(arr[r] == pivot) {l++;}}//7.防止栈溢出//添加此句的目的是为了，递归排序的时候，将我们的基准值抛开，不然会进入死循环if(l == r) {l++;r--;}//8.左边进行递归排序if (left < r) {quickSort(arr, left, r);}//9.右边进行递归排序if (right > l) {quickSort(arr, l, right);}}}

3、测试案例

利用我们以有的条件，进行一个小案例的测试：计算将数组长度为80000的乱序数组排序所花费的时间

public class QuickSortTest02 {public static void main(String[] args) {int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random() * 80000);}long start = System.currentTimeMillis();quickSort(arr, 0, arr.length - 1);long end = System.currentTimeMillis();System.out.println("快速排序花费的时间是:" + (end - start));}public static void quickSort(int[] arr, int left, int right) {int l = left;int r = right;//将中间的那个值设置为基准值int pivot = arr[(left + right) / 2];int temp;while (l < r) {while (arr[r] > pivot) {r--;}while (arr[l] < pivot) {l++;}if (l >= r) {break;}temp = arr[r];arr[r] = arr[l];arr[l] = temp;if (arr[l] == pivot) {r--;}if (arr[r] == pivot) {l++;}}if (l == r) {l++;r--;}if (left < r) {quickSort(arr, left, r);}if (right > l) {quickSort(arr, l, right);}}}

不得不说，该方式的速度超过了希尔排序，但是它的缺点就是，代码实现比较复杂，代码思路需要多多体会

如果觉得《常见排序算法之快速排序》对你有帮助，请点赞、收藏，并留下你的观点哦！