脚本宝典收集整理的这篇文章主要介绍了快速排序--洛谷卡TLE后最终我还是选择了三向切割,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
这篇文章呢,我们接着聊一下排序算法,我们之前已经谈到了简单插入排序 和ta的优化版希尔排序 ,这节我们要接触一个更“高级”的算法了--快速排序。 在做洛谷的时候,遇到了一道卡优化的题,如果没有去对快排进行优化的话,会有几个点是TLE的,后边我们可以围绕这道题来做各种优化,先来认识一下快速排序。
假如我们的计算机每秒钟可以运行 10 亿次,那么对 1 亿个数进行排序,桶排序只需要 0.1 秒,而冒泡排序则需要 1 千万秒,达到 115 天之久,是不是很吓人?那有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”! 假设我们现在对“** 6 1 2 7 9 3 4 5 10 8”这 10 个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,这就是一个用来参照的数,待会儿你就知道它用来做啥了)。为了方便,就让第一个数 6 作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在 6 的右边,比基准数小的数放在 6 的左边**,类似下面这种排列。
3 1 2 5 4 6 9 7 10 8
在初始状态下,数字 6 在序列的第 1 位。我们的目标是将 6 挪到序列中间的某个位置,假设这个位置是 k。现在就需要寻找这个 k,并且以第 k 位为分界点,左边的数都小于等于 6,右边的数都大于等于 6。
方法其实很简单:分别从初始序列“ 6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于 6 的数,再从左往右找一个大于 6 的数,然后交换它们。这里可以用两个变量 i 和 j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵 i”和“哨兵 j”。刚开始的时候让哨兵 i 指向序列的最左边(即 i=1),指向数字 6。让哨兵 j 指向序列的最右边(即 j=10),指向数字 8。
图源: 《啊哈算法》
#include <iostream>
#include<cstdio>
int a[1000001];//定义全局变量,这两个变量需要在子函数中使用
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//递归方法
void quicksort(int left, int right) {
//举例子可得出若左边大于等于右边就返回?
//大于的情况是:index刚好==right,然后还要再去(index+1,right)
if (left >= right) {
return;
}
//默认基准index是最左边那个,且i从左边开始,j从右边开始
int i = left, j = right, index = left;
//重构方法
//大前提,两个没相遇
while (i != j) {
//里边还得判断一下i<j,因为外边的大前提,里边可能会破坏掉
while (a[j] >= a[left]&&i<j) {
j--;
}
while(a[i] <= a[left]&&i<j){
i++;
}
//若i,j还未相遇
if (i < j) {
swap(&a[i], &a[j]);
}
}
//出来时i,j必然相遇
swap(&a[i],&a[index]);
//将i赋值给基准
index = i;
quicksort(left, index - 1);
quicksort(index + 1, right);
}
由于是单边搜索,后两个点都TLE
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctyPE.h>
#include <time.h>
void swap(int arr[], int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void QuickSort(int arr[], int left, int right)
{
int i, pivot;
if (left >= right)
return;
pivot = left;
swap(arr, left, (left + right) / 2);
for (i = left + 1; i <= right; i++) //单边搜索,可以该为双向搜索
if (arr[i] < arr[left])
swap(arr, i, ++pivot);
swap(arr, left, pivot);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
int main()
{
int n;
int *arr;
int i;
scanf("%d", &n);
arr = (int*)malloc(sizeof(int) * (n + 1));
for (i = 1; i <= n; i++)
scanf("%d", arr + i);
QuickSort(arr, 1, n);
for (i = 1; i <= n; i++)
printf("%d ", arr[i]);
return 0;
}
只是最后一个点TLE了,而最后一个点,刚好就是常数列的情况
#include <iostream>
#include<cstdio>
int a[100010];//定义全局变量,这两个变量需要在子函数中使用
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//递归方法
void quickSort(int left, int right) {
//举例子可得出若左边大于等于右边就返回?
//大于的情况是:index刚好==right,然后还要再去(index+1,right)
if (left >= right) {
return;
}
//默认基准index是最左边那个,且i从左边开始,j从右边开始
int i = left, j = right, index ;
int mid=(left+right)/2;
swap(&a[left],&a[mid]);
index=left;
//重构方法
//大前提,两个没相遇
while (i != j) {
//里边还得判断一下i<j,因为外边的大前提,里边可能会破坏掉
while (a[j] >= a[left]&&i<j) {
j--;
}
while(a[i] <= a[left]&&i<j){
i++;
}
//若i,j还未相遇
if (i < j) {
swap(&a[i], &a[j]);
}
}
//出来时i,j必然相遇
swap(&a[i],&a[index]);
index = i;
quickSort(left, index - 1);
quickSort(index + 1, right);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
quickSort(0, n - 1);
for (int i = 0; i < n; i++) {
i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
}
}
还没三数取中,取到的mid是最小的话还是会退化到冒泡n平方
#include<cstdio>
#include<iostream>
using namespace std;
int a[100010];
//交换元素位置
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void quickSort(int* arr, int low, int high) {
//若长度已经不符合要求,直接返回
if (low >= high) {
return;
}
int left = low;
int right = high;
//选取中间为基准,注意是取中间的值,而不是下标,因为下标可能在后续交换中会改变
//比如left走到了mid这里,而right停在了mid右边,这时会去交换,arr[mid]就变了
int mid = arr[(low + high) >> 1];
while (left <= right) {
//注意是小于,如果是小于等于的话,常数列就会一直left移动,而right不移动,沦为n平方
while (arr[left] < mid) {
left++;
}
//同样注意是大于
while (arr[right] > mid) {
right--;
}
//这里要注意是小于或等于,以便于left和right直接跳到枢纽点的左右
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
//递归调用
//right走到了区间一的尾部
quickSort(arr,low, right);
//left走到了区间二的头部
quickSort(arr, left, high);
}
int main()
{
int n, i;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> a[i];
}
quickSort(a,1,n);
for (i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
此处取到的mid是60
while (arr[left] < mid) {
left++;
}
//同样注意是大于
while (arr[right] > mid) {
right--;
}
//这里要注意是小于或等于,以便于left和right直接跳到枢纽点的左右
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
//递归调用
//right走到了区间一的尾部
quickSort(arr,low, right);
//left走到了区间二的头部
quickSort(arr, left, high);
自行用一定数据量测试的话,时间效率上差距还算不上很大的。
#include<cstdio>
#include<iostream>
#include"RcdSQList.h"
using namespace std;
//int a[100010];
//交换元素位置
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//三数取中
int getmid(int* array, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] <= array[right])
{
if (array[mid] < array[left])
return left;
else if (array[mid] > array[right])
return right;
else
return mid;
}
else
{
if (array[mid] < array[right])
return right;
else if (array[mid] > array[left])
return left;
else
return mid;
}
}
void quickSort(int* arr, int low, int high) {
//若长度已经不符合要求,直接返回
if (low >= high) {
return;
}
int left = low;
int right = high;
//选取中间为基准,注意是取中间的值,而不是下标,因为下标可能在后续交换中会改变
//比如left走到了mid这里,而right停在了mid右边,这时会去交换,arr[mid]就变了
//调用三数取中,得到中间数
int mid = arr[getmid(arr, low, high)];
while (left <= right) {
//注意是小于,如果是小于等于的话,常数列就会一直left移动,而right不移动,沦为n平方
while (arr[left] < mid) {
left++;
}
//同样注意是大于
while (arr[right] > mid) {
right--;
}
//这里要注意是小于或等于,以便于left和right直接跳到枢纽点的左右
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
//递归调用
//right走到了区间一的尾部
quickSort(arr, low, right);
//left走到了区间二的头部
quickSort(arr, left, high);
}
int main()
{
int n, i;
/*cin >> n;*/
/*for (i = 1; i <= n; i++)
{
cin >> a[i];
}*/
int a[100] = { 0,42 ,90,30,86,42,15,57,20 };
quickSort(a, 1, 8);
for (i = 1; i <= 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
最后是下载了测试点,然后看了博客,去找超时的原因,其实是完全有序 然后拿标准答案debug一下,终于发现了区别,就是常数列的时候他两个都移动,我只是一个移动,就退化成n平方了
如果我们不在交换完做移动的话,那>就得改成>=,这样才会移动,但就变成单指针移动了,还是退化成n平方了
https://www.luogu.com.cn/problem/P1177(依旧是模板题)
#include<cstdio>
#include<iostream>
using namespace std;
int a[100010];
//交换元素位置
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//三数取中
int getmid(int* array, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] <= array[right])
{
if (array[mid] < array[left])
return left;
else if (array[mid] > array[right])
return right;
else
return mid;
}
else
{
if (array[mid] < array[right])
return right;
else if (array[mid] > array[left])
return left;
else
return mid;
}
}
void quickSort_2(int rcd[], int low, int high) {
if (low >= high) {
return;
}
//调用三数取中,获取枢纽位置
int pivot=getmid(rcd,low,high);
//把枢纽值放到low位置(交换)
swap(&rcd[low],&rcd[pivot]);
//枢纽值就等于rcd[low]
int pivotVal = rcd[low];
//i用来遍历一趟区间
int left, right, i;
//直接从枢纽的下一位开始遍历区间
left = low, right = high, i = low + 1;
//遍历整个区间
while (i <= right) {
//若小于枢纽值
if (rcd[i] < pivotVal) {
//得放到前边,跟left交换
swap(&rcd[i], &rcd[left]);
//交换完,i换来了一个i前边的值,肯定比较过了,所以i++
i++;
//left换来了一个i原来位置的值,也比较过了,所以left++
left++;
}
//若大于枢纽值
else if(rcd[i]>pivotVal)
{
//得放到后边,跟right交换
swap(&rcd[i], &rcd[right]);
//right换来了一个i原来位置的值,也比较过了,所以right++
right--;
//i不动,因为换过来一个i后边的新的值,还没比较过
}
//等于的情况
else
{
i++;
}
}
quickSort_2(rcd, low, left - 1);
quickSort_2(rcd, right + 1, high);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
quickSort_2(a,0, n - 1);
for (int i = 0; i < n; i++) {
i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
}
}
这里我们先默认枢轴就是最左边的元素就好了,方便理解(实际情况再按上边代码取中后跟最左边交换即可)
用一个i去遍历这个区间,还需要一个left和一个right指针
具体看图中的文字说明
总结一下就是,如果该位置是一个已经跟枢纽值比较过了的值,或者换过来一个已经跟枢纽值比较过了的值(那就需要更新一下他的指针位置)
以上是脚本宝典为你收集整理的快速排序--洛谷卡TLE后最终我还是选择了三向切割全部内容,希望文章能够帮你解决快速排序--洛谷卡TLE后最终我还是选择了三向切割所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。