首页 > 编程语言 > 详细

快速排序(C语言实现)

时间:2022-05-27 23:20:18      阅读:23      评论:0      收藏:0      [点我收藏+]

时间复杂度:O(nlogn)
空间复杂度:O(logn)

思路:

  任意选取一个数作为基准数,从数组两端同时遍历,左边寻找比基准数大的,右边寻找比基准数小的,将这两个数交换位置,当左右两端符合上面条件的数都交换完后再将基准数放在中间,基准数此时所在的位置就是数组排序后应该在的位置。一轮结束后再通过递归将左半边和右半边的基准数分别归位。  

具体实现如下

void quicksort(int* a, int left, int right) {
	if(left>=right)//判断是否为空数组
            return;
        /*
            i从左边寻找 j从右边寻找 
            t为交换两个变量时的临时变量
            temp为存储基准数的变量
        */
	int i,j,t,temp;
	temp = a[left];//temp为基准数
	i = left;
	j = right;
        
        //把所有比基准数小的放左边,大的放右边
	while(i!=j) {
            while(a[j]>=temp && i<j)//从右边开始找比基准数小的
                j--;
            while(a[i]<=temp && i<j)//从左边开始找比基准数大的
                i++;

            if(i<j) {
		t = a[i];
		a[i] = a[j];
		a[j] = t;
            }
	}

	/*将最后找到的比基准数小的那个和基准数交换位置*/
	a[left] = a[i];//a[i]和a[j] 都可以 i==j
	a[i] = temp;
        //此时成功的将一个数放到它该在的位置了
	quicksort(a,left,i-1);//再处理左边
	quicksort(a,i+1,right);//处理右边
}

细节实现:

目标是让左半边全为小于等于基准数的,右半边全为大于等于基准数的
    让i和j哨兵分别从左右两端开始
        j找比基准数小的值 大于等于的一律不是,所以  while条件为 a[j]>=temp  继续循环去找
        i找比基准数大的值  符合条件的保留,不符合条件的交换
        与基准数相同的放在原位即可,一轮只找一个数,只要左边的没基准数大,右边的都没基准数小就找对了
        找到后交换位置
当最后一轮找到的数为此情况时
	         6      8   2
	交换后: 6      2   8
	此时该轮已全部交换完成 i = x ;j = x+1
        i!=j 循环继续
	就不用再找与基准数比较的数了,需要将2和6的位置交换,故需要从右边先找,j先寻找
        此时i和j相遇,且都为2的下标,就不用再循环了,故循环条件里需加上 i < j
	
如果情况为 
                6   2  8  8
                    i     j
	        6   2  3  8
                    i     j
			j都会找到那个比基准数小的,最差也是找到i的位置上
                           
如果基准数为最右边的值,这里需要从左边开始找

快速排序(C语言实现)

原文:https://www.cnblogs.com/haiziche/p/15359132.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!