title: quick_sort and merge_sort
toc: true
date: 2022-12-10 22:38:21
tags: 排序
categories: 算法
简介：简单记录一下快速排序与归并排序的实C++实现。
1.快速排序
代码：
#include<iostream>
using namespace std;
int n;
const int N=1e6+10;
int arr[N];
void quickSort(int q[],int l,int r){//传入待排数组和左右边界
if(l>=r) return;
//排除空数组和单个数字
int i=l-1,j=r+1,x=q[(l+r)/2];
//设定双指针的位置，启动位置距离边界为1,x为分界点
while(i<j){
do i++;while (q[i]<x);
//比较数字与分界点的大小，当i指针运行到大于分界点的数字时停下
do j--;while (q[j]>x);
//比较数字与分界点的大小，当j指针运行到小于分界点的数字时停下
if(i<j) swap(q[i],q[j]);
//交换i和j所指的不满足分界条件的数字，使其仍然满足i左边的全小于x，j右边的全大于x
}
quickSort(q,l,j);
quickSort(q,j+1,r);
//将数组分为l到j和j+1到r两部分，递归处理两边，分治的思想
//注意：当用i指针划分时，应取l到i-1和i-1到r，此时x不能取q[l]，否则会发生死循环，当使用j时同理，不能取q[r]
}
int main(){
scanf("%d",&n);
//读入数组长度
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
//正序读入数组
}
quickSort(arr,0,n-1);
//调用快排函数
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
//打印排序后的数组
}
return 0;
}
2.归并排序
代码：
#include<iostream>
using namespace std;
int n;
const int N=1e6+10;
int arr[N],temp[N];
void merge_sort(int q[],int l,int r){
if(l>=r) return;
int mid=l+r>>1;
//“>>”为位运算，表示左值除以2的右值次方
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
//归并排序先递归处理分界点左右两部分
int k=0,i=l,j=mid+1;//this i="L",j=mid+"1"
//设定左右部分的起点
while(i<=mid&&j<=r){
if(q[i]<=q[j]) temp[k++]=q[i++];
else temp[k++]=q[j++];
//temp数组中先存入比较中的小值，经过递归处理后，小值都将位于左侧，升序排列
}
while(i<=mid) temp[k++]=q[i++];
//如果比较完成后，左部分仍然有剩余数组，将其直接接到temp数组后(经过前面递归处理部分，内部已经有序，剩下的数组必然为较大部分，排列在后边)
while(j<=r) temp[k++]=q[j++];
//处理右部分多余的情况
for(int i=l,j=0;i<=r;i++,j++) q[i]=temp[j];//this i="L"
//将临时数组中的数存入原数组
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
merge_sort(arr,0,n-1);
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
return 0;
}
3.时空复杂度与稳定性
快速排序是不稳定的，时间复杂度为O（nlogn）到O（n平方）。
归并排序是稳定的，时间复杂度为O（nlogn）。
注意:稳定是值排序前后，相同数字的位置是否发生变化。
快速排序在一趟排序中将数字分割成为独立的两部分，左边一部分小于轴值，右边一部分大于轴值，轴值的选择理论上可以选择数组中的任何一个数组，我们在这里考虑选择第一个数字。然后对两部分序列重复进行上述操作，快速排序可以用递归来完成，其时间复杂度：最好情况O(nlogn)——Partition函数每次恰好能均分序列，其递归树的深度就为.log2n.+1（.x.表示不大于x的最大整数），即仅需递归log2n次； 最坏情况O（n^2）,每次划分只能将序列分为一个元素与其他元素两部分，这时的快速排序退化为冒泡排序，如果用数画出来，得到的将会是一棵单斜树，也就是说所有所有的节点只有左（右）节点的树；平均时间复杂度O(nlogn)。