快速排序 发表于 2018-06-09 | 分类于 简单算法 介绍 核心是跳位比较和交换随机的在数组中选一个数,小于等于它的数,统一放在这个数的左边,大于等于它的数,统一放在这个数的右边,接下来对左右两个部分,分别递归的调用快速排序的过程,这样整个数组就有序了。 指标时间复杂度 O(n*logn)空间复杂度O(logn) 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465public class QuickSort { public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int l, int r) { if (l < r) { // 随机选择pivot,并且放在尾部 swap(arr, l + (int) (Math.random() * (r - l + 1)), r); // 空间复杂度O(logn),是能二分的次数,要记录每次压栈的位置 int[] p = partition(arr, l, r); // patition返回值是等于p区域的起止下标,下面分别对 小于和大于区域 快排 quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); } } public static int[] partition(int arr[], int left, int right) { int index = left; // 当前位置索引 int less = left - 1; // 小于区域 int more = right; // 大于区域 // ---------------往 小于区 和 大于区 “发货 ”-------------- while (index < more) { // 当前位置一直往右推移,一定会遇到大于区域 if (arr[index] < arr[right]) {// ------ arr[right]就是pivot----- // 当前位置的数与小于区域的下一个数交换,然后当前位置下移一位 (扩大小于区域) swap(arr, index++, ++less); } else if (arr[index] > arr[right]) { // 当前位置的数与大于区域的前一个数交换,因为刚交换过来的数不知道大小,所以需要继续比较 swap(arr, index, --more); } else { // 等于的情况只需要当前位置下移一位 index++; } } swap(arr, more, right); // 返回一个等于区域的左右边界 return new int[] { less + 1, more }; } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } private 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[] arr = new int[] { 3, 5, 4, 2, 6, 7, 1, 9, 8 }; quickSort(arr); printArray(arr); }} 输出