网站 目标,装修无忧网,js模版网站,网址制作网站目录
1.快速排序
Hoare版本#xff1a;
挖坑法#xff1a;
前后指针版本:
快速排序的时间复杂度
2.快速排序的优化
三数取中法选key
随机数选key
三路划分法
3. 非递归实现快速排序 1.快速排序
快速排序一共有三种版本#xff1a;Hoare版本、挖坑法、前后指针版本…目录
1.快速排序
Hoare版本
挖坑法
前后指针版本:
快速排序的时间复杂度
2.快速排序的优化
三数取中法选key
随机数选key
三路划分法
3. 非递归实现快速排序 1.快速排序
快速排序一共有三种版本Hoare版本、挖坑法、前后指针版本。
Hoare版本 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 也就是说如果我们要排一个升序我们可以在待排数据中选择一个值key把大于该值的数据放在该值的右边小于该值的数据放在该值的左边然后在左边的数据中同样选择一个值重复以上步骤同时在右边的数据中选择一个值重复以上步骤直到key的左边和右边都是有序的此时所有数据都有序了。
过程如图所示是一个递归的过程 下面我们先来实现一趟的排序 可以选左边第一个数据为key然后从右边先开始遍历当右边找到小于key的值时停下来当左边遍历找到大于key的值时也停下来然后交换左右两边的数据最后当左右相遇的时候把key交换到相遇位置这就保证了小于key的数据落入key左边大于key的数据落在key右边。 上代码 int PartSort(int* a, int left, int right)
{int key a[left];int keyi left;while (left right){while (left right a[right] key){right--;}while (left right a[left] key){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);return left;
} 我们单趟排完之后应该如下图所示 下面来解释一下代码中的循环判断条件 最外层循环leftright左右相遇时就停止。 内层循环left right a[right] key这段代码解决了两个可能存在的问题 1. 死循环问题 当待排数据如下面所示就可能造成死循环 所以a[right] key时继续遍历。 2. 越界问题 如果a[right] key时继续遍历下面极端情况可能导致越界 所以我们在内层循环中还要判断一下 leftright。 这就是单趟排序的代码了我们要实现对所有数据的升序递归调用就行了当完成一趟排序时返回相遇位置然后对相遇位置的左边和右边数据继续重复进行以上操作。这有些类似于二叉树的递归问题。
代码如下
//交换函数
Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//快速排序
int PartSort(int* a, int left, int right)
{int key a[left];int keyi left;while (left right){while (left right a[right] key){right--;}while (left right a[left] key){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int keyi PartSort(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1,end);
}Print(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}
int main()
{int a[] { 9,7,5,2,4,7,1,6,0,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);Print(a, sizeof(a) / sizeof(int));return 0;
}
整个排序过程如下图 注意下面这段代码的作用是当区间只有一个值或者出现区间不存在的情况的时候就返回。 if (begin end) { return; } 不知道大家有没有注意到一个情况我们在选择key为左边的数据时先让右边开始遍历这是为什么呢
首先我们选左边的数据为key那最终相遇位置的数就一定要比key的值小这样交换后才能保证key的左边的值都比它小右边的值都比它大那我们如何保证相遇位置的值一定就比key小呢
先给结论: 1. 左边做key右边先走保证了相遇位置的值比key小。 2. 右边做key左边先走保证了相遇位置的值比key大。 下面我们来论证一下 结论2的论证同上。
这就是Hoare版本但是通过上文的学习这种版本存在的坑太多下面我们来学一种方法避坑。
挖坑法 挖坑法的单趟排序过程如图所示 先选左边的一个数据把它作为坑并保存它的值然后继续右边遍历找到比key小的值就停下挖走这个值填坑挖走后形成新的坑左边遍历找比key大的值就停下挖走这个值填坑......最后左右相遇把保存的key值填坑。 代码实现如下: //挖坑法
int PartSort2(int* a, int left, int right)
{int key a[left];int hole left;while (left right){while (left right a[right] key){right--;}a[hole] a[right];hole right;while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int keyi PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
Print(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}
int main()
{int a[] { 9,7,5,2,4,7,1,6,0,8 };QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);Print(a, sizeof(a) / sizeof(int));return 0;
} 前后指针版本: 前后指针版本单趟排序过程如下图所示 我们可以看到cur在找小如果a[cur]keyprev然后交换a[prev]和a[cur]如果a[cur]keyprev不动整个过程中cur一直不停的往后走直到cur越界就结束了此时再交换key和a[prev]。 代码如下 //前后指针版本
int PartSort3(int* a, int left, int right)
{int prev left;int cur left 1;int keyi left;while (cur right){if (a[cur] a[keyi]){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
Print(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}
int main()
{int a[] {6,1,2,7,9,3,4,5,10,8};QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);Print(a, sizeof(a) / sizeof(int));return 0;
} 快速排序的时间复杂度 时间复杂度最好O(N*logN)。 时间复杂度最坏O(N^2)。 什么时候最好呢
当每次选的key恰好是中位数时每次都把数据分成两份每次减少一半的运算量相当于二分法 什么时候最坏呢
当待排数据本来就是有序的时候每次选key选的都是最小的值此时就相当于等差数列 那我们选key有两种方案
1. 随机数取key。
2. 三数取中法选key。
这样可以保证不会是最坏的情况。
2.快速排序的优化
三数取中法选key 三数取中法就是把左边、右边和中间的三个数相比较取出其中的中位数把它作为key这样就可以提高快速排序的效率。 代码如下
//三数取中法选key
int GetMidIndex(int* a, int left, int right)
{int mid (left right) / 2;if (a[mid] a[left]){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[right] a[left]){return right;}else{return left;}}
}
//快速排序
//Hoare版本
int PartSort(int* a, int left, int right)
{int midi GetMidIndex(a, left, right);Swap(a[left], a[midi]);int keyi left;while (left right){while (left right a[right] a[keyi]){right--;}while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int keyi PartSort(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}以上就是三数取中法对快速排序的优化了下面我们来看一道题看看我们的快速排序能不能通过
题目链接力扣LeetCode
结果呢 超出时间限制了这其实是力扣针对快速排序三数取中专门设计的一个测试用例他故意把左边、右边和中间的值都设的很小这样即使你三数取中选出的key依旧很小接近我们上文说的最坏情况所以会超出时间限制那我们不玩三数取中能不能过呢 结果很明显还是过不了这次他直接给了个有序的测试用例这就直接是我们上文中所说的最坏情况了那怎么办呢别急我们还有一招
随机数选key 随机数取key的意思是我们保证左右的数据位置不变中间数据的位置取一个随机数这样我们三数取中得到的key也是随机的数据这样力扣就针对不到我们了。 代码如下 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}//三数取中法选key
int GetMidIndex(int* a, int left, int right)
{//随机数取keyint midleft(rand()%(right-left));if (a[mid] a[left]){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[right] a[left]){return right;}else{return left;}}
}
//前后指针版本
int PartSort3(int* a, int left, int right)
{int midi GetMidIndex(a, left, right);Swap(a[left], a[midi]);int prev left;int cur left 1;int keyi left;while (cur right){if (a[cur] a[keyi]){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}int* sortArray(int* nums, int numsSize, int* returnSize) {srand(time(0));QuickSort(nums,0,numsSize-1);*returnSizenumsSize;return nums;
} int midleft(rand()%(right-left)); 表示中间位置取随机位置为了防止随机数越界我们用它取余right-left。 但是这就结束了吗还是太天真了力扣预判了你的预判不信再运行一下 这次它给的数据全部相同那不管我们怎么取key值都是取的最小的这就又相当于最坏的情况可见这道题为了针对快速排序是费尽了心思那我们就没办法了吗
当然不是我们还有终极一招
三路划分法 何谓三路划分呢我们之前的快速排序是把大于等于key的放在右边小于等于key的放在左边相当于待排数据分为两份而三路划分的意思是把小于key的放在左边大于key的放在右边等于key的放在中间如图所示 这种方法就是把等于key的收拢在中间位置当我们递归子区间的时候只递归小于和大于的区间这样当待排数据中有重复数据时可以大大提高效率尤其是上述测试用例收拢之后左右子区间直接就没有值了都不用再递归。 下图就是三路划分的思想 我们可以演示一下三路划分的过程 可以看到三路划分的本质就是 1. 和key相等的值都被收拢到中间 2. 小的被甩到左边大的被甩到右边。 代码如下 //三数取中法选key
int GetMidIndex(int* a, int left, int right)
{//随机数取keyint midleft(rand()%(right-left));if (a[mid] a[left]){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[right] a[left]){return right;}else{return left;}}
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}//三数取中int midi GetMidIndex(a, begin, end);Swap(a[begin], a[midi]);int leftbegin;int rightend;int curleft1;int keya[left];//三路划分while (cur right){if (a[cur] key){Swap(a[left], a[cur]);left;cur;}else if (a[cur] key){Swap(a[right], a[cur]);right--;}else{cur;}}//递归QuickSort(a, begin, left - 1);QuickSort(a, right 1, end);
}int* sortArray(int* nums, int numsSize, int* returnSize) {srand(time(0));QuickSort(nums,0,numsSize-1);*returnSizenumsSize;return nums;
} 到这这道题就用了三种优化方式了而且三种方式缺一不可那能不能解决问题呢 当然可以啦如果没有上述优化方式用快排做这道题会很坑不是快排不快而是“人红是非多”啊快排在这道题上被针对的体无完肤反而堆排、希尔排序等还能通过。
3. 非递归实现快速排序 我们前文讲的递归方式实际上递归过程处理的是左右子区间现在我们不能用递归那要如何处理左右子区间呢 其实可以用栈实现每次从栈中拿出一段区间单趟分割处理然后让左右子区间入栈。 代码如下栈部分的代码可以拷贝前面章节的这里只给核心代码
//前后指针版本
int PartSort3(int* a, int left, int right)
{int prev left;int cur left 1;int keyi left;while (cur right){if (a[cur] a[keyi]){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}
//非递归方式实现快排
void QuickSortNonR(int* a, int begin, int end)
{ST st;STInit(st);STPush(st, end);STPush(st, begin);while (!STEmpty(st)){int left STTop(st);STPop(st);int right STTop(st);STPop(st);int keyi PartSort3(a, left, right);if (keyi 1 right){STPush(st, right);STPush(st, keyi 1);}if (left keyi-1){STPush(st, keyi-1);STPush(st, left);}}STDestroy(st);
}
好了以上就是快速排序下节继续学习归并排序
未完待续。。。
