数据结构-快速排序的原理与实现

川长思鸟来 2024-03-16 18:43 83阅读 0赞

**目录**

一、前言

二、快速排序的原理

三、快速排序的实现

1. 递归实现

2. 非递归实现

四、C++实现

1. 递归实现

2. 非递归实现

五、优化

1. 随机化

2. 三数取中

六、总结

--------------------

## 一、前言 ##

在计算机科学中，排序是一种重要的算法。快速排序是一种常用的排序算法，它的时间复杂度为O(nlogn)，在实际应用中被广泛使用。本文将介绍快速排序的原理、实现以及C++代码，并对其进行优化。

## 二、快速排序的原理 ##

快速排序是一种基于分治思想的排序算法。它的基本思想是选取一个基准元素，将数组分成两个部分，一部分比基准元素小，一部分比基准元素大。然后对这两部分分别进行递归排序，最终得到有序数组。

快速排序的过程可以用以下图示表示：

!\[快速排序示意图\](https://i.imgur.com/7QKJ5yP.png)

## 三、快速排序的实现 ##

### 1. 递归实现 ###

快速排序的递归实现比较简单，代码如下：

void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int i = left, j = right, pivot = nums[left];
        while (i < j) {
            while (i < j && nums[j] >= pivot) j--;
            nums[i] = nums[j];
            while (i < j && nums[i] <= pivot) i++;
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

### 2. 非递归实现 ###

快速排序的非递归实现需要使用栈来模拟递归过程，代码如下：

void quickSort(vector<int>& nums, int left, int right) {
        stack<int> stk;
        stk.push(left);
        stk.push(right);
        while (!stk.empty()) {
            int r = stk.top(); stk.pop();
            int l = stk.top(); stk.pop();
            if (l >= r) continue;
            int i = l, j = r, pivot = nums[l];
            while (i < j) {
                while (i < j && nums[j] >= pivot) j--;
                nums[i] = nums[j];
                while (i < j && nums[i] <= pivot) i++;
                nums[j] = nums[i];
            }
            nums[i] = pivot;
            stk.push(l);
            stk.push(i - 1);
            stk.push(i + 1);
            stk.push(r);
        }
    }

## 四、C++实现 ##

### 1. 递归实现 ###

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int i = left, j = right, pivot = nums[left];
        while (i < j) {
            while (i < j && nums[j] >= pivot) j--;
            nums[i] = nums[j];
            while (i < j && nums[i] <= pivot) i++;
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }
    
    int main() {
        vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        quickSort(nums, 0, nums.size() - 1);
        for (int num : nums) {
            cout << num << " ";
        }
        cout << endl;
        return 0;
    }

### 2. 非递归实现 ###

#include <iostream>
    #include <vector>
    #include <stack>
    
    using namespace std;
    
    void quickSort(vector<int>& nums, int left, int right) {
        stack<int> stk;
        stk.push(left);
        stk.push(right);
        while (!stk.empty()) {
            int r = stk.top(); stk.pop();
            int l = stk.top(); stk.pop();
            if (l >= r) continue;
            int i = l, j = r, pivot = nums[l];
            while (i < j) {
                while (i < j && nums[j] >= pivot) j--;
                nums[i] = nums[j];
                while (i < j && nums[i] <= pivot) i++;
                nums[j] = nums[i];
            }
            nums[i] = pivot;
            stk.push(l);
            stk.push(i - 1);
            stk.push(i + 1);
            stk.push(r);
        }
    }
    
    int main() {
        vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        quickSort(nums, 0, nums.size() - 1);
        for (int num : nums) {
            cout << num << " ";
        }
        cout << endl;
        return 0;
    }

## 五、优化 ##

### 1. 随机化 ###

快速排序的时间复杂度与基准元素的选择有关。如果每次选择的基准元素都是数组的最大或最小值，那么快速排序的时间复杂度将退化为O(n^2)。为了避免这种情况，可以随机选择基准元素。

void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int i = left, j = right, pivot = nums[rand() % (right - left + 1) + left];
        while (i < j) {
            while (i < j && nums[j] >= pivot) j--;
            nums[i] = nums[j];
            while (i < j && nums[i] <= pivot) i++;
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

### 2. 三数取中 ###

在实际应用中，为了避免最坏情况的出现，可以使用三数取中的方法选择基准元素。即选择左端、右端和中间位置的三个元素中的中位数作为基准元素。

void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int i = left, j = right, mid = (left + right) / 2;
        int pivot = nums[mid];
        if (nums[left] < nums[right]) {
            if (nums[mid] < nums[left]) pivot = nums[left];
            else if (nums[mid] > nums[right]) pivot = nums[right];
        } else {
            if (nums[mid] > nums[left]) pivot = nums[left];
            else if (nums[mid] < nums[right]) pivot = nums[right];
        }
        while (i < j) {
            while (i < j && nums[j] >= pivot) j--;
            nums[i] = nums[j];
            while (i < j && nums[i] <= pivot) i++;
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

## 六、总结 ##

快速排序是一种高效的排序算法，它的时间复杂度为O(nlogn)。本文介绍了快速排序的原理、实现以及C++代码，并对其进行了优化。在实际应用中，可以根据具体情况选择不同的优化方法，以达到更好的排序效果。