保定建站服务,太原网站建设搜q479185700,网站中点击链接怎么做的,咨询服务网站源码快排排序是非常快的#xff0c;但是有一种情况快排是无法进行的。
912. 排序数组 - 力扣#xff08;LeetCode#xff09; 这道题看上去没什么问题#xff0c;但是如果我们用快排去提交的话#xff0c;发现快排其实是被针对了的。
有一个样例是这样的。如果我们按照快排的…快排排序是非常快的但是有一种情况快排是无法进行的。
912. 排序数组 - 力扣LeetCode 这道题看上去没什么问题但是如果我们用快排去提交的话发现快排其实是被针对了的。
有一个样例是这样的。如果我们按照快排的思想right指针将一路狂奔到left指针这里回合然后每次分割区间都是只分割出去一个数这样就会造成时间超限。 所以我们将快排进行优化实现三路划分。
原来的快排思想是将小于等于key的放在左边将大于等于key的放在右边这样形成了两个区间。 三路划分的思想其实就是将小于key的放在左边将大于key的放在右边将等于key的放在中间。 然后分割区间的时候左边小于key的一个右边大于key的一个中间的就不用再动了。 具体操作的方法
还是left在左侧right在右侧current遍历。
当current遇到比key小的就将current下的值和left交换然后将leftcurrent。因为left为和key相等的值交换过后left相当于是left左边是比key小的值left永远指向和key相等的值
当current遇到和key相等的值时就将current继续遍历。
当current遇到比key大的值就将current下的值和right交换然后将right--不先管right原位置的值的大小先交换此时right--后right右侧的值则永远都是比key大的值current不动因为不确定交换后的值的大小。进行新一轮的比较之后再决定去留 代码 /*** Note: The returned array must be malloced, assume caller calls free().*/int GetMidIndex(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right])return mid;else if (a[right] a[left]){return left;}else return right;}else{if (a[mid] a[right])return mid;else if (a[left] a[right])return left;else return right;}}void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void QuickSort(int* a, int begin, int end)
{if (begin end){ return;}int left begin;int current left1;int right end;int midi GetMidIndex(a, left, right);Swap(a[left], a[midi]);int key a[left];while (current right){if(a[current] key){Swap(a[current], a[right]);right--;}else if(a[current] key){Swap(a[current], a[left]);left;current; }else current;}QuickSort(a, begin,left-1);QuickSort(a, right1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize){QuickSort(nums,0,numsSize-1);*returnSize numsSize;return nums;
}
提交还有样例没过 做出三路划分后这个样例针对的是快排的三数取中GetMidIndex方法。
但是如果去掉三数取中方法当遇到接近有序的序列后就会超时。所以我们不能用普通的三数取中方法。 int GetMidIndex(int* a, int left, int right)
{int mid left(rand()%(right-left)); //中间的数不再固定。if (a[left] a[mid]){if (a[mid] a[right])return mid;else if (a[right] a[left]){return left;}else return right;}else{if (a[mid] a[right])return mid;else if (a[left] a[right])return left;else return right;}}
这样这道题就可以用快排的方法提交了。
