排序算法之快速排序、归并排序
目录
快速排序归并排序的意义
快速排序
思维步骤
具体思想
测试样例解释
代码实现
归并排序
思维步骤
具体思想
测试样例解释
代码实现
快速排序归并排序的意义
快速排序和归并排序不仅仅是一种方法，更重要的是其作为一种算法而节省时间，在处理小型数据时，用普遍学习的排序方法如c语言中的方法：冒泡排序法、 选择排序法、插入排序法等等时间都差不多，但就时间复杂度上和得出结果所用时间来说，快速排序和归并排序无异于是优于这些普通的方法的。这也就是快速排序和归并排序不仅仅是一种思想、一种方法，更是一种快速解决问题的算法。
快速排序
基于————分治思想
思维步骤
1.寻找分界点x，可以为q[l](最左端元素)q[r](最右端元素)q[l+r>>1](中间元素)，为了保险起见，我们一般使用中间元素作为分界点也就是q[l+r>>1]
2.调整区间，对于分界点左边的元素全部调整为小于等于x，对于分界点右边的元素全部调整为大于等于x
3.递归处理左右两端
具体思想
对于调整区间的操作，可以使用双指针操作，为了避免指针的越界，首指针i指向首地址的前一个元素，尾指针j指向末地址的后一个地址，头指针从前往后扫，尾指针搜后往前扫，当头指针尾指针相遇时即结束调整区间，头指针在从前往后扫的同时，一旦遇到大于等于分界点x的元素即停止，尾指针在从后往前扫的同时，一旦遇到小于等于分界点x的元素即停止，若两指针在未交错之前都停止，那么swap交换而指针所指向的元素，而后指针继续扫描数组进行调整区间
递归处理即为先对于左半部分的区间进行处理之后再对于右半部分的区间进行处理，具体实现排序可以理解为一个做饺子皮的过程，首先我们先将一团面团揉成一个长条(即整个数组未处理的长度)，然后不断进行二分的过程，成为一个个小的独立元素个体
测试样例解释
5
3 2 8 1 6我们用彩色笔圈住分界点x，蓝色指针为头指针，橙色指针为尾指针
在首次进行快排调整区间之后，我们先对[l,j]区间进行快排也就是左区间，而后在对于[j+1,r]右区间进行处理，显而易见的是，j+1是等于r的，所以进行仅仅进行函数quick_sort(q,l,j);
在对区间进行处理之后，quick_sort(q,l,j)函数运行对于1、2的顺序进行调整，显然其是符合要求的，因此1、2的顺序也就不必再动，我们仅仅看quick_sort(q,j+1,r)函数的运行即可，也就是对于6、3的区间进行调整
最后的结果也就是我们想要的即升序排列的答案1、2、3、6、8
代码实现
#include <iostream>
using namespace std;
const int N = 100000+10;
int q[N];
void quick_sort(int q[],int l,int r)
{
if(l>=r)return;
int x=q[l+r>>1],i=l-1,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]);
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i ++ )cin>>q[i];
quick_sort(q,0,n-1);
for(int i = 0;i < n;i ++ )cout<<q[i]<<' ';
return 0;
}归并排序
基于————分治思想
思维步骤
1.确定分界点mid
2.对于划分好的左右区间进行排序
3.汇入总的原数组当中
具体思想
将区间不断二分，
测试样例解释
5
3 2 8 1 6我们用彩笔来表示mid，将数组分为[l,mid]与[mid+1,r]两部分
再二分
再二分
由此可见我们最终得到了所有的单个元素，根据颜色：
灰色为第一批次二分，结果为：[3 2 8]与[1 6]
蓝色为第二批次二分，结果为：[3 2]和[8]、[1]和[6]
黄色为第三批次二分，结果为：[3]和[2]
而后我们依次对于结果进行回溯处理
第三批次二分回溯
第二批次二分回溯
第一批次二分回溯
那么具体回溯的结果是什么呢？拿第一批次回溯来举例，回溯的本质就是将左右部分展开并列排放，哪儿个元素小取哪儿一个放入tep数组，直至某一个部分所有元素被取完，当然如果出现两部分中的某一元素相同，我们就优先取左部分的元素，这样就保证了并列排序算法的稳定性。那么当某一部分被取完时，必有另外一部分未取完，直接将未取完的部分推入tep数组即可，最后将tep数组复刻进q数组也就是原数组中就ok了
用蓝色表示i指针，用橙色表示j指针
开始复刻
代码实现
#include <iostream>
using namespace std;
const int N = 10000+10;
int q[N],tep[N];
void merge_sort(int q[],int l,int r)
{
if(l>=r)return;
int mid=l+r>>1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int k = 0,i = l,j = mid+1;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j])tep[k++]=q[i++];
else tep[k++]=q[j++];
}
while(i<=mid)tep[k++]=q[i++];
while(j<=r)tep[k++]=q[j++];
for(int i = l,j = 0;i <= r;i ++ ,j ++ )q[i]=tep[j];
}
int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i ++ )cin>>q[i];
merge_sort(q,0,n-1);
for(int i = 0;i < n;i ++ )cout<<q[i]<<' ';
return 0;
}