初级算法 – 快速排序 | 高性能架构探索

效率高于冒泡排序和选择排序。

初始数组：{ 27,1,11,200,31,4,58,78,23,47,9,10000};

第一轮QuickSort的排序见，

27,1,11,200,31,4,58,78,23,47,9,10000

9,1,11,200,31,4,58,78,23,47,27,10000

9,1,11,27,31,4,58,78,23,47,200,10000

9,1,11,23,31,4,58,78,27,47,200,10000

9,1,11,23,27,4,58,78,31,47,200,10000

9,1,11,23,4,27,58,78,31,47,200,10000

中间值是27，可以看出27左边的数值都比它小，右边都比它大。

然后再此分组，简称"分而治之"

详细代码：

#include <iostream>

void swap(int* a, int* b);
void QuickSort(int* num, int low, int high);

int main()
{
    int a[] = { 27,1,11,200,31,4,58,78,23,47,9,10000};
    int low = 0, high = sizeof(a)/sizeof(int);

    QuickSort(a, low, high-1);

    for (int i = 0; i < high; i++)
    {
        std::cout << a[i] << " ";
    }

    return 0;
}


void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void QuickSort(int* num, int low, int high)
{
    int i = low,j = high;
    int* b = num;
    int key = b[low];

    while (low >= high)
    {
        return;
    }

    while (low < high)
    {
        while (low < high && key <= b[high])
        {
            high--;
        }
        if (key > b[high])
        {
            swap(&b[low], &b[high]);
            low++;
        }
        while (low < high && key > b[low])
        {
            low++;
        }
        if (key < b[low])
        {
            swap(&b[low], &b[high]);
            high--;
        }    

        for (int k = 0; k < 12; k++)
        {
            std::cout << b[k] << " ";
        }
        std::cout << std::endl;
    }
    QuickSort(b, i, low - 1);
    QuickSort(b, low + 1, j);
}

原文链接: https://www.cnblogs.com/strive-sun/p/14435746.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/404686

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

初级算法 – 快速排序

相关推荐