快速排序图解(分治)--算法学习_快速排序分治法图解过程

思路

数组排序任务可以如下完成：
1）设k=a[0], 将k挪到适当位置，使得比k小的元素都
在k左边,比k大的元素都在k右边，和k相等的，不关心
在k左右出现均可 （O（n)时间完成）
2) 把k左边的部分快速排序
3) 把k右边的部分快速排序

图解
一组数据：

首先 左指针为i，右边的指针为j，中间值为a[0]=7;
然后，左边的让着右边的，右边j向左移动，如下图

发现2比7小停止移动了，所以2和7就进行调换

这时候右边的调换一次了，总不能一直让右边移动，太累了，这时候左边开始移动了，但是他发现1比7小就没停，继续移动

发现3比7还是小，就继续移动，一直移动到8停下来了

8比7大，所以8和7进行了调换

这时候，右边开始移动，发现11，12都比7大所以，没有调换，最后ij都移动到了7的位置，他们俩相遇了，就停止了

对左右两边进行递归，就会得到有序的数组了

代码：

#include <iostream>
using namespace std;
void swap(int& a, int& b) //交换变量a,b值 
{
int tmp = a;
a = b;
b = tmp; 
}
void QuickSort(int a[], int s, int e)
{
    if (s >= e)//相当于左指针跑到右指针右边了，必然就停止了
        return;
    int k = a[s];//以a[s],即左边第一个数为中间值
    int i = s, j = e;
    while (i != j) {
        while (j > i&& a[j] > k)//找不到比中间值小的就一直走
            --j;
        swap(a[i], a[j]);//找到了，进行交换
        while (i < j && a[i] <= k)//找不到比中间值大的就一直走
            ++i;
        swap(a[i], a[j]);//找到了，交换
    }//处理完后，a[i]=k;
    QuickSort(a, s, i - 1);//对左右两边递归，得到
    QuickSort(a, i + 1, e);
}
int a[] = { 93,27,30,2,8,12,2,8,30,89 };
int main()
{
    int size = sizeof(a) / sizeof(int);
    QuickSort(a, 0, size - 1);
    for (int i = 0; i < size; ++i)
        cout << a[i] << ",";
    cout << endl;
    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
34
35
36