首页 > 代码库 > 快速排序的算法导论划分形式和hoare划分
快速排序的算法导论划分形式和hoare划分
1. hoare划分
1 int hoare_partition(int a[], int begin, int end) 2 { 3 int pivot = a[begin]; 4 int ini = begin; 5 int ter = end; 6 while (ini < ter) 7 { 8 while (a[ini] <= pivot && ini <end) 9 ++ini;10 while (a[ter] >= pivot && ter>begin)11 --ter;12 if (ini<ter)13 swap(a[ini], a[ter]);14 15 }16 swap(a[ter], a[begin]);17 return ter;18 19 }20 void quick_sort(int a[], int begin, int end)21 {22 if (begin < end)23 {24 int div = hoare_partition(a, begin, end);25 cout << div << endl;26 quick_sort(a, begin, div);27 28 quick_sort(a, div+1, end);29 }30 31 }
1
算法导论的划分形式
int partition(int a[], int begin, int end) 2 { 3 int pivot = a[begin]; 4 int cur = begin + 1; 5 int divid_location = begin; 6 for (; cur <= end; ++cur) 7 { 8 if (a[cur] < pivot) 9 {10 ++divid_location;11 int temp = a[divid_location];12 a[divid_location] = a[cur];13 a[cur] = temp;14 }15 }16 a[begin] = a[divid_location];17 a[divid_location] = pivot;18 return divid_location;19 }20 void quick_sort(int a[], int begin,int end)21 {22 if (end-begin > min_size)23 {24 int div = partition(a, begin, end);25 quick_sort(a, begin, div);26 int div_plus_1 = div + 1;27 quick_sort(a,div_plus_1, end);28 }29 insert_sort(a, begin, end);30 }区别在哪呢,区别在于hoare划分将区间分为两部分,而主元可能位于两个区间的任何一个,而算导的划分将其划为3部分。
median-of-3改进等比较简单,不再赘述。
关于快速排序的工业级实现,参见STL 源码剖析当中的讲解,我们会发现,和我们写的版本基本一致,当然为了保证递归不是很深,会进行优化,比如只对每次划分较短的一侧进行递归,另一个尾递归优化。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。