Zero Lee的专栏

快速排序C++实现

2种方案的C++实现:
  1 #include <vector>
  2 #include <iterator>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <cstdlib>
  6 #include <ctime>
  7 #include <cassert>
  8 
  9 void printv(const std::vector<int>& v)
 10 {
 11     std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
 12     std::cout << std::endl;
 13 }
 14 
 15 void printv(const std::vector<int>& v, int l, int h)
 16 {
 17     std::copy(v.begin()+l, v.begin()+h+1, std::ostream_iterator<int>(std::cout, " "));
 18     std::cout << std::endl;
 19 }
 20 
 21 int exchange(int& a, int& b)
 22 {
 23     int tmp = a;
 24     a = b;
 25     b = tmp;
 26 }
 27 
 28 int partition1(std::vector<int>& v, int l, int h)
 29 {
 30     int i = l-1;
 31     int pivot = v[h];
 32     int j = l;
 33     while (j < h) {
 34         if (v[j] < pivot) {
 35             i++;
 36             exchange(v[i], v[j]);
 37         }
 38         j++;
 39     }
 40     exchange(v[i+1], v[h]);
 41     return i+1;
 42 }
 43 
 44 int partition2(std::vector<int>& v, int l, int h)
 45 {
 46     int m = l+(h-l)/2;
 47     int i = l;
 48     int j = h;
 49 
 50     int pivot = v[m];
 51     while (1) {
 52         while (v[i] < pivot) i++;
 53         while (v[j] > pivot) j--;
 54         if (!(i<j)) {
 57             return j;
 58         }
 59         exchange(v[i], v[j]);
 60         i++;j--;
 61     }
 62 }
 63 
 64 void myQuickSort1(std::vector<int>& v, int l, int h)
 65 {
 66 /*
 67   Please note, returned m is the loc of pivot,
 68   in below myQuickSort1, can remove m, since left of m, all <= pivot
 69   right of m, all >= pivot
 70  */
 71     if (l < h) {
 72         int m = partition1(v, l, h);
 73         myQuickSort1(v, l, m-1);
 74         myQuickSort1(v, m+1, h);
 75     }
 76 }
 77 
 78 void myQuickSort2(std::vector<int>& v, int l, int h)
 79 {
 80 /*
 81  if partition2 return i, please call below
 82   myQuickSort2(v, l, m-1);
 83   myQuickSort2(v, m, h);
 84  else if it return j, please call below
 85   myQuickSort2(v, l, m);
 86   myQuickSort2(v, m+1, h);
 87 */
 88     if (l < h) {
 89         int m = partition2(v, l, h);
 90         myQuickSort2(v, l, m);
 91         myQuickSort2(v, m+1, h);
 92     }
 93 }
 94 
 95 int main()
 96 {
 97 
 98     const int N = 100;
 99     srand(time(0));
100     std::vector<int> v, vtmp;
101     for (int i = 0; i < N; i++)
102         v.push_back(int(rand()%N));
103     vtmp.insert(vtmp.end(), v.begin(), v.end());
104     std::cout << "Original data sequence is:\n";
105     std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
106     std::cout << std::endl;
107     myQuickSort1(v, 0, N-1);
108     std::cout << "After quicksort(1), the data sequence is:\n";
109     std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
110     std::cout << std::endl;
111 
112     myQuickSort2(vtmp, 0, N-1);
113     std::cout << "After quicksort(2), the data sequence is:\n";
114     std::copy(vtmp.begin(), vtmp.end(), std::ostream_iterator<int>(std::cout, " "));
115     std::cout << std::endl;
116 
117     assert(v==vtmp);
118     return 0;
119 }
120 

posted on 2011-09-16 14:15 Zero Lee 阅读(506) 评论(0)  编辑 收藏 引用 所属分类: Data structure and algorithms


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理