排序算法快速排序,快速排序归并排序
Yyds干货库存
快排(不稳定)是基于分而治之的思想。
期望：nlogn，最差
确定分界点
常见分界点：取左边界q[l]，中间值q[(1 r)/2]，右边界q[r]，取随机值。调整间隔
确保左边的数字小于或等于X，右边的数字大于或等于X.
递归处理左端和右端
左边顺序，右边顺序。重点是如何调整区间：
常见想法：
双数组方法(占用更多空间)
再打开两个数组，a []和b []。
然后，对于原数组Q，如果q[i] x，则将X存放在a[]中，否则存放在b[]中。
最后把a[]放入Q，再把b[]放入数。双指针法
采用双指针的思想。设置Sentinel X进行比较。
让I，j移动到中间，如果i x，继续移动，否则等待交换，如果j x，继续移动，否则等待交换。当我和J都在等待被交换的时候，交换ij，然后继续前进。直到我大于。
示例：快速排序给出一个长度为n的整数序列。
请使用快速排序将此系列从小到大排序。
并依次输出排序后的序列。
输入格式
输入两行，第一行包含整数n。
第二行包含n个整数(所有整数都在1的范围内)，代表整个系列。
输出格式
总共输出一行，其中包含N个整数，表示顺序良好的数字序列。
数据范围
1n100000
输入样本：
五
1 2 4 5输出样本：
1 3 4 5算法模板#包含bits/stdc。h
使用命名空间std
const int N=1e6 10
int q[N]；
void quick_sort(int q[]，int l，int r)
{
if (l=r)返回；
//如果数组中只有一个数字，直接返回
int x=q[l]，i=l - 1，j=r 1；
//随机取号。注意，I应该在左边界的左边，J应该在右边界的右边。就是因为采用了dowhile循环，打开会执行一次。
while (i j)
{
我愿意；while(q[I]x)；
做j-；while(q[j]x)；
if (i j) swap(q[i]，q[j])；
//双方都停了，就交换位置。
}
//递归调用函数，左右排序。同时注意，这里可能会有问题。
quick_sort(q，l，j)；
quick_sort(q，j 1，r)；
}
int main()
{
int n；
scanf(%d ，n)；
for(int I=0；I n；i ) scanf(%d ，q[I])；
quick_sort(q，0，n-1)；
for(int I=0；I n；i ) printf(%d ，q[I])；
返回0；
}对于模板中的
int x=q[l]，i=l - 1，j=r 1；
while (i j)
{
我愿意；while(q[I]x)；
做j-；while(q[j]x)；
if (i j) swap(q[i]，q[j])；
//假设[1，2] x=1，多轮交换后始终是[0，1]，无法走出死循环。
}
同时注意，这里可能会有问题。
quick_sort(q，l，j)；//如果这是J，X一定得不到q[r]
//quick_sort(q，l，I-1)；如果这是I，X一定得不到q[l]
//quick_sort(q，I，r)；
quick_sort(q，j 1，r)；详细注释
融合(稳定)思想：分而治之
时间复杂度：nlogn
以数组中间部分为界，分为左右。
确定截止点。mid=(1r)/2；递归地左右排序。二合一(重点)。合成一个有序数组。
合并的方法：双指针法。
因为合并排序是稳定的，所以当两个数相同时，可以将第一个数移到末尾。
示例：合并和排序得到一个长度为n的整数序列。
请使用合并排序将此系列从小到大排序。
并依次输出排序后的序列。
输入格式
输入两行，第一行包含整数。
第二行包含整数(所有整数都在1的范围内)，表示整个系列。
输出格式
总共输出一行，包含整数，表示有序序列。
数据范围
1n100000
输入样本：
五
1 2 4 5输出样本：
1 3 4 5算法模板#包含iostream
使用命名空间std
const int N=1e5 10
int a[N]，tmp[N]；
void merge_sort(int q[]，int l，int r)
{
if (l=r)返回；
int mid=l r 1；
//取中间位置
//左右两边分别合并排序，排序。
merge_sort(q，l，mid)，merge_sort(q，mid 1，r)；
//=====合并的过程=========
//k表示已经合并的数字，I是左半序列的起点，j是右半序列的起点。
int k=0，i=l，j=mid 1；
while (i=mid j=r)
//做个判断，每次都把小部分放在当前位置。
if(q[I]=q[j])tmp[k]=q[I]；
else tmp[k]=q[j]；
//如果左右两边没有完成循环，就粘贴到数组末尾
while(I=mid)tmp[k]=q[I]；
而(j=r)tmp[k]=q[j]；
//将其存储回Q数组中
for (i=l，j=0；I=r；I，j)q[I]=tmp[j]；
}
int main()
{
int n；
scanf(%d ，n)；
for(int I=0；I n；i ) scanf(%d ，a[I])；
merge_sort(a，0，n-1)；
for(int I=0；I n；i ) printf(%d ，a[I])；
返回0；
}来自的博主timerring的原创作品。如需转载，请联系作者，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。