常用算法-快速排序

题目描述

用快速排序算法给输入的数据排序。

输入描述

两行，第一行输入数据的长度n，第二行输入数据data[0]，data[1]，…，data[n-1]（0 < data[i]）。

输出描述

排序后的序列

解法分析

快速排序是经典算法。有好多种差不多的类型，我这里选用的是我们数据结构书上（哈工大的《数据结构》）的那种。

主要分为哪几个步骤呢？

• step1: 判断数据段是不是需要进行快速排序。当找不到两个不相同的时候就不需要在进行了。
• step2: 选择参考数pivot（重点）。比参考大或等于的放右边，其他放左边。注意参考数一定能够把数据分割成两部分。书上保证一定能让数据分割的办法是选取数据段中第一对儿不同的数据中较大的数。那么较小的那个数和较大的那个数就一定不会在同一个组了。
• step3: 递归被分割的两部分数据（难点）。
  • 首先定义两个数组的索引j，l分别为开始的位置和结束的位置。
  • 当j < l时迭代下述三步直到条件(j < l)不成立,此时j-1即为分割点。
  • j < l的情况下，如果data[l] < pivot则将 j += 1
  • j < l的情况下，如果data[l] >= pivot 则将 l -= 1
  • 交换data[j]和data[l]中的数据。
• 每一部分（begin~j-1, j~end）都进入 step1, 直至不需要在快速排序为止。

代码

#include <iostream>
#include <vector>
using namespace std;
void quick_sort(vector<int>* array);
void quick_sort_array(vector<int>* array, int begin, int end);
int find_pivot(vector<int>* array, int begin, int end);
int get_partition(vector<int>* array, int begin, int end, int pivot);
void Swap(int* a, int*b);

int main() {
    int n;
    cin >> n;
    vector<int> array;
    for(int i =0; i < n; i++)
    {
        int temp;
        cin >> temp;
        array.push_back(temp);
    }
    quick_sort(&array);
    for (int i : array) {
        cout << i << " ";
    }
    return 0;
}

void quick_sort(vector<int>* array)
{
    int n = (*array).size();
    quick_sort_array(array, 0, n-1);
}

void quick_sort_array(vector<int>* array, int begin, int end)
{
    int pivot = find_pivot(array, begin, end);
    if(pivot)
    {
        int k = get_partition(array, begin, end, pivot);
        quick_sort_array(array, begin, k-1);
        quick_sort_array(array, k, end);
    }
}

int find_pivot(vector<int>* array, int begin, int end)
{
    int first = (*array)[begin];
    for(int i = begin+1; i < end; i++)
    {
        if((*array)[i] != first)
        {
            return max(first, (*array)[i]);
        }
    }
    return 0;
}

int get_partition(vector<int>* array, int begin, int end, int pivot)
{
    while(begin < end)
    {
        while((*array)[begin] < pivot && begin < end)
            begin += 1;
        while((*array)[end] >= pivot && begin < end)
            end -= 1;
        if(begin < end)
            Swap(&(*array)[begin], &(*array)[end]);
    }
    return begin;
}

void Swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}