栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

排序算法之快速排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

排序算法之快速排序

排序算法之快速排序

今天面试被问到了这个问题,自己回答的不是很好,因此特意来记录一下,巩固学习。

概念

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

基本思想
  1. 从数列中找出一个数作为基准数x;
  2. 分区过程,大于等于x的放在其右边,小于等于x的放在其左边;
  3. 再重新划分左右区间,重复第二步,直到只剩一个数为止;
具体实现

例如数组s {5,1,7,8,4}
i = 0,j =4 (代表左右边界索引)
int x = s[0] (选取索引0为基准数)

此时x=s[0],可以理解为索引0的位置出现了一个坑(需要填补),
然后我们从右往左(j—i)的方向进行遍历,找到第一个比基准值小的数(4,s[4]),
然后将s[4]填补到这个坑里,s[0]==s[4],且i++,此时由于s[4]被拿来填补了,所以s[4]这个位置变成了坑,因此我们需要继续填坑,
此时我们再从最左边(i—j)遍历,找到第一个比基准值大的数(7,s[2]),然后讲这个数填补到刚才的坑里,s[4]==s[2],且j–,
重复上述步骤,最后的坑就是我们的基准值,因此把x填入其中就可以了。

代码实现(java)
	void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                j--;  
            if(i < j) 
                s[i++] = s[j];
            
            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用 
        quick_sort(s, i + 1, r);
    }
}

效率:O(N*logN)
参考:https://www.runoob.com/w3cnote/quick-sort.html

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/969866.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号