DS排序--快速排序

Description

给出一个数据序列，使用快速排序算法进行从小到大的排序

排序方式：以区间第一个数字为枢轴记录

输出方式：每一步区间排序，都输出整个数组

–程序要求–

• 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
• 程序中若include多过一个头文件，不看代码，作0分处理
• 不允许使用第三方对象或函数实现本题的要求

Input

第一行输入t，表示有t个测试示例

第二行输入n，表示第一个示例有n个数据

第三行输入n个数据，都是正整数，数据之间用空格隔开

以此类推

Output

每组测试数据，输出每趟快排的结果，即每次排好一个数字结果（长度为1的子序列，不用排，不用输出）。不同测试数据间用空行分隔。

Sample

#0

Input

Copy

2
6
111 22 6 444 333 55
8
77 555 33 1 444 77 666 2222

Output

Copy

55 22 6 111 333 444
6 22 55 111 333 444
6 22 55 111 333 444
6 22 55 111 333 444

1 33 77 555 444 77 666 2222
1 33 77 555 444 77 666 2222
1 33 77 77 444 555 666 2222
1 33 77 77 444 555 666 2222
1 33 77 77 444 555 666 2222

本题用的快速排序，而且还是折半快速排序

快速排序原理:

基本思想：

? ? ? ? 采用“分治”的思想，对于一组数据，选择一个基准元素（base），通常选择第一个或最后一个元素，通过第一轮扫描，比base小的元素都在base左边，比base大的元素都在base右边，再有同样的方法递归排序这两部分，直到序列中所有数据均有序为止。

大家一定要记得快速排序不稳定哈。
什么叫不稳定？
就是比如1 2 2 3，这里的两个2其实有先后之分的，如果我们的算法会导致第一个2跟第二个2交换位置，这个就是不稳定。
快速排序为什么不稳定？
从之后我给你们跑的样例就可以看出来，快速排序他交换位置的时候跨过了很多别的数，所以相等的数原本在后面的可能跑到前面去了

快速排序的实现：

如果是sztu的可以学一下郭老师教的这个版本，我会一步一步按照样例给你们跑出来结果演示一遍

样例：111 22 6 444 333 55

这个是要排序的数组

用两个指针 left 和 right 还有一个temp存临时值

开始让数组dp[0]的值为temp值，然后相比较temp值在左边，所以我们从右边right开始往左走找小于temp的值

找到小于temp的55然后交换

然后temp值在右边，然后left从左向右找大于temp的值

tips：temp在左，right从右往左找小于temp的值。temp在右，left从左往右找大于temp的值

找到444大于temp值然后交换位置

然后temp在做，right找比temp小的，没找到，然后left=right，结束循环

这里还没完成！！！

这其实之后进行递归，将此时left为准左右两边分块分别重复上面的步骤，然后就可以排好序了。右边大家都看出来已经排好了，我就不画图了，但是实际上代码还是把右边的跑了一遍的

分块成这样：

然后重复步骤temp为最左边那个，然后right找＜temp的值，然后找到6交换位置

这里其实都已经排序好了，但是递归会递归到每组只有一个元素的时候。剩下的我就不画了

快速排序实现代码细节：

tips：上面的temp参数代码里用的是center，还有上面移动的 left 是 ll ，right 是 rr 。这样写的原因是底下递归的时候，需要用到传入的left和right，所以最好不要改变他们

本题思路：

enmmmm，还有什么好说的，已经说了是快速排序算法了！

tips：记住这张图（图来源郭老师）

空间复杂度为什么是，因为你每次分割递归的时候平均相当于折半开了空间，然后每次都给你折半了。

本题实现代码：

#include <iostream>
using namespace std;
const int maxn = 1e5 + 10;
int n;
int dp[maxn];
void output()
{
    for (int i = 0; i < n; i++)
    {
        cout << dp[i] << " ";
    }
    cout << endl;
}
void quicksort(int left, int right)//这里是左闭右开的写法
{
    if (left >= right - 1)//如果left >= right - 1递归就结束返回
        return;
    int center = dp[left];//center是刚才上面的temp
    int ll = left, rr = right - 1;//ll和rr是刚才上面跑的left和right指针
    while (ll < rr)               //为什么要取一个新的原因是递归需要输入边界，所以最开始用的left和right最好不要改
    {
        while (ll < rr && center <= dp[rr])//center就是temp在左边，右指针rr往左找比center小的数
            rr--;
        swap(dp[ll], dp[rr]);//找到了然后交换
        while (ll < rr && dp[ll] <= center)//这个时候center在右边，所以left指针向右找比center大的数
            ll++;
        swap(dp[ll], dp[rr]);//然后交换
    }
    output();//本题要输出每次排序一次的结果
    quicksort(left, ll);//然后以ll为界限，左右两边分块递归
    quicksort(ll + 1, right);
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> dp[i];//输入要排序的数组
        }
        quicksort(0, n);//调用快速排序
        cout << endl;
    }
    return 0;
}

---

? ? ? ?我也不知道自己写清楚没，这个方法跟网上一些的区别是我们center取的是第一个数，但是网上的好像折半取，就是取中间那里的，但是实质上没有区别，因为center值在那次函数实现中没有改变过?

期末月了，好多事情啊，感觉更不下去了。

祝我别挂科吧。概率论真的慌！！！
概率论竟然还有大作业，好想哭