做网站的不给源文件,贵州seo技术查询,企业名录搜索软件下载,网页设计比赛策划案1. 简介
传统快速排序用的是双路快速排序#xff0c;即将大于基准值的部分放到基准值右侧#xff0c;小于基准值的部分放到基准值左侧#xff0c;但是这种算法面对过多的重复数据的数组#xff0c;时间复杂度会增多#xff0c;于是就有了三路快速排序的思想#xff0c;其…1. 简介
传统快速排序用的是双路快速排序即将大于基准值的部分放到基准值右侧小于基准值的部分放到基准值左侧但是这种算法面对过多的重复数据的数组时间复杂度会增多于是就有了三路快速排序的思想其想法是将数组分为三个区间假设选择数组的首元素作基准值e则小于基准值e的数组放到基准值的左侧等于基准值e的放到中间大于基准值e的放到右边即下图所示。
2. 思路
我们用i做循环遍历遍历整个数组我们选择数组的第一个元素做基准值e如下图
left指针代表当前搜索区间的开始下标 right指针代表当前搜索区间的结束下标 lt(less than)指针代表小于e的区间的结束下标 gt(greater than)代表大于e的区间的开始下标 i指针指向当前待处理的元素
记数组为nums我们分三种情况讨论该算法设当前nums[i]为x 1x和基准值e相等 i直接向后移动1位当前元素自动划分到等于e的区间
2x小于基准值e nums[lt1]和nums[i]互换并且lt和i都向前移动一位此次互换之前的数组都已经排好左侧的都遍历过了小于e的区间的元素都严格小于e而nums[lt1]在交换前是等于e区间的所以和nums[i]互换后nums[i]就是e所以直接i自增1移动因为交换后的nums[i]已经是等于e所以向后移动此时交换后nums[lt1]一定是严格小于e所以小于e的区间的结束下标lt指针也得向后移动1个位置。 3x大于基准值e nums[gt-1]和nums[i]互换gt向前移动1位此时i不向前移动因为交换过来的到底是大于基准值还是小于基准值还需要等待下次循环再判断但是交换后nums[gt-1]已经是大于基准值e且gt是大于e的区间的开始指针所以gt要减1来向前移动1位这样也保证了遍历到最后nums[i]如果还是大于e最后nums[i]与首元素交换的时候就不合理了。 最后(i gt的时候跳出循环i会在等于e的区间的最后我们要把nums[i]与nums[left]互换使得等于e的区间里的元素全是重复的e情况3中已经保证nums[i]不会大于e情况1也保证nums[i]不会等于e 经过一趟三路快速排序的划分后和传统的双路快速排序类似我们要分别在小于e和大于e的区间上继续进行三路快速排序的划分
3. 代码实现C语言
思路在注释中
//生成从x到y的整数随机数
int getIntRandom(int x, int y)
{// 传入时间戳生成伪随机数srand((unsigned int)time(NULL));return (int)(x (rand() % (y - x 1)));
}
//三路快速排序返回lt小于e的区间的结束下标和gt大于e的区间的开始下标
//以长度为2的数组的形式返回lt和gt
void divide3(int* nums, int left, int right)
{//left超过right递归结束if (left right) {return;}//随机选择一个下标做基准值的元素的下标不做随机化处理不能过长度很长的测试用例int rand_index getIntRandom(left, right);printf(%d\n, rand_index);//基准值int pivot nums[rand_index];//交换元素用的临时遍历int temp 0;//交换nums[rand_index]与nums[left]为了方便下面的交换//这样交换后还是等价于首元素做基准值temp nums[rand_index];nums[rand_index] nums[left];nums[left] temp;//注意到如果选择首元素做基准值那么lt最开始就是left1对应首元素下标//因为lt(less than)指针代表小于e的区间的结束下标int lt left;//gt默认从最右侧1开始因为假设最开始大于e的区间是无限大//gt无需担心越界因为我们遇到nums[i]大于e的情况交换的是nums[i]与nums[gt-1]int gt right 1;//i从left 1开始因为首元素是基准值遍历首元素后面的元素int i left 1;//循环结束的条件是i和gt指向同一个元素此时i左侧最近的区间是等于e的区间右侧是大于e的区间完成了一轮三路快速排序while(i gt){//如果当前元素和基准值相等i自增1if(nums[i] pivot){i;}//如果当前元素小于基准值else if(nums[i] pivot){//nums[lt1]和nums[i]互换temp nums[i];nums[i] nums[lt1];nums[lt1] temp;//lt和i都自增1lt;i;}//如果当前元素大于基准值else{//nums[gt-1]和nums[i]互换temp nums[i];nums[i] nums[gt-1];nums[gt-1] temp;//i无需自增1留着判断换过来的数//gt自减1因为多了一个大于e的数要向左扩大大于e的数组区间gt--;}}//交换nums[lt]与nums[left]temp nums[lt];nums[lt] nums[left];nums[left] temp;//递归小于e和大于e的区间divide3(nums, left, lt-1);divide3(nums, gt, right);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {divide3(nums, 0, numsSize - 1);*returnSize numsSize;return nums;
}提交结果
