经典算法之快速排序（QuickSort）

活动地址：CSDN21天学习挑战赛

1. 概念

快速排序，从名字得知，算法效率是快而高。快速排序是使用分治策略将一个序列分为两个子序列，再针对子序列又继续分若干个子序列。快速排序应该算是在冒泡排序基础上的递归分治法。针对该算法思想，举个例子演示一下，大家就一目了然了。

输入

6 1 2 7 9 3 4 5 10 8
1

算法执行详解

首先在这个序列中，随机找一个元素作为基准数，一般来说，选择最左边的元素作为基准数，即选择元素6作为基准数，然后将所有比基准数大的数放在6的右侧，比基准数小的数放在6的左侧。那该如何执行呢？在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。
最左边为i，最右边为j，首先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。

首先j开始往左移动，找到比6小的元素，此时找到了元素5，然后i往右移动，找到了元素7，此时交换5和7，就得到 6 1 2 5 9 3 4 7 10 8

然后，j继续往左移动找比6小的元素，找到了4，i继续往右移动找比6大的元素，找到了9，然后交换4和9的位置

然后，j继续往左移动找比6小的元素，找到了3，i继续往右移动，也走到了3面前，i与j相遇，至此移动结束，交换3和6的位置，

由图可以得到，以6为基准，左侧都是比6小的元素，右侧都是比6大的元素，第一轮交换结束，再针对子序列进行二轮交换。以此类推。

2. 伪代码

3. 代码实现

quickSort(array, left, right)
  if (left < right)
    pivotIndex <- partition(array,left, right)
    quickSort(array, left, pivotIndex - 1)
    quickSort(array, pivotIndex, right)

partition(array, left, right)
  set right as pivotIndex
  storeIndex <- left - 1
  for i <- left + 1 to right
  if element[i] < pivotElement
    swap element[i] and element[storeIndex]
    storeIndex++
  swap pivotElement and element[storeIndex+1]
return storeIndex + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.1 Java版

package DirectlnsertTest;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] nums = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
        quickSort(nums, 0, nums.length - 1);
        System.out.println("快速排序后:" + Arrays.toString(nums));
    }

    public static void quickSort(int[] nums, int start, int end) {
        if (start > end)
            return;
        int i, j, base;
        i = start;
        j = end;
        base = nums[start];
        while (i < j) {
            while (i < j && nums[j] >= base)
                j--;
            while (i < j && nums[i] <= base)
                i++;
            if (i < j) {
                swap(nums, i, j);
            }
        }
        swap(nums, start, i);
        quickSort(nums, start, j - 1);
        quickSort(nums, j + 1, end);
    }

    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

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

3.2 Python核心代码

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. 算法效率分析

4.1 时间复杂度

• 最好情况
  当每次待排元素恰好都处在中间位置，将原有序列分为等长的子序列，每次划分子序列都是这种情况，那么总共划分的次数是以2为底n的对数，所以时间复杂度为n倍的以2为底n的对数
• 最坏情况
  如果序列是一个有序序列，每次都要比较一遍，所以时间复杂度为O(n^2)
• 平均情况
  综上所述，平均时间复杂度为以2为底n的对数。

4.2 空间复杂度

因为是递归操作，所以在执行过程时需要在栈中保存相关信息，所以，平均情况是以2为底n的对数。