互联网科技架构算法设计模式和编程理论C++

小朋友学数据结构(7):快速排序

2018-06-15  本文已影响95人  海天一树X

(一)基本思想

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

(二)例子

6-1.png

以{5, 9, 2, 7 ,8, 3, 6, 1, 4, 0}为例。
选择第0个元素5作为参照数,咱们第一步的目标是把比5小的数都调整到5的左边,比5大的数都调到5的右边。
(1)从左往右开始观察,发现9比5大,准备调整。再从右往左观察,发现0比5小,准备调整。对调9和0的位置。
(2)继续从左往右观察,2比5小,不用调。继续往右,7比5大,准备调整。继续从右往左观赛,4比5小,准备调整。对调7和4的位置。
(3)继续从左往右观察,8比5大,准备调整。继续从右往左观察,1比5小,准备调整。对调8和1的位置。
(4)继续从左往右观察,3比5小,不用调整。继续往右观察,碰到6,准备调整。继续从右往左观察,第一个碰到的就是6,这时从左往右或者从右往左碰到的都是6,所以6不用调,也不需要再继续观察下去了。
(5)最后一次调整一下3和5的位置。得到了第一步的目标,比5小的{3, 0, 2, 4, 1}都在5的左边,比5大的{6, 8, 7, 9}都在5的右边。
(6)对新数列{3, 0, 2, 4, 1}和{6, 8, 7, 9}分别用上面的方法继续调整,直到所有的数都排完序为止。

(三)C++代码实现

#include <iostream>
using namespace std;

void QuickSort(int a[], int low, int high)
{
    if(low >= high)
    {
        return;
    }
    
    int pivot = a[low];
    int i = low + 1;
    int j = high;
    
    while(i <= j)
    {
        if(a[i] <= pivot)
        {
            i++;
        }
        else if(a[j] > pivot)
        {
            j--;
        }
        else
        {
            // swap a[i], a[j]
            a[i] ^= a[j];
            a[j] ^= a[j];
            a[i] ^= a[j];
            i++;
            j--;
        }
    }
    
    // swap a[low] , a[j]
    a[low] = a[j];
    a[j] = pivot;
    j--;
    
    QuickSort(a, low, j);
    QuickSort(a, i, high);
}

void PrintArrary(int data[], int size)
{
    for (int i = 0; i < size; ++i)
    {
        cout << data[i] << " ";
    }
    
    cout << endl;
}

int main(int argc, const char** argv)
{
    int array[]= {5, 9, 2, 7, 8, 3, 6, 1, 4, 0};
    int size = sizeof(array)/sizeof(int);
    QuickSort(array, 0, size - 1);
    PrintArrary(array, size);
    
    return 0;
}

运行结果:

0 1 2 3 4 5 6 7 8 9

TopCoder & Codeforces & AtCoder交流QQ群:648202993
更多内容请关注微信公众号


wechat_public_header.jpg
上一篇下一篇

猜你喜欢

热点阅读