Chinaunix首页 | 论坛 | 博客
  • 博客访问: 7376653
  • 博文数量: 159
  • 博客积分: 10424
  • 博客等级: 少将
  • 技术积分: 14605
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-14 12:45
个人简介

啦啦啦~~~

文章分类
文章存档

2015年(5)

2014年(1)

2013年(5)

2012年(10)

2011年(116)

2010年(22)

分类: C/C++

2011-09-28 23:54:51

本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接,严禁用于任何商业用途。
作者:gfree.wind@gmail.com
博客:linuxfocus.blog.chinaunix.net
 

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

上代码。。。。
  1. #include "my_basetype.h"

  2. /**************************************************************************************/
  3. static int partition(B_U32 *array, int l, int r);
  4. static inline void swap_array_value(B_U32 *array, int a, int b);
  5. static void real_quick_sort(B_U32 *array, int l, int r);
  6. /**************************************************************************************/
  7. void quick_sort(B_U32 *array, int size)
  8. {
  9.     real_quick_sort(array, 0, size-1);
  10. }

  11. static void real_quick_sort(B_U32 *array, int l, int r)
  12. {
  13.     if (l < r) {
  14.         int m = partition(array, l, r);
  15.         if (r > m+1) {
  16.             real_quick_sort(array, m+1, r);
  17.         }
  18.         if (m-1 > l) {
  19.             real_quick_sort(array, l, m-1);
  20.         }
  21.     }
  22. }

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

  26.     c = array[a];
  27.     array[a] = array[b];
  28.     array[b] = c;
  29. }

  30. static int partition(B_U32 *array, int l, int r)
  31. {
  32.     int tl, tr;
  33.     tl = l-1;
  34.     tr = r;
  1.     B_U32 v = array[r];

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

  5.         if (tl < tr) {
  6.             swap_array_value(array, tl, tr);
  7.         }
  8.         else {
  9.             break;
  10.         }
  11.     }

  12.     swap_array_value(array, tl, r);
  13.     return tl;
  14. }
在这个实现中,直接选用最后一个元素作为中间值。另外,一般的快速排序的实现,为了性能,当元素个数降到比较少的时候,就使用其它排序方法。


下面是测试用例,使用gtest做的测试:
  1. #include "my_basetype.h"
  2. #include "my_utils.h"
  3. #include "gtest/gtest.h"

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

  10.         B_U32 orig2[] = {3, 4};
  11.         B_U32 expect2[] = {3, 4};
  12.         quick_sort(orig2, ARRAY_SIZE(orig2));
  13.         EXPECT_TRUE(0 == memcmp(orig2, expect2, ARRAY_SIZE(orig2)));

  14.         B_U32 orig3[] = {3, 1, 1};
  15.         B_U32 expect3[] = {1, 1, 3};
  16.         quick_sort(orig3, ARRAY_SIZE(orig3));
  17.         EXPECT_TRUE(0 == memcmp(orig3, expect3, ARRAY_SIZE(orig3)));

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

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


  26. }

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

阅读(2904) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~