C++：快速排序

摘要

这篇文章将会讲解如何用C++实现快速排序算法。尽管STL库中已提供了排序函数，但是理解如何通过简单的循环实现快速排序算法还是有必要的。

原理

对于快速排序算法更简洁的理解，可访问网站https://visualgo.net/。

C++代码

#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

void quick_sort(vector<int> *serial, int left_pos, int right_pos);

int main(int argc, char* argv[])
{
    vector<int> serial;
    int temp = 0;

    //Hint sentence to ask user input numbers.
    cout << "Please input numbers with space to seperate and finished with any non-number character:" << endl;

    //Use a vector as dynamic array to store numbers.
    while(cin >> temp) serial.push_back(temp);

    //Call quick_sort function.
    quick_sort(&serial, 0, serial.size()-1);

    //Print the result.
    cout << endl << "From min to max:" << endl;
    for(int i = 0; i < serial.size(); i++)
        cout << serial[i] << " ";
    cout << endl;

    return 0;
}

void quick_sort(vector<int> *serial, int left, int right)
{
    int temp = 0, base, base_pos;
    int left_pos, right_pos;

    //Flag and condition for recursive finished.
    if(left > right) return;

    //The first number on the left is the base number by default.
    base = (*serial)[left];
    base_pos = left;

    //Specifies the numbers at both ends of this sort.
    left_pos = left;
    right_pos = right;

    //When the left and right are not search to the same number.
    while(left_pos != right_pos)
    {
        //Search from right one by one until the searched number < base number.
        while(((*serial)[right_pos] >= base) && (left_pos < right_pos)) right_pos--;
        //Search from left one by one until the searched number > base number.
        while(((*serial)[left_pos] <= base) && (left_pos < right_pos)) left_pos++;

        //Swap the two searched number.
        if(left_pos != right_pos)
        {
            temp = (*serial)[left_pos];
            (*serial)[left_pos] = (*serial)[right_pos];
            (*serial)[right_pos] = temp;
        }
    }

    /* When it become the same number for searching from both sides, swap the current 
    number and the base number to confirm the position of base number. */
    (*serial)[base_pos] = (*serial)[left_pos];
    (*serial)[left_pos] = base;

    //Recursive to continue sorting for the left and right parts.
    quick_sort(serial, left, left_pos-1);
    quick_sort(serial, left_pos+1, right);
}