java代码的快速排序理解

 1 package changesort;
 2 
 3 
 4 public class MyQuickSort {
 5 
 6     //冒泡排序交换相邻元素消除一个逆序，快速排序通过两个不相邻元素的交换，可能消除多个逆序
 7     public static void sort(int arr[],int low, int high) {
 8         if(low<high) {
 9             int pos = partition(arr,low,high);
10             sort(arr, low, pos-1);
11             sort(arr, pos+1, high);
12         }        
13     }
14     //选取第一个元素为枢轴，给pivot找一个位置，保证pivot左边的比它小,pivot右边的比它大，通过递归直到分割的子表长度为1
15     public static int partition(int arr[],int low , int high) {
16         int pivot = arr[low];//pivot存储arr[low]的值，low这个位置可以存放右边第一个小于pivot的值
17         while(low<high) {
18             while(low<high && arr[high]>=pivot) {
19                 high--;
20             }
21             if(low<high) {
22                 arr[low] = arr[high];//将右边第一个小于pivot的值给arr[low],high这个位置空了
23                 low++;
24             }
25             
26             while(low<high && arr[low]< pivot) {//没有等于号时(3,3,3,1,2)证明不稳定,有等于号时(3,3,2)证明不稳定
27                 low++;
28             }
29             if(low<high){
30                 arr[high] = arr[low];//将左边第一个大于pivot的值给arr[high],low这个位置空了
31                 high--;
32             }
33         }
34         arr[low] = pivot;//low已经等于high了，pivot找到了它的位置
35         return low;
36     }
37 
38 }

时间复杂度：

快速排序取决于递归深度

最坏情况：已经排好顺序，O(n²)

最好情况：每次序列一分为二，O(nlog₂n),完全二叉树