“快速排序”(Quicksort )是泡沫排序的改进。 快速排序是rrdzc在1960年提出的。 其基本思想是，将排序后的数据用一次排序分割成独立的两个部分，其中一个部分的所有数据小于其他部分的所有数据，然后用该方法分别高速地对两个部分的数据进行排序，从而递归地对整个排序过程进行排序本文将基数：指数组中的一个因素，数组中的其他因素均与其因素进行比较，基数以下的部分放在基数左边，大于基数的部分放在基数右边
白话说，快速排序有一种气泡排序的思想，先以一个数字为准，再以下的数全部放在其左侧，再大的数全部放在其右侧，其位置其实已经确定，左右两个部分分别以一个数为准直接看上面的照片：
照片太大了，只能分别上传。
初学者看这个排序算法很辛苦，但没关系。 耐心地继续读这个博客，自己敲几下，就一定会记住的。
普通的快速排序其实涉及到分治的思想，即每次循环时，把小于或等于的东西放在左边，把大于或等于的东西放在右边。 以该部分以下，以该部分最右边的数字为基数，继续将以下的向左侧放置，将大于该部分的向右侧放置，大于该部分的也同样。 概略图如下。
代码package com.bean.com.bean.sort alg； import java.util.Arrays； publicclassquicksortdemo { publicstaticvoidquicksort (int [ ] arr ) if ) arr==null|||arr.length2) return； 快速排序(arr，0，arr.length - 1 )； } publicstaticvoidquicksort (int [ ] arr、int left、int right (if ) leftright ) )//随机快速排列。 这叫做swap(arr，left(int ) )。 int[]p=partition(ARR、left、right； 快速排序(arr，left，p[0] - 1 )； 快速排序(arr，p[1] 1，right )； (/) /中排名区间public static int [ ] partition (int [ ] arr，int left，int right ) ) intless=left-1； int more=right； while(leftmore ) if ) arr[left]arr[right] ) swap ) arr，less，left )； }elseif(arr[left]arr[right] ) swap ) arr，--more，left )； }else left； }swap(arr、more、right )； 返回新int [ ] { less 1，more}； //更换位置publicstaticvoidswap(int[]arr，int a1，int a2 ) ) { int temp=arr[a1]； arr[a1]=arr[a2]； arr[a2]=temp； //正确的排序方法publicstaticvoidcomparator (int [ ] arr ) Arrays.sort ) arr； //随机数组public static int [ ] generaterandomarray (int maxsize，int maxnum (int ) ) arr=newint ) ) int (.random ) ) matar i arr.length； I () arr[I]=(int ) ) Math.random ) * maxNum 1)- (int ) Math.random ) )； }返回arr； //数组公共静态int [ ] copy array (int [ ] arr ) if ) arr==null ) { return null； (I
nt[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; }//判断两个数组是否相同 public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; }//打印数组内容 public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int testTime = 500000; int maxSize = 20; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); QuickSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "成功!" : "有错。。"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); QuickSort(arr); printArray(arr); }} 加了swap(arr, left + (int)(Math.random() * (right - left + 1)), right);这句话就是随机快排为什么？我们先分析一下普通快速排序的时间复杂度，很简单，因为用到了分治思想，所以T(n) = 2T(N/2) + O(n)，不知道这是什么意思请点击这里，所以时间复杂度为N*logN，可是仔细想一下，如果顺序为1 2 3 4 5 6 7，那岂不是每次都需要变换位置，跟冒泡排序不就完全一样了，丝毫没有增加效率，时间复杂度为O(N²)，为了避免这种分区域太极限了，所以我们不每次只跟数组的最后一个元素进行比较，而是从数组中随机选一个元素为基数。所以随机快排的时间复杂度就是一个概率事件了，它的数学期望是NlogN，算法上比普通快排更优。
理解原理后动手多敲几遍，多跟几遍debug才能彻底搞懂哦！