快速排序

快速排序思路：

快速排序时间最好情况下的复杂度为 $O(\log_2 n)$ ，待排序序列越无序，本算法效率越高。最坏情况下的时间复杂度为 $O(n^2)$ ，平均复杂度为$O(\log_2 n)$，

对一个序列A[1]、A[2]、… 、A[n]，调整序列中元素的位置，一趟排序后，使得A[1]的左侧所有元素都不超过A[1]、右侧所有元素都大于A[1].
然后，以A[1]位置分割左右两部分递归快速排序

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cmath>
using namespace std;

//一趟关键元素（主原）排序
int partition(int A[], int left, int right){
    int temp = A[left];
    while(left < right){
        while(left < right && A[right] > temp) right--;
        A[left] = A[right];
        while(left < right && A[left] <= temp ) left++;
        A[right] = A[left];
    }
    A[left] = temp;
    return left;
}

//优化主原没有把区间[left,right]分成两个近似的子区间:随机的选择主原
int randPartition(int A[], int left, int right){
    int randNum = (round(1.0*rand()/RAND_MAX*(right - left) + left));
    printf("randNum: %d\n",randNum);
    swap(A[randNum],A[left]);
    int temp = A[left];
    while(left < right){
        while(left < right && A[right] > temp) right--;
        A[left] = A[right];
        while(left < right && A[left] <= temp) left++;
        A[right] = A[left]; 
    }
    A[left] = temp;
    return left;
}

void quickSort(int A[],int left, int right){
    if(left < right){
        //int pos = partition(A,left,right);
        int pos = randPartition(A,left,right);
        quickSort(A,left,pos - 1);
        quickSort(A,pos + 1,right);
    }
}

int main(){
    int A[] = {35,18,16,72,24,65,12,88,46,28,100,66,866};
    quickSort(A,0,9);
    for(int i = 0; i < 10; i++){
        printf("%d\n",A[i]);
    }
    return 0;
}

欢迎访问 chenyawei 的博客, 若有问题或者有好的建议欢迎留言，笔者看到之后会及时回复。评论点赞需要github账号登录，如果没有账号的话请点击 github 注册，谢谢 !

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

快速排序思路：

FEATURED TAGS

FRIENDS