[每日算法]快速排序

题目描述

利用快速排序算法将读入的 N 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入格式

第 1 行为一个正整数 N，第 2 行包含 N 个空格隔开的正整数 a_i，为你需要进行排序的数，数据保证了a_i不超过 10^9。

输出格式

将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例

样例#1	输出#1
5 4 2 4 5 1	1 2 4 4 5

说明/提示

对于20% 的数据，有 N≤ 10^3；

对于 100% 的数据，有 N≤10^5

题解

快速排序是效率很高的一种不稳定的排序算法，平均时间复杂度为O(n log n)。

快速排序采用了分治的思想来完成排序，一般来说快速排序分为3个过程来完成：

1.将数列划分为两部分，选择一个数作为基数，小于基数的部分放在基数左边，大于基数的部分放在基数的右边。

2.递归到两个子序列中分别进行快速排序；

3.当每个子序列都只有一个元素的时候不用合并，因为此时数列已经完全有序，递归结束。

为了提高算法的效率，可以设置两根指针，从两个头端同时向中间的基数靠近进行排序，左边的指针寻找比基准数大的数，右边的指针寻找比基准数小的数，然后交换两个指针指向的数后指针同时向中间移动一个位置，当左边的指针指向的位置在右边指针的右边后，说明这一轮划分已经结束了，把基数放到两个子序列中间。然后对两个子序列进行相同的操作，直到每个子序列都只有一个数位置，这样整个序列就排序完毕了。

经过大量的实验表明，当数比较少的时候，其实快速排序的效率会比较低，因此当一个序列的元素个数少于8个时，可以从快速排序变成选择排序和冒泡排序来提高排序效率。

源代码

#include <iostream>
using namespace std;

void quickSort(int* numbers, int begin, int end)
{
    //数组中间的数默认为基准数
    int midNumber = numbers[(begin + end) / 2];
    //左指针指向第一个数据，右指针指向最后一个数据
    int left = begin;
    int right = end;
    while (left <= right)
    {
        //在左边找比基准数大的数，在右边找比基准数小的数
        while (numbers[left] < midNumber) left++;
        while (numbers[right] > midNumber)  right--;
        if (left <= right)
        {//如果左边有大的数，右边有小的数，交换位置
            swap(numbers[left], numbers[right]);
            left++;
            right--;
        }
    }
    if (begin < right) quickSort(numbers, begin, right);
    if (end > left) quickSort(numbers, left, end);
}

int main()
{
    int n, i, number;
    cin >> n;    //获取正整数的个数n
    int* numbers = new int[n];
    //将正整数输入到数组中
    for (i = 0;i < n;i++)
    {
        cin >> number;
        numbers[i] = number;
    }

    //进行快速排序
    quickSort(numbers, 0, n-1);

    //将排好序后的数输出
    for (i = 0;i < n;i++)
    {
        cout << numbers[i]<<" ";
    }
}