快速排序(分治)-创新互联
算法基础—快速排序日常分享:岁聿云暮,日月其除,前路未远,步履不停。
为昭阳等地区用户提供了全套网页设计制作服务,及昭阳网站建设行业解决方案。主营业务为成都网站设计、网站建设、昭阳网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
- 前言
- 一、快速排序的时间复杂度
- 二、快速排序实现
- 总结
- 三、代码
前言
快速排序就是先找一个关键字,然后通过一趟排序,把大于关键字的位于一侧,小于关键字的位于一侧,然后对两侧在进行排序。
一、快速排序的时间复杂度二、快速排序实现快速排序最优情况下时间复杂度为:O( nlgn )
最优情况下空间复杂度为: O(logn)
怎么去计算这个复杂度在这里就不多说了。
1.首先我们应该输入数组的值
const int N = 1e6 + 10;//1e6 就是1*10的6次方
int q[N];
int n;
cin >>n;
for (int i = 0; i< n; i++)
{cin >>q[i];
}
也可以用scanf,scanf和printf是要比cin,cout快的,但是不要忘记用&符号。
2.确定函数的分界点
确定分界点之前,不要忘记考虑一种情况,左边界==有边界的时候,是不是应该直接退出函数??
if (l >= r)
{return;
}
左边界可不能>=有边界。
int x = q[l + r >>1];
这个不加括号是因为➕的优先级要比>>的优先级要高。
在这里我们以中间值为分界点,也可以选取q[0]当分解点。当然,最好选取中间值,当你选两边的值的时候,再做一些题的时候,可能会出现超时的情况。
这样确定了分界点之后,就可以进行下一步了。
3.在这里有两个指针,i和j,q[i]小于x,就++,直到出现大于x的情况,q[j]大于x,j就–,直到遇到小于x的情况。
代码实现如下:
int x = q[l + r >>1];
int i = l - 1;
int j = r + 1;
while (i< j)
{do
{ i++;
} while (q[i]< x);
do
{ j--;
} while (q[j] >x);
if (i< j)
{ swap(q[i], q[j]);
}
}
这里为什么要用l-1和r+1呢?因为这里我用的是do—while循环,先执行的i++,在执行的判断条件,大家也可以改成while循环。
可以把数组以中间值,分开,然后每个指针进行移动+判断,直到两个指针都不满足循环条件,进入交换。
就是这样交换的,如果你的学的编程语言没有swap这样的函数,那么我们也可以自己实现一下
if (i< j)
{int tmp = q[i];
q[i] = q[j];
q[j] = tmp;
}
这个代码够简单了,在这里不多说了。
4.最重要的一点,边界问题
代码如下(示例):
QuickSort(q, l, j);
QuickSort(q, j + 1, r);
也可以用其他方法,在这里就不多介绍了。
总结为什么要学快速排序呢,明明有库函数,如C++(sort),C语言(qsort)等等,
学快排,学的是思想,正如一句话:算法学的好,工作不愁找。哈哈
#includeusing namespace std;
const int N = 1e6 + 10;
int q[N];
int n;
void QuickSort(int q[], int l, int r)
{if (l >= r)
{return;
}
int x = q[l + r >>1];
int i = l - 1;
int j = r + 1;
while (i< j)
{do
{ i++;
} while (q[i]< x);
do
{ j--;
} while (q[j] >x);
//if (i< j)
//{// swap(q[i], q[j]);
//}
if (i< j)
{ int tmp = q[i];
q[i] = q[j];
q[j] = tmp;
}
}
QuickSort(q, l, j);
QuickSort(q, j + 1, r);
}
int main()
{cin >>n;
for (int i = 0; i< n; i++)
{cin >>q[i];
}
QuickSort(q, 0, n - 1);
for (int i = 0; i< n; i++)
{cout<< q[i]<< ' ';
}
return 0;
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文题目:快速排序(分治)-创新互联
链接地址:http://scyanting.com/article/cogodo.html