目录

要求代码复杂度时间复杂度空间复杂度 稳定性分析

要求

将数值数组按从小到大排序。

代码

public class Quick { public static void sort(Comparable[] a) { int lo = 0; int hi = a.length - 1; quicksort(a, lo, hi); } private static void quicksort(Comparable[] a, int lo, int hi) { if (lo >= hi) return; Comparable key = a[lo]; // 把最左边的元素当作基准值 int left = lo; // 定义一个左指针，初始指向最左边的元素 int right = hi; // 定义一个右指针，初始指向最右侧元素 // 进行切分 while(left < right){ // 先从右往左扫描，找到一个比基准值小的元素 while(less(key,a[right]) && left < right){ right--; } // 再从左往右扫描，找一个比基准值大的元素 while (less(a[left],key) && left < right){ left++; } //交换left和right索引处的元素 exch(a,left,right); } // 交换最后left索引处和基准值所在索引处的值 exch(a, lo, left); // 继续迭代 quicksort(a, lo, left - 1); quicksort(a, left + 1, hi); } // 比较v元素是否小于等于w元素 private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) <= 0; } // i索引和j索引处的元素互换 private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } } public class Test { public static void main(String[] args) throws Exception { Integer[] arr = {8,6,1,2,7,40,8,56,21,88}; Quick.sort(arr); System.out.println(Arrays.toString(arr)); } } [1, 2, 6, 7, 8, 8, 21, 40, 56, 88]

复杂度

时间复杂度

最好情况O(nlogn)，最坏情况O(n^2)，平均O(nlogn)

空间复杂度

O(logn)

稳定性分析

不稳定