Chinaunix首页 | 论坛 | 博客
  • 博客访问: 489652
  • 博文数量: 23
  • 博客积分: 398
  • 博客等级: 一等列兵
  • 技术积分: 850
  • 用 户 组: 普通用户
  • 注册时间: 2012-06-03 22:18
文章分类

全部博文(23)

文章存档

2013年(9)

2012年(14)

分类: C/C++

2012-10-10 09:52:16

    最近学习算法,终于弄明白了快速排序的原理,并敲了代码验证,稍微总结一下以便复习。
概述:

    快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2),但由于平均运行时间为O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对进行随机化的可能,使得快速排序在一般情况下是最实用的排序方法之一。
 快速排序被认为是当前最优秀的内部排序方法。


      快速排序每次将待排序数组分为两个部分,在理想状况下,每一次都将待排序数组划分成等长两个部分,则需要logn次划分。
  而在最坏情况下,即数组已经有序或大致有序的情况下,每次划分只能减少一个元素,快速排序将不幸退化为,所以快速排序时间复杂度下界为O(nlogn),最坏情况为O(n^2)。在实际应用中,快速排序的平均时间复杂度为O(nlogn)。
  快速排序在对序列的操作过程中只需花费常数级的空间。S(1)。
  但需要注意递归栈上需要花费最少logn 最多n的空间。

c++ code :

点击(此处)折叠或打开

  1. /* quikSork.cpp 快排递归算法*/
  2. /* 快排算法描述如下:
  3.  * 快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

  4. 步骤为:

  5.     1) 从数列中挑出一个元素,称为 "基准"(pivot),
  6.     2) 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面
  7.        (相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  8.     3) 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
  9.         合并:由于两个子序列是就地排序的,所以对它们的合并不需要操作,整个序列L[m .. n]已排好序。
  10. */

  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <time.h>
  14. #include <iostream>
  15. using namespace std;

  16. template <class T>
  17. void Swap(T &x, T &y)
  18. {
  19.     T tmp;

  20.     tmp = x;
  21.     x = y;
  22.     y = tmp;
  23. }
  24. // 进行一趟快排,并返回分界的基准
  25. template <class Type>
  26. int partition(Type array[], int left, int right)
  27. {
  28.     Type x = array[left]; // 找基准点,之后array[left]相当空单元
  29. /*
  30.     while (left < right) {
  31.         // right --> left 扫描 find smaller than x
  32.         while (right > left && array[right] >= x) {
  33.             right--;
  34.         }
  35.         if (left < right) {
  36.             array[left] = array[right]; //<= x的存入空单元
  37.             left++;
  38.         }
  39.         // left --> right 扫描 find bigger than x
  40.         while (left < right && array[left] < x) {
  41.             left++;
  42.         }
  43.         if (left < right) {
  44.             array[right] = array[left]; //>= x的存入空单元
  45.             right--;
  46.         }
  47.     }
  48.     array[left] = x; //insert
  49.     return left;
  50. */

  51.  /* 或者使用下面的改进代码,原理和上面一样,只不过代码少点 */
  52.     int p_left = left;
  53.     int p_right = right + 1;

  54.     // 找分界点,
  55.     for( ; ;) {
  56.         while(array[++p_left] < x && p_left < right)
  57.             ; //left-->right find one bigger than x
  58.         while(array[--p_right] > x) //array[p_right] >= x = array[left]相当一道栏杆
  59.             ; //right-->left find one smaller than x
  60.         if(p_left >= p_right)
  61.             break;
  62.         Swap(array[p_left], array[p_right]);//交换后左边小,右边大
  63.     } // end for
  64.     
  65.     // 找到的数 array[p_right] 一定 <= x,found one middle position for x
  66.     array[left] = array[p_right];
  67.     array[p_right] = x; // insert to middle position

  68.     return p_right; //返回分界下标
  69. }

  70. template <class Type>
  71. void quikSort(Type array[], int pos_start, int pos_end)// pos_start,pos_end为下标
  72. {
  73.     if (pos_start < pos_end) {
  74.         int partition_pos;
  75.         partition_pos = partition(array, pos_start, pos_end);//一趟快排,获得基准点

  76.         quikSort(array, pos_start, partition_pos-1); //递归分解,对左边进行快排
  77.         quikSort(array, partition_pos+1, pos_end); //递归分解,对右边进行快排
  78.     }
  79. }


  80. template <class T>
  81. void print_array(T a[], int n)
  82. {
  83.     for (int i = 0; i < n; i++) {
  84.         cout << a[i] << " ";
  85.     }
  86.     cout << endl;
  87. }

  88. /* ------------------------------------------------------------------------ */
  89. /* 我们容易发现,快排算法的性能取决于划分的对称性。通过修改partition函数可以设计出采用
  90.  * 随机选择策略的快排算法。也就是说找基准时从array[left,right]中随机找一个作为划分的基准
  91.  * 而不是只以第一个[left]作为基准。
  92.  */
  93.  (关于随机数请阅读我的另一博文:http://blog.chinaunix.net/uid-27034868-id-3368530.html
  94.  //随机生成某范围的随机整数,调用前用srand设置种子
  95. int range_random(int start, int end)
  96. {
  97.     return    ( start + rand() % (end - start + 1) );
  98. }

  99. template < class T >
  100. int Random_part(T array[], int left, int right)
  101. {
  102.     int rd = range_random(left, right);// 从left到right中取随机下标
  103.     Swap(array[rd], array[left]);
  104.     
  105.     return partition(array, left, right);
  106. }

  107. template <class Type>
  108. void random_quikSort(Type array[], int pos_start, int pos_end)// pos_start,pos_end为下标
  109. {
  110.     if (pos_start < pos_end) {
  111.         int partition_pos;
  112.         partition_pos = Random_part(array, pos_start, pos_end);//一趟快排,获得基准点

  113.         random_quikSort(array, pos_start, partition_pos-1); //递归分解,对左边进行快排
  114.         random_quikSort(array, partition_pos+1, pos_end); //递归分解,对右边进行快排
  115.     }
  116. }

  117. /* ------------------------------------------------------------------------- */

  118. int main(void)
  119. {
  120.     int a[] = {7, 2, 5, 6, 0, 10, 4};

  121.     quikSort(a, 0, sizeof(a)/sizeof(a[0])-1);
  122.     print_array(a, sizeof(a)/sizeof(a[0]));
  123.     
  124.     int b[] = {1, 2, -2, 0, 7, 18, 4, 3, 4, 8};
  125.    
  126.     srand((unsigned)time(NULL));
  127.     random_quikSort(b, 0, sizeof(b)/sizeof(b[0])-1);
  128.     print_array(b, sizeof(b)/sizeof(b[0]));
  129.     
  130.     return 0;
  131. }


  注:本博客的文章除注明有“转载”字样的外,均为原创,欢迎转载,请注明文字出处,谢谢!
阅读(6953) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~