排序算法 – 52funny Blog

清华大学严蔚敏《数据结构》
清华大学李春葆《数据结构教程》

快速排序

数据结构课已经临近尾声，今天老师还给我们讲了一点排序，但是我觉得排序里面在算法里面最好用的还是快速排序，C++ algorithm头文件里的sort(_RandomAccessIterator __first, _RandomAccessIterator __last,_Compare __comp)函数就是快速排序算法。

快速排序的基本思想就是在待排序的 n 个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入适当位置后，数据序列被此元素分成两部分。所有关键字比该元素关键字小的元素放置在前一部分，所有比它大的元素放置在后一部分，并把该元素排在这两部分的中间，这个过程称为一趟快速排序，及一趟划分。

之后对产生的两个部分分别重复上述过程，直至每部分内只有一个元素或为空为止。简而言之，每趟使表的第一个元素放入适当位置，将表一分为二，对子表按照递归方式继续这种划分，直至划分的子表的长为 1 或 0。

我们来举个栗子

首先给个序列

6 8 7 9 0 1 3 2 4 5 基准为 6

5 4 2 3 0 1 6 9 7 8 一次划分

5 4 2 3 0 1 进行划分

1 4 2 3 0 5 6 9 7 8 二次划分

1 4 2 3 0 进行划分

0 1 2 3 4 5 6 9 7 8 三次划分

2 3 4 进行划分

0 1 2 3 4 5 6 9 7 8 四次划分

3 4 进行划分

0 1 2 3 4 5 6 9 7 8 五次划分

9 8 7 进行划分

0 1 2 3 4 5 6 8 7 9 六次划分

8 7 划分

0 1 2 3 4 5 6 7 8 9 七次划分

所以快速排序还是很是实用的

C++代码

#include <iostream>
#include <algorithm>
using namespace std;
int Partition(int a[], int l, int r)
{
    int temp = a[l];
    int i = l, j = r;
    while (i < j)
    {
        while (i < j && a[j] >= temp)
            j--;
        a[i] = a[j];
        while (i < j && a[i] <= temp)
            i++;
        a[j] = a[i];
    }
    a[i] = temp;
    return i;
}
void QuickSort(int a[], int l, int r)
{
    if (l < r)
    {
        int i = Partition(a, l, r);
        QuickSort(a, l, i - 1); //左区间划分
        QuickSort(a, i + 1, r); //右区间划分
    }
}
int main()
{
    int n;
    cin >> n;
    int a[100];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    QuickSort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
}

我们也可以把递归函数 QuickSort 函数写入划分函数 Partition

将递归写入划分

C++代码

#include <iostream>
#include <algorithm>
using namespace std;
int Partition(int a[], int l, int r)
{
    int temp = a[l];
    int i = l, j = r;
    if (l < r)
    {
        while (i < j)
        {
            while (i < j && a[j] >= temp)
                j--;
            a[i] = a[j];
            while (i < j && a[i] <= temp)
                i++;
            a[j] = a[i];
        }
        a[i] = temp;

        Partition(a, l, i - 1);		//左区间
        Partition(a, i + 1, r);		//右区间
    }
}

int main()
{
    int n;
    cin >> n;
    int a[100];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    Partition(a, 0, n - 1);
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
}