首页 > 代码库 > 算法就是这么一回事（排序）（第三部分）
算法就是这么一回事（排序）（第三部分）
六、快速排序
快速排序是通过一种把集合中的元素按照第一个元素（这个是动态过程变化）作为标杆来分为两部分，前面一部分比他小（或等），后面一部分比它大。然后就是通过适当的程序来递归这个过程，当最后没有交换说明需要退出递归。
上图
。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为 "基准"（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
代码：
1 #include <iostream> 2 #include <iterator> 3 #include <vector> 4 #include <ctime> 5 #include <random> 6 #include <functional> 7 #include <algorithm> 8 using namespace std; 9 int intSwap(int& a,int& b) 10 { 11 int intswaptemp=a; 12 a=b; 13 b=intswaptemp; 14 return 0; 15 } 16 /*---------------------------------------------------- 17 -----------------快速排序（STL版本）--------------------- 18 参数：迭代器、cmp 19 cmp可以为less、greater等函数 20 template<typename _Tp> 21 struct less_equal : public binary_function<_Tp, _Tp, bool> 22 { 23 bool 24 operator()(const _Tp& __x, const _Tp& __y) const 25 { return __x <= __y; } 26 }; 27 这个东西第一次学需要自己拿笔算写，不需要想，因为太费劲了。 28 ----------------------------------------------------*/ 29 template<typename Conditerator,typename Compare> 30 int quickSortIter(Conditerator begin,Conditerator end,Compare cmp) 31 { 32 if(begin!=end)//递归终止条件 33 { 34 Conditerator left=begin;//左 35 Conditerator right=end;//右 36 Conditerator pivot=left++;//用于作为参考相对大小的数子 37 while(left!=right) 38 { 39 if(cmp(*left,*pivot))//从begin开始下一个比较是否小于begin， left<begin(pivot) 40 ++left;//如果成立，left移向下一个未和begin比较的值 41 else 42 { 43 while((left!=right)&&cmp(*pivot,*right))//begin(pivot)<right 44 right--; 45 iter_swap(left,right); 46 } 47 } 48 if(cmp(*pivot,*left))//这里就是为了防止left和right重合 49 --left;//因为在上面程序中，最后会导致left和right重合，需要分离left 50 iter_swap(begin,left);//保留了pivot,通过交换到前面一组中的最后一位 51 quickSortIter(begin,left,cmp); 52 quickSortIter(right,end,cmp); 53 } 54 return 0; 55 } 56 template<typename T> 57 inline int quickSort(T begin,T end) 58 { 59 quickSortIter(begin,end, 60 less_equal<typename iterator_traits<T>::value_type>()); 61 return 0; 62 } 63 inline int QuickSortVector(vector<int> &ivec) 64 { 65 quickSort(ivec.begin(),ivec.end()); 66 return 0; 67 } 68 /*---------------------------------------------------- 69 -----------------快速排序（vector版本）------------------ 70 参数：vector<int> 71 关键信息：通过合适的交换来实现，以第一个begin值为临时交换的参考值 72 解释同上 73 注意：一定要搞清楚>=和<=的逻辑关系，否则error或者死循环 74 ----------------------------------------------------*/ 75 int quicksort_vector(vector<int>& ivec,int begin,int end) 76 { 77 if(begin!=end) 78 { 79 int left=begin; 80 int right=end; 81 int pivot=left++;//设置参考值（用于比较） 82 while(left!=right) 83 { 84 if(ivec[pivot]>=ivec[left]) 85 ++left; 86 else 87 { 88 while((left!=right)&&(ivec[pivot]<=ivec[right])) 89 --right; 90 intSwap(ivec[left],ivec[right]); 91 } 92 } 93 if(ivec[pivot]<=ivec[left]) 94 left--; 95 intSwap(ivec[begin],ivec[left]); 96 quicksort_vector(ivec,begin,left); 97 quicksort_vector(ivec,right,end); 98 } 99 return 0;100 }101 inline int quicksort1(vector<int> &ivec)102 {103 quicksort_vector(ivec,0,ivec.size()-1);104 return 0;105 }106 int main()107 {108 clock_t start,end;109 vector<int> ivec,copyivec;110 srand(14);111 for(int i=0;i<10000;i++)//10k112 ivec.push_back((int)rand());113 copyivec=ivec;114 start=clock();115 QuickSortVector(ivec);116 end=clock();117 for(int i=0;i<10000;i+=500)118 cout<<ivec[i]<<‘\t‘;119 cout<<endl;120 cout<<"the time of 1 is "<<end-start<<endl;121 start=clock();122 quicksort1(copyivec);123 end=clock();124 for(int i=0;i<10000;i+=500)125 cout<<ivec[i]<<‘\t‘;126 cout<<endl;127 cout<<"the time of 2 is "<<end-start<<endl;128 129 return 0;130 }
乱数快速排序有一个值得注意的特性，在任意输入数据的状况下，它只需要O(n log n)的期望时间。是什么让随机的基准变成一个好的选择？
假设我们排序一个数列，然后把它分为四个部份。在中央的两个部份将会包含最好的基准值；他们的每一个至少都会比25%的元素大，且至少比25%的元素小。如果我们可以一致地从这两个中央的部份选出一个元素，在到达大小为1的数列前，我们可能最多仅需要把数列分区2log2 n次，产生一个 O(nlogn)算法。
不幸地，乱数选择只有一半的时间会从中间的部份选择。出人意外的事实是这样就已经足够好了。想像你正在翻转一枚硬币，一直翻转一直到有 k 次人头那面出现。尽管这需要很长的时间，平均来说只需要 2k 次翻动。且在 100k 次翻动中得不到 k 次人头那面的机会，是像天文数字一样的非常小。借由同样的论证，快速排序的递归平均只要2(2log2 n)的调用深度就会终止。但是如果它的平均调用深度是O(log n)且每一阶的调用树状过程最多有 n 个元素，则全部完成的工作量平均上是乘积，也就是 O(n log n)。
| 数据结构 | 不定 |
|---|---|
| 最差时间复杂度 |  |
| 最优时间复杂度 |  |
| 平均时间复杂度 | |
| 最差空间复杂度 | 根据实现的方式不同而不同 |
算法就是这么一回事（排序）（第三部分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。