三天一算法:快速排序

浏览数：23 / 时间：2015年06月08日

i---> 6, 5, 7, 8, 3 , 2 , 9 , 10 <----j
首先以第一个为基准值 6

1： j从右边出发，在j移动到2的时候发现小于6，j停了下来，

然后i开始移动，当i移动到7的时候发现大于6，于是i也停了下来

然后i和j交换了他们所代表的值

6, 5, 7, 8, 3 , 2 , 9 , 10 --> 6, 5, 2, 8, 3 , 7 , 9 , 10

2：然后j继续向左移动，在移动到3的时候发现小于6，j停了下来，

i也继续移动，当移动到8的时候发现大于6，于是i又停了下来

i和j交换了他们所代表的值

6, 5, 2, 8, 3 , 7 , 9 , 10 --> 6, 5, 2, 3, 8 , 7 , 9 , 10

3: 继续，j继续向左移动，当移动到3的时候i == j，循环结束

这个时候呢，我们要把i代表的值和基准值进行交换

6, 5, 2, 3, 8 , 7 , 9 , 10 --> 3, 5, 2, 6, 8 , 7 , 9 , 10

在这个的整个过程中呢，6我们已经找好了它的位置，我们就不在管它了，于是我们把6前后分成了2组，[3,5,2] 和[8, 7, 9, 10]

我们再继续对[3, 5, 3]和[8, 7, 9, 10]重新上面的过程，最后我们就能得到最终结果：2，3，5，6，7，8，9，10

#include<iostream>
using namespace std;

int a[] = {6, 5, 7, 8, 3, 2, 9, 10 };

void QuickSort(int left, int right)
{
    if (left >= right) //如果left >= right就没有必要交换了，因为本身已经排序了
        return;
    
    int guard = a[left];
    int i = left;
    int j = right;

    while (i != j) {
        while (a[j] >= guard && i < j) //保证每次要先从右边开始遍历
            j--;
        while (a[i] <= guard && i < j)
            i++;
        
        if (i < j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    a[left] = a[i]; //结束后要把基准值和当前的那个值进行交换
    a[i] = guard;

    QuickSort(left, i - 1);
    QuickSort(i+1, right);
}

int main()
{
    QuickSort(0, sizeof(a)/sizeof(int) -1);
    for (int i = 0; i < sizeof(a)/sizeof(int) ;i++ )
        cout << a[i] << " " ;
    cout << endl;
}