基础算法：快速排序的实现代码

本文的copyleft归[e-mail]所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。
作者：[e-mail]
博客：linuxfocus.blog.chinaunix.net 

今天温习快速排序——很精典的排序算法，发现一下子写对也听不容易的。快速排序的优缺点，还是问google。在测试的过程中，由于编写的gtest用例中，有一个地方把test case写错了，浪费了一些时间。

上代码。。。。

#include "my_basetype.h"

/**************************************************************************************/
static int partition(B_U32 *array, int l, int r);
static inline void swap_array_value(B_U32 *array, int a, int b);
static void real_quick_sort(B_U32 *array, int l, int r);
/**************************************************************************************/
void quick_sort(B_U32 *array, int size)
{
    real_quick_sort(array, 0, size-1);
}

static void real_quick_sort(B_U32 *array, int l, int r)
{
    if (l < r) {
        int m = partition(array, l, r);
        if (r > m+1) {
            real_quick_sort(array, m+1, r);
        }
        if (m-1 > l) {
            real_quick_sort(array, l, m-1);
        }
    }
}

static inline void swap_array_value(B_U32 *array, int a, int b)
{
    B_U32 c;

    c = array[a];
    array[a] = array[b];
    array[b] = c;
}

static int partition(B_U32 *array, int l, int r)
{
    int tl, tr;
    tl = l-1;
    tr = r;

    B_U32 v = array[r];

    while (1) {
        while (array[++tl] < v);
        while (--tr > tl && array[tr] >= v );

        if (tl < tr) {
            swap_array_value(array, tl, tr);
        }
        else {
            break;
        }
    }

    swap_array_value(array, tl, r);
    return tl;
}

在这个实现中，直接选用最后一个元素作为中间值。另外，一般的快速排序的实现，为了性能，当元素个数降到比较少的时候，就使用其它排序方法。

下面是测试用例，使用gtest做的测试：

#include "my_basetype.h"
#include "my_utils.h"
#include "gtest/gtest.h"

TEST(My_Sort_Algo, TestQuickSort)
{
        B_U32 orig1[] = {3, 4, 1, 7, 8, 9, 2, 0, 6, 5};
        B_U32 expect1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        quick_sort(orig1, ARRAY_SIZE(orig1));
        EXPECT_TRUE(0 == memcmp(orig1, expect1, ARRAY_SIZE(orig1)));

        B_U32 orig2[] = {3, 4};
        B_U32 expect2[] = {3, 4};
        quick_sort(orig2, ARRAY_SIZE(orig2));
        EXPECT_TRUE(0 == memcmp(orig2, expect2, ARRAY_SIZE(orig2)));

        B_U32 orig3[] = {3, 1, 1};
        B_U32 expect3[] = {1, 1, 3};
        quick_sort(orig3, ARRAY_SIZE(orig3));
        EXPECT_TRUE(0 == memcmp(orig3, expect3, ARRAY_SIZE(orig3)));

        B_U32 orig4[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        B_U32 expect4[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        quick_sort(orig4, ARRAY_SIZE(orig4));
        EXPECT_TRUE(0 == memcmp(orig4, expect4, ARRAY_SIZE(orig4)));

        B_U32 orig5[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        B_U32 expect5[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        quick_sort(orig5, ARRAY_SIZE(orig5));
        EXPECT_TRUE(0 == memcmp(orig4, expect5, ARRAY_SIZE(orig5)));


}

这个快速排序实现只为练手，仅供大家参考。