文档章节

快速排序

cjavaer
 cjavaer
发布于 2017/08/31 19:26
字数 428
阅读 1
收藏 0

        快排对于不管是校招,还是社招,都会面试官非常喜欢考的一道题目,而且是一道要求在10分钟写出的一道算法题。下面我们就讲讲“快速排序”。

 

1、快排的思路如下:

a)、添补法

b)、分而治之

 

1、在一个数组中,在数组中选出一个基值,一般如果从小到大的排序,一般会选数组的第一个值arr[low]作为基值,然后从这个数组的其它元素中获取元素与这个基值比较,比它小的放左边,比它大的放右边。用一个temp=arr[low]记住这个值,这样的话,用会一直空出这个值,这样的话,就比较这个值,符合条件的话,就交换这两个数组节点的值,从两侧依次查找。

2、通过依次排序可以得到左边都是比Temp小的,右边都是比temp大的,以此递归,可得到排序结果。

 

        

 

 

2、代码

    

private static void sort(int[] arr,int low,int high){
        //校验参数略掉
        
        int start = low;
        int end = high;
        int temp = arr[start];
        
        while(end > start){
            
            while(end > start && temp <= arr[end])
                end--;
            if(end > start){//说明上面是temp <= arr[end]条件不符合
                arr[end] = arr[start]^arr[end];
                arr[start] = arr[start]^arr[end];
                arr[end] = arr[start]^arr[end];
            }
            
            while(end > start && temp >= arr[start])
                start++;
            if(end > start){//说明上面是temp >= arr[end]条件不符合
                arr[end] = arr[start]^arr[end];
                arr[start] = arr[start]^arr[end];
                arr[end] = arr[start]^arr[end];
            }
        }
        arr[start] = temp;
        //达到这里,start=end,这里就是temp放的位置
        //循环结束,代表temp的值前后都是有一定的顺序
        if(start > low){
            sort(arr,low,start-1);
        }
        
        if(start < high){
            sort(arr,start+1,high);
        }
  }

测试:

 

 

 

© 著作权归作者所有

cjavaer
粉丝 0
博文 38
码字总数 15232
作品 0
朝阳
程序员
私信 提问

暂无文章

python学习10.04:Python list列表使用技巧及注意事项

前面章节介绍了很多关于 list 列表的操作函数,细心的读者可能会发现,有很多操作函数的功能非常相似。例如,增加元素功能的函数有 append() 和 extend(),删除元素功能的有 clear()、 remo...

太空堡垒185
26分钟前
4
0
新手插画学习的方法?教你如何自学?

插画学习的方法?教你如何自学? 从小喜欢画一些漫画头像随笔画,但是其实没有基础。个人偏好小清新手绘风的插画(如下图),每每看到都希望自己能画出这样的作品。 我其实很想说画这种美术功...

huihuajiaocheng
31分钟前
4
0
面试题

1、实现clone();

gtandsn
42分钟前
5
0
CentOS 7 部署 tesseract-ocr

官方地址 github yum-config-manager --add-repo https://download.opensuse.org/repositories/home:/Alexander_Pozdnyakov/CentOS_7/ 若提示 yum-config-manager: command not found 执行以......

阿白
43分钟前
3
0
JAVA比较器中comparator的使用

一个专用的比较器Comparator Comparator是一个专用的比较器,当一个不支持自比较或者自比较函数不能满足要求时,可写一个比较器来完成两个对象之间大小的比较。Comparator体现了一种策略模式...

daxiongdi
43分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部