社区首页 >专栏 >快速排序的思想、时间复杂度、实现以及优化方法

快速排序的思想、时间复杂度、实现以及优化方法

原创

代码小李

发布于 2024-12-30 07:31:40

3190

快速排序的思想

快速排序（Quicksort）是一种高效的排序算法，采用分治法（Divide and Conquer）的策略。其基本思想是：

选择一个基准值（Pivot）：从数组中选择一个元素作为基准值。
分区操作（Partition）：将数组分为两部分，一部分的所有元素都小于基准值，另一部分的所有元素都大于或等于基准值。
递归排序：对这两部分分别递归地进行快速排序。

时间复杂度

最佳情况：O(n log n)，当每次分区都能均匀分割数组时。
平均情况：O(n log n)，在大多数情况下，快速排序的性能接近最佳情况。
最坏情况：O(n^2)，当每次分区都选择最小或最大元素作为基准值时，例如数组已经有序或逆序。

实现

以下是一个简单的快速排序实现：

#include <stdio.h>

// 交换两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准值
    int i = (low - 1);  // 小于基准值的元素的索引

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // 递归排序左子数组
        quickSort(arr, pi + 1, high); // 递归排序右子数组
    }
}

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

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序后的数组: ");
    printArray(arr, n);

    return 0;
}

优化方法

选择更好的基准值：
随机选择基准值：通过随机选择基准值可以减少最坏情况的发生概率。
三数取中法：选择数组的第一个、中间和最后一个元素的中位数作为基准值。

尾递归优化：
- 在递归调用时，优先处理较小的子数组，这样可以减少递归深度，避免栈溢出。
小数组使用插入排序：
- 对于小数组，插入排序通常比快速排序更高效。可以在数组大小小于某个阈值时切换到插入排序。
非递归实现：
- 使用迭代和栈来实现快速排序，避免递归带来的栈溢出问题。

示例代码优化

以下是一个包含上述优化的快速排序实现：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 交换两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 三数取中法选择基准值
int medianOfThree(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[mid]) swap(&arr[low], &arr[mid]);
    if (arr[low] > arr[high]) swap(&arr[low], &arr[high]);
    if (arr[mid] > arr[high]) swap(&arr[mid], &arr[high]);
    return mid;
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivotIndex = medianOfThree(arr, low, high);
    int pivot = arr[pivotIndex];
    swap(&arr[pivotIndex], &arr[high]);  // 将基准值移到末尾
    int i = (low - 1);  // 小于基准值的元素的索引

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 插入排序
void insertionSort(int arr[], int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    while (low < high) {
        if (high - low < 10) {  // 小数组使用插入排序
            insertionSort(arr, low, high);
            break;
        } else {
            int pi = partition(arr, low, high);
            if (pi - low < high - pi) {
                quickSort(arr, low, pi - 1);  // 优先处理较小的子数组
                low = pi + 1;
            } else {
                quickSort(arr, pi + 1, high);
                high = pi - 1;
            }
        }
    }
}

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

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5, 3, 2, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    srand(time(NULL));  // 初始化随机数生成器

    printf("原始数组: ");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序后的数组: ");
    printArray(arr, n);

    return 0;
}