青岛网站设计多少钱,如何防止网站被采集,学做网站格式工厂,济南网站建设熊掌号前言 在[C/C]排序算法 快速排序 (递归与非递归)一文中,对于快速排序的单趟排序一共讲了三种方法: hoare、挖坑法、双指针法 ,这三种方法实现的快速排序虽然在一般情况下效率很高,但是如果待排序数据存在大量重复数据,那这几种方法的效率就很低,而为了解决快速排序在这样特殊情况…前言 在[C/C]排序算法 快速排序 (递归与非递归)一文中,对于快速排序的单趟排序一共讲了三种方法: hoare、挖坑法、双指针法 ,这三种方法实现的快速排序虽然在一般情况下效率很高,但是如果待排序数据存在大量重复数据,那这几种方法的效率就很低,而为了解决快速排序在这样特殊情况下效率低下的问题, 三路划分就可以完美解决
三路划分
思想: 对于上述三种方法,其本质都是选定数组开头元素作特定值,让小的数据放左边,大的数据放右边。而三路划分顾名思义就是通过处理将数据分为三个部分 [小于特定值的部分 等于特定值的部分 大于特定值的部分] ,这样划分好后,只需要对小于特定值的部分和大于特定值的部分进行递归排序即可,中间的数据就不需要处理了,相比于上述三种方法效率提升很大,并且重复数据越多排序效率越快,当带排序数据全为重复数据时,时间复杂度甚至可以达到O(N)。
算法实现 首先我们定义一个cur指针指向begin的下一个元素,将begin开始所指元素定为关键值key 比较a[cur]与key的值,会出现三种情况 若a[cur]key,交换a[begin]和a[cur], cur, begin若a[cur]key,交换a[end]和a[cur],end--若a[cur]key,cur 重复比较操作,直到curend [解释]:
为什么a[begin]和a[cur]交换后, cur要, 而a[end]和a[cur]交换后,cur不和情况1一样呢? 因为a[end]和a[end]交换,目的是让大于key的值放到后面,而end所指元素我们不知道其与key的大小关系,所以下一次循环,还得判断其与key的关系才行,cur会跳过这个元素。而begin初始所指元素就是关键值key, 当第一次找到比key小的数让两者交换,此时cur所指元素就是关键值,再仔细揣摩一下,只有小的数往左放的时候begin才会,碰到大的数会把他往后放,放完还得比较当前cur所指的元素,碰到与key相同的元素不交换,cur往后走,这样我们会发现begin只会指向和key一样大的元素,所以交换完后,cur可以。 单趟排序图解如下: a[cur]key,交换,cur,begin a[cur]key,交换,cur,begin a[cur]key, cur a[cur]key, cur a[cur]key,交换a[end]和a[cur],end-- a[cur]key, cur a[cur]key, cur,此时curend,排序完成,将数据分为了三个部分 因为单趟排序排好后划分了三个部分,我们处理两边的部分需要返回两个值,所以就不单独封装三路划分的单趟排序了
代码如下:
void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}int GetMid(int* a, int begin, int end)
{int mid (begin end) / 2;if (a[begin] a[mid]){if (a[mid] a[end])return mid;else if (a[begin] a[end])return end;elsereturn begin;}else{if (a[begin] a[end])return begin;else if (a[mid] a[end])return end;elsereturn mid;}
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int mid GetMid(a, begin, end);swap(a[begin], a[mid]);//由于begin和end要改变,提前保存,便于递归使用int left begin;int right end;int cur begin 1;int key a[begin];while (cur end){if (a[cur] key){swap(a[cur], a[begin]);begin;cur;}else if (a[cur] key){swap(a[cur], a[end]);end--;}else{cur;}}QuickSort(a, left, begin - 1);QuickSort(a, end 1, right);
}
