分治之快速排序_分治排序

前言

分治算法是比较常见的，本文就讲一下分治在快排中的应用。

主要步骤

快速排序主要分为四个步骤：
1.确定分界点，定义一个x,比较常见的有nums[left],nums[right],nums[(left+right)/2],当然也可以是随机一点。
2.调整区间：
顾名思义，就是将数组以第一步确定的边界值划分为两部分，这也是整个算法最难的一步，这里我介绍一种较好的方法。
首先我们定义两个指针i,j;分别指向数组的两端。
先看左边的指针i，如果nums[i]<x,我们就执行i++;否则我们就保持i不变。同理j也是如此，如果nums[j]>x,我们就执行j--,直到满足nums[j]<=x,然后保持j不变。最后我们交换i,j指向的数值，同时i++,j--。重复此操作直至不满足i<j。
给出这部分代码，其中有个问题需要注意一下:

int i=l-1,j=r+1,x=nums[i+j>>1];
    while(i<j){
        while(nums[++i]<x);
        while(nums[--j]>x);
        if(i<j) swap(nums[i],nums[j]);
    }
1
2
3
4
5
6

为什么要定义i=l-1,j=r+1,可以类比一下vector.end(),vector.rbegin()因为我们发现每次在交换完两个指针指向的数时，两个指针都得向中间移动一次,所以我们干脆先移动，其中两个while语句我们就可以这么理解：

do i++;while(nums[i]<x);
do j--;while(nums[i]>x);
1
2

3.最后就是分别对两部分递归处理啦，这部分比较简单，我就直接放出代码了：

    quick_sort(nums,l,j);
    quick_sort(nums,j+1,r);daim
1
2

这里同样有个问题需要注意，我们递归函数中用j做参数的时候，我们第一步确定的边界值就不能是nums[r],这是为什么呢。假设我们待排序的数组为[1，2],边界值为nums[1]=2,初始时i=-1，j=2经过循环后i=1,j=1;进入递归，quick_sort(nums,0,1)和quick_sort(nums,2,1),可以看出第二个函数直接跳出，因为不满足l<r,而第一个函数和原函数相同，由此进入死循环，故不可取。
同样当我们递归函数为

    quick_sort(nums,l,i-1);
    quick_sort(nums,i,r);
1
2

我们第一步边界值就不能为nums[l] 。
最后给上完整代码：

#include<iostream>
using namespace std;
int n;
const int N=1e6+10;
int arr[N];
void quick_sort(int nums[],int l,int r){
    if(l>=r) return;
    int i=l-1,j=r+1,x=nums[i+j>>1];//等同于num[(i+j)/2]，但是位运算计算机处理更快
    while(i<j){
        while(nums[++i]<x);
        while(nums[--j]>x);
        if(i<j) swap(nums[i],nums[j]);
    }
    quick_sort(nums,l,j);
    quick_sort(nums,j+1,r);
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&arr[i]);
    quick_sort(arr,0,n-1);
    for(int i=0;i<n;i++)cout<<arr[i]<<' ';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

另外附上python代码：

def quick_sort(arr:list,l:int,r:int)->None:
    if l>=r:return
    i,j,x=l-1,r+1,arr[l+r>>1]
    while i<j:
        i+=1
        while arr[i]<x:i+=1
        j-=1
        while arr[j]>x:j-=1
        if i<j: arr[i],arr[j]=arr[j],arr[i]
    quick_sort(arr,l,j)
    quick_sort(arr,j+1,r)

n=int(input())
nums=list(map(int,input().split()))
quick_sort(nums,0,n-1)
for i in nums:
    print(i,'',end='')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17