一天一个算法之快速排序

发表于

排序算法

快速排序

快速排序基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

时间复杂度：平均时间复杂度O(nlogn) 最差情况下会变为O(n2)

基本思路如下:

1.设置分界值,通过该分界值将数组分为两部分。

2.将大于等于分界值数据集中在数组的右边，小于等于分界值数据集中在数组的左边。

3.递归：将左边和右边的数据分别独立排序，对于左侧数组再取一次分界点，又将分为两个部分，右侧数组数据也做一样的处理，通过递归排好左侧 再排右侧。

代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include<iostream>
using namespace std;
int q[N];
const int N=1e5+10;
void quicksort(int q[],int l,int r){
    //若数组就一个数 直接返回数值
    if(l>=r>) return;
    //这里写l==r也可以 >=也包含==的情况
    //选取分界点
    int x=q[l+r>>1];
    //l+r>>1是选中间的点
    int 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);//递归排序左右
    }
}

cout<<”over~”<< endl;