吃透快排

快排是种十分巧妙而优秀的算法，时间复杂度为O(nlogn)，花费了一点时间终于弄懂了其原理，写文以记录

步骤：

1.选择一个flag（通常用数组第一个元素）

2.将数组重新排列，使得左边均小于flag，右边均大于flag

3.对flag左右两侧递归1、2步骤

其中第2步为难点，如何实现？我们设一个j从右侧向左，一个i从左侧向右，停止条件为i和j相遇，当遇到小于flag的a[j]，将a[j]与a[i]换位，当遇到大于flag的a[i]，将a[i]与a[j]换位

#include<iostream>

int a[11] = { 5, 4, 8, 7, 3, 10, 6, -5, 9, -20, 7};

void swap(int* p, int* q)
{
    int t = *p;
    *p = *q;
    *q = t;
}

int quicksort(int left, int right)
{
    if (left >= right)
    {
        return 0;
    }

    int i = left;
    int j = right;
    int flag = a[i];

    while (i < j)
    {
        while (i<j && a[j]>=flag)
        {
            j--;
        }
        swap(&a[i], &a[j]);
        while (i < j && a[i] <= flag)
        {
            i++;
        }
        swap(&a[i], &a[j]);
    }

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

int main()
{
    printf("before: ");
    for (int i = 0; i < sizeof(a)/sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }

    quicksort(0, sizeof(a) / sizeof(int) - 1);


    printf("\nafter: ");
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }
}

运行结果

上面的方法较易理解，使用swap进行交换，但实际程序这样写会占用更小的资源：

#include<iostream>

int a[11] = { 5, 4, 8, 7, 3, 10, 6, -5, 9, -20, 7};

int quicksort(int left, int right)
{
    if (left >= right)
    {
        return 0;
    }

    int i = left;
    int j = right;
    int flag = a[i];

    while (i < j)
    {
        while (i < j && a[j] >= flag)
        {
            j--;
        }
        a[i] = a[j];

        while (i < j && a[i] <= flag)
        {
            i++;
        }
        a[j] = a[i];
    }
    a[i] = flag;

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

int main()
{
    printf("before: ");
    for (int i = 0; i < sizeof(a)/sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }

    quicksort(0, sizeof(a) / sizeof(int) - 1);

    printf("\nafter: ");
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }
}