快速排序算法

提示

1. 快速排序的核心机制：基于分治法，通过选取基准元素划分数组为子数组，确保基准左侧元素小于基准，右侧元素大于基准。
2. 递归划分子数组：对基准的左右子数组重复执行相同划分过程，直至每个子数组只含一个元素，完成排序。
3. 性能和应用：平均时间复杂度为O(n log n)，适用于大多数情况下的高效排序，空间复杂度为O(log n)。

快速排序是一种基于分治法的排序算法，其工作原理如下：

1. 首先，通过选择一个基准元素（从数组中选择的元素）来将数组划分为子数组。

   在划分数组时，基准元素应该被放置在这样的位置，即小于基准的元素在基准的左侧，大于基准的元素在基准的右侧。

2. 然后，对左右子数组使用相同的方法进行划分，这个过程一直持续下去，直到每个子数组包含一个元素。

3. 此时，元素已经排好序。最后，将这些元素合并成一个排序好的数组。

快速排序算法的工作原理

1. 选择基准元素

快速排序有不同的变体，其中基准元素可以从不同位置选择。在这里，我们将选择数组的最右侧元素作为基准元素。

2. 重新排列数组

现在，重新排列数组的元素，以便将小于基准的元素放在左侧，大于基准的元素放在右侧。

以下是重新排列数组的步骤：

1. 在基准元素处固定一个指针。将从第一个索引开始的元素与基准元素进行比较。

2. 如果元素大于基准元素，则为该元素设置第二个指针。

3. 现在，基准元素与其他元素进行比较。如果到达一个小于基准元素的元素，就将较小的元素与之前找到的较大元素交换位置。

4. 然后，重复此过程以设置下一个较大元素为第二个指针，并将其与另一个较小元素交换。

5. 这个过程一直持续到倒数第二个元素。

6. 最后，将基准元素与第二个指针处的元素交换。

3. 划分子数组

然后，分别为左侧和右侧的子部分选择基准元素，然后重复步骤2。

这些子数组将被划分，直到每个子数组只包含一个元素。此时，数组已经排好序。

快速排序算法

quickSort(array, leftmostIndex, rightmostIndex)
  if (leftmostIndex < rightmostIndex)
    pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
    quickSort(array, leftmostIndex, pivotIndex - 1)
    quickSort(array, pivotIndex, rightmostIndex)

partition(array, leftmostIndex, rightmostIndex)
  set rightmostIndex as pivotIndex
  storeIndex <- leftmostIndex - 1
  for i <- leftmostIndex + 1 to rightmostIndex
  if element[i] < pivotElement
    swap element[i] and element[storeIndex]
    storeIndex++
  swap pivotElement and element[storeIndex+1]
return storeIndex + 1

快速排序算法的可视化示例

您可以通过以下示例图形了解快速排序算法的工作原理。

Python、Java 和 C/C++ 中的快速排序代码

Python Java C C++

# Python 中的快速排序

# 寻找分区位置的函数
def partition(array, low, high):

  # 选择数组中的最右侧元素作为基准
  pivot = array[high]

  # 指向较大元素的指针
  i = low - 1

  # 遍历所有元素，将每个元素与基准进行比较
  for j in range(low, high):
    if array[j] <= pivot:
      # 如果找到小于基准的元素
      # 将其与指针 i 指向的较大元素交换位置
      i = i + 1

      # 交换 i 处的元素与 j 处的元素
      (array[i], array[j]) = (array[j], array[i])

  # 将基准元素与 i 处指针指向的较大元素交换位置
  (array[i + 1], array[high]) = (array[high], array[i + 1])

  # 返回划分的位置
  return i + 1

# 执行快速排序的函数
def quickSort(array, low, high):
  if low < high:

    # 寻找基准元素，使得左侧元素小于基准，右侧元素大于基准
    pi = partition(array, low, high)

    # 在基准的左侧递归调用
    quickSort(array, low, pi - 1)

    # 在基准的右侧递归调用
    quickSort(array, pi + 1, high)


data = [8, 7, 2, 1

, 0, 9, 6]
print("未排序的数组")
print(data)

size = len(data)

quickSort(data, 0, size - 1)

print('升序排列的排序后数组:')
print(data)

// Java中的快速排序

import java.util.Arrays;

class Quicksort {

  // 查找分区位置的方法
  static int partition(int array[], int low, int high) {

    // 选择最右侧的元素作为基准
    int pivot = array[high];

    // 用于较大元素的指针
    int i = (low - 1);

    // 遍历所有元素
    // 比较每个元素与基准
    for (int j = low; j < high; j++) {
      if (array[j] <= pivot) {

        // 如果找到小于基准的元素
        // 与指针 i 指向的较大元素交换位置
        i++;

        // 交换 i 处的元素与 j 处的元素
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }

    }

    // 交换基准元素与 i 处指针指向的较大元素
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    // 返回划分位置
    return (i + 1);
  }

  static void quickSort(int array[], int low, int high) {
    if (low < high) {

      // 寻找基准元素，使得左侧元素小于基准，右侧元素大于基准
      int pi = partition(array, low, high);

      // 对基准左侧进行递归调用
      quickSort(array, low, pi - 1);

      // 对基准右侧进行递归调用
      quickSort(array, pi + 1, high);
    }
  }
}

// 主类
class Main {
  public static void main(String args[]) {

    int[] data = { 8, 7, 2, 1, 0, 9, 6 };
    System.out.println("未排序的数组");
    System.out.println(Arrays.toString(data));

    int size = data.length;

    // 调用 quicksort() 对数组 data 进行排序
    Quicksort.quickSort(data, 0, size - 1);

    System.out.println("升序排列的排序后数组: ");
    System.out.println(Arrays.toString(data));
  }
}

// C中的快速排序

#include <stdio.h>

// 交换元素的函数
void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

// 查找分区位置的函数
int partition(int array[], int low, int high) {

  // 选择最右侧的元素作为基准
  int pivot = array[high];

  // 用于较大元素的指针
  int i = (low - 1);

  // 遍历数组的每个元素
  // 将它们与基准进行比较
  for (int j = low; j < high; j++) {
    if (array[j] <= pivot) {

      // 如果找到小于基准的元素
      // 将其与指针 i 指向的较大元素交换位置
      i++;

      // 交换 i 处的元素与 j 处的元素
      swap(&array[i], &array[j]);
    }
  }

  // 将基准元素与 i 处指针指向的较大元素交换位置
  swap(&array[i + 1], &array[high]);

  // 返回分区点
  return (i + 1);
}

void quickSort(int array[], int low, int high) {
  if (low < high) {

    // 寻找基准元素，使得左侧元素小于基准，右侧元素大于基准
    int pi = partition(array, low, high);

    // 对基准左侧进行递归调用
    quickSort(array, low, pi - 1);

    // 对基准右侧进行递归调用
    quickSort(array, pi + 1, high);
  }
}

// 打印数组元素的函数
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

// 主函数
int main() {
  int data[] = { 8, 7, 2, 1, 0, 9, 6 };

  int n = sizeof(data) / sizeof(data[0]);

  printf("未排序的数组\n");
  printArray(data, n);

  // 对 data 数组执行快速排序
  quickSort(data, 0, n - 1);

  printf("升序排列的数组: \n");
  printArray(data, n);
}

快速排序算法（C++）

快速排序是一种高效的排序算法，采用分而治之的策略，是在平均情况下性能最好的排序算法之一。

快速排序代码示例（C++）

#include <iostream>
using namespace std;

// 交换元素函数
void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

// 打印数组函数
void printArray(int array[], int size) {
  int i;
  for (i = 0; i < size; i++)
    cout << array[i] << " ";
  cout << endl;
}

// 重排数组并找到分区点
int partition(int array[], int low, int high) {

  // select the rightmost element as pivot
  int pivot = array[high];

  // pointer for greater element
  int i = (low - 1);

  // traverse each element of the array
  // compare them with the pivot
  for (int j = low; j < high; j++) {
    if (array[j] <= pivot) {

      // if element smaller than pivot is found
      // swap it with the greater element pointed by i
      i++;

      // swap element at i with element at j
      swap(&array[i], &array[j]);
    }
  }

  // swap pivot with the greater element at i
  swap(&array[i + 1], &array[high]);

  // return the partition point
  return (i + 1);
}

void quickSort(int array[], int low, int high) {
  if (low < high) {

    // find the pivot element such that
    // elements smaller than pivot are on left of pivot
    // elements greater than pivot are on righ of pivot
    int pi = partition(array, low, high);

    // recursive call on the left of pivot
    quickSort(array, low, pi - 1);

    // recursive call on the right of pivot
    quickSort(array, pi + 1, high);
  }
}

// Driver code
int main() {
  int data[] = {8, 7, 6, 1, 0, 9, 2};
  int n = sizeof(data) / sizeof(data[0]);

  cout << "未排序数组: \n";
  printArray(data, n);

  quickSort(data, 0, n - 1);

  cout << "升序排列的数组: \n";
  printArray(data, n);
}

快速排序的复杂度

时间复杂度
最佳情况	O(n*log n)
最坏情况	O(n^2)
平均情况	O(n*log n)
空间复杂度	O(log n)
稳定性	否

1. 时间复杂度

• 最坏情况复杂度（Big-O）：O(n^2) 当所选的枢轴元素是数组中的最大或最小元素时，会发生这种情况。

  这种情况下，枢轴元素位于已排序数组的一个极端。一个子数组总是空的，另一个子数组包含 n - 1 个元素。因此，快速排序只在这个子数组上调用。

  但是，对于分散的枢轴，快速排序算法的性能更好。

• 最佳情况复杂度（Big-omega）：O(n*log n) 当枢轴元素总是位于中间或接近中间时发生。

• 平均情况复杂度（Big-theta）：O(n*log n) 当上述条件不发生时发生。

2. 空间复杂度

快速排序的空间复杂度为 O(log n)。

快速排序的应用

在以下情况下使用快速排序算法：

• 编程语言适用于递归
• 时间复杂度重要
• 空间复杂度重要

相似的排序算法

• 插入排序
• 归并排序
• 选择排序
• 桶排序