快速排序

发表于 | 更新于 | 分类于

本篇简单讲述一下快速排序以及时间复杂度

006QzbZDly1g126p771soj30m80etn1i.jpg

快速排序

快速排序（Quick Sort）是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个（不相邻）记录的一次交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。

动画演示

图片来源：https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg

快速排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class QuickSort {
   public static void quickSort(int[] arr) {
      if (arr == null || arr.length < 2) {
         return;
      }
      quickSort(arr, 0, arr.length - 1);
   }
   private static void quickSort(int[] arr, int l, int r) {
      if (l < r) { // l == r 则结束递归
         // 随机选定一个值与最后一个值交换作为判定值(随机快排)
         swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
         int[] p = partition(arr, l, r);
         quickSort(arr, l, p[0] - 1);  // 对 < x 的区域继续排序
         quickSort(arr, p[1] + 1, r);  // 对 > x 的区域继续排序
      }
   }
   private static int[] partition(int[] arr, int l, int r) {
      int less = l - 1;
      int more = r;
      while (l < more) {
         if (arr[l] < arr[r]) {
            swap(arr, ++less, l++);
         } else if (arr[l] > arr[r]) {
            swap(arr, --more, l);
         } else {
            l++;
         }
      }
      // 将最后一个值交换到 = x 和 > x 的边界
      swap(arr, more, r);
      // 返回等于区域两个边界的下标值
      return new int[] { less + 1, more };
   }
   public static void swap(int[] arr, int i, int j) {
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
   }
}

快速排序

上述代码中swap(arr, l + (int) (Math.random() * (r - l + 1)), r);该行代码随机选取一个值与最后一个值交换作为判断值（枢轴记录），这就是随机排序，是比较常用的快排算法。

经典快排在选取主元的时候，每次都选取最右边的元素。当序列为有序时，会发现划分出来的两个子序列一个里面没有元素，而另一个则只比原来少一个元素。为了避免这种情况，引入一个随机化量来破坏这种有序状态。

但是随机化快排因为要生成随机数，所以有一些性能损失，所以数据规模较小，数据分布均匀时普通快排还是比随机化快排要快些的，不过随着数据规模的上升，随机化快排的性能优势就展现出来了。

时间复杂度

平均情况下，快速排序的时间复杂度为$O(nlog_2n)$。

空间复杂度

快速排序是递归的，执行时需要有一个栈来存放相应的数据。最大递归调用次数与递归树的深度一致，所以最好情况下的空间复杂度为$O(nlog_2n)$，最坏情况下为O(n)。

0%