快速排序算法最简单介绍 以及C++代码实现_快速排序c++代码

其他常见的排序算法

• 起泡排序
• 插入排序
• 插入排序
• 归并排序
• 桶排序
• 计数排序
• 基数排序
• 堆排序
• 锦标赛排序
• 希尔排序

快速排序算法原理

• 基本思想：将待排序序列分为两个子序列，其中一个子序列中的所有值都小于等于基准值，另一个子序列中的所有值都大于等于基准值。然后将这两个子序列分别递归地进行快速排序，再拼接到一起。

需要强调的是，对于和基准值相等的序列元素，其在基准值左边或右边的子序列都没有关系。

• 基准值：随机从待排序序列中去除一个值作为基准值，出于简单考虑，一般取序列中的第一个元素或最后一个元素作为基准值。需要注意的是，如果使用下面的代码模板，那么在递归调用阶段以i作为分界点，则不能以序列最左边的元素作为基准值；如果以j作为分界点，则不能以序列最右边的元素作为初始值。
• 排序过程：
  • 第一步：分别在待排序序列的左右边界外各设置一个左右指针，左指针在之后会向右移动，右指针之后会向左移动。
  • 第二步：首先移动左指针。左指针每次向右滑动一个元素，如果该元素的值小于基准值，则左指针继续向右滑动，直到找到第一个大于等于基准值的元素。因为序列中本身就存在值为基准值的元素，因此左指针最多滑动到该元素的位置就一定会停下，而不会发生越界。
  • 第三步：接着移动右指针，右指针每次向左滑动一个元素，如果该元素的值大于基准值，则右指针继续向左滑动，直到找到第一个小于等于基准值的元素。与左指针的滑动过程类似，右指针也不会发生越界。
  • 第四步：交换左右指针所指向的元素的值。交换完成后，左指针及其左侧元素构成的序列中的所有元素均小于等于基准值，右指针及其右侧元素构成的序列中的所有元素均大于等于基准值。然后继续按照上述的步骤移动左右指针，直到右指针移动到左指针的左边。
  • 第五步：以左指针指向的元素作为右子序列的第一个元素，对左右两段子序列分别进行递归的快速排序即可（之所以以左指针指向元素作为右子序列的第一个元素，是因为左指针已经走过的地方的元素的值都是小于基准值的）。递归基是只含有一个元素的序列。

快速排序算法简单案例

下面通过一个简单的案例介绍快速排序算法的过程。案例如下：

2 3 4 1

1. 设置左右指针和选定基准值。初始情况下，左指针指向序列的左边界，即2的左边；右指针指向序列的右边界，即1的右边。本例中以序列的第一个元素2作为基准值。
2. 移动左指针：左指针向右移动一次，发现左边第一个元素2不满足小于基准值2，因此停下。
3. 移动右指针：右指针向左移动一次，发现右边第一个元素1不满足大于基准值2，因此停下。
4. 交换左右指针的值：由于此时右指针仍然在左指针的右边，因此交换两个指针所指向的值，此时，序列变为：

1 3 4 2

5. 移动左指针：左指针向右移动一次指向下一个元素3，发现该元素也不满足大于基准值2，因此停下。
6. 移动右指针：右指针向左移动一次指向下一个元素4，发现该元素满足大于基准值2，因此继续向左移动，发现元素3也满足大于基准值2，因此继续向左移动指向元素1，由于1不满足大于基准值2，因此右指针停下。
7. 判定：由于右指针指向序列的第一个元素，而左指针指向序列的第二个元素，因此左指针在右指针的右边，不发生元素交换。
8. 递归：以左指针指向的元素作为右子序列的第一个元素，将序列划分为左右两个子序列，即(1)和(3 4 2)。分别递归地对左右子序列进行快速排序。
9. 左子序列排序：由于左子序列只包含一个元素1，属于递归基，因此无需排序。
10. 右子序列排序：采用和上述类似的方法即可对右子序列完成排序，排序结果是(2 3 4)。
11. 左右子序列拼接：将左子序列和右子序列进行拼接，即可得到最终的排序结果（1 2 3 4）。

实现代码（C++）和注意事项

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int a[N];
int n;

void quick_sort(int* a, const int& left, const int& right)
{
    if (left >= right)return;
    int i(left - 1), j(right + 1), ref(a[(left+right)>>1]);
    while (i < j)
    {
        do i++; while (a[i] < ref);
        do j--; while (a[j] > ref);
        if (i < j)swap(a[i], a[j]);
    }
    //下面的递归调用部分，如果采用下面的写法，则基准值不能取原始序列的最左侧元素
    //因为i-1可能取值-1，导致数组越界
    quick_sort(a, left, i-1);
    quick_sort(a, i, right);
}

int main(void)
{
    cin >> n;
    for (int i(0); i < n; ++i) cin>> a[i];
    quick_sort(a, 0, n - 1);
    for (int i(0); i < n; ++i) printf("%d ", a[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

注意事项：

• 使用静态数组：对于编程竞赛，使用静态数组有更高的执行效率，并且可以避免内存泄漏等问题，因此上面的代码中的数组采用静态形式。在开辟静态数组时，往往会将其最大空间进行一定程度的扩展防止数组越界。
• swap函数的使用：swap函数是C++的<algorithm>头文件中提供的函数，用于交换两个变量的值，使用时需要导入头文件。
• 输入的效率：编程竞赛中，当输入数据量较大时，往往使用效率更高的scanf函数进行输入，此处由于输入规模不大，故才使用cin进行输入。
• sort函数：sort是C++的STL中自带的排序函数，可以按照从小到大的顺序对一个向量等容器中的元素进行排序。使用语法为：sort(容器变量名.begin(),容器变量名.end())。