Java学习笔记——排序算法之快速排序

会当凌绝顶，一览众山小。

　　　　　　　　　　——望岳

如果说有哪个排序算法不能不会，那就是快速排序（Quick Sort）了

快速排序简单而高效，是最适合学习的进阶排序算法。

直接上代码：

 1 public class QuickSort {
 2 
 3     public static void quickSort(int[] arr){
 4         qSort(arr,0,arr.length - 1);
 5     }
 6     public static void qSort(int[] arr, int l, int r) {
 7         int i = l;
 8         int j = r;
 9         // l<r 进入,否则return
10         if (i < j) {
11             while (i < j) {
12                 while (i < j) {
13                     if (arr[j] < arr[i]) {
14                         arr[j] = arr[j] ^ arr[i];
15                         arr[i] = arr[j] ^ arr[i];
16                         arr[j] = arr[j] ^ arr[i];
17                         break;
18                     }
19                     j--;
20                 }
21                 if (i == j) {
22                     break;
23                 }
24                 i++;
25 
26                 while (i < j) {
27                     if (arr[i] > arr[j]) {
28                         arr[j] = arr[j] ^ arr[i];
29                         arr[i] = arr[j] ^ arr[i];
30                         arr[j] = arr[j] ^ arr[i];
31                         break;
32                     }
33                     i++;
34                 }
35                 if (i == j) {
36                     break;
37                 }
38                 j--;
39             }
40 
41             qSort(arr, l, i);//递归
42             qSort(arr, j + 1, r);
43         }
44     }
45 }

想象一个简单的int[] arr = {2,3,1}

第一趟：{1,3,2}，i=1

第二趟：{1,2,3}，j=1

跳出循环，执行qSort(0,1)和qSort(2,2)

qSort(0,1)，循环一次后执行qSort(0,0)和qSort(1,1)，分别return

qSort(2,2)直接return，排序完成。

最后附上算法比较：