注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

轻松度过每一天

真的猛士敢于直面惨淡的人生,敢于正视淋漓的鲜血,这是怎样的哀痛者和幸福者!!

 
 
 

日志

 
 
关于我

When you are young, you may want several love experiences. But as timegoes on, you will realize that if you really love someone, the wholelife will not be enough. You need time to know, to forgive and to love.All this needs a very big mind.

网易考拉推荐

快速排序理解思路,心得  

2015-01-07 11:21:14|  分类: 艺术、算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
先贴上快速排序的代码:

public static int[] quickSort(int le, int ri, int[] v) {

int l = le;//先把left和right赋 l 和 r ,而left和right的值始终是不变的
int r = ri;
int base = v[l];
if (l >= r)
return null;
while(l != r){
while(l<r&&v[r]>=base)
r--;
if(l<r)
v[l] = v[r];
while(l<r&&v[l]<=base)
l++;
if(l<r)
v[r] = v[l];
}
v[l] = base;

quickSort(le, l-1, v);//递归左边
quickSort(l+1, ri, v);//递归右边
return v;
}

何为快速排序:在数组中找一个基准base,将数组中的其它元素与之相比较,较大的放在base的右边,较小的放在左边,如此递归,就可以快速的将这个数组进行排序。这个base,一般选前中后的一个数。
快速排序,需要base,还需要两个类似指针作用的left和right;
有一数组a[] = {4,2,2,3,6,4,9},我这里把基准选择为base = a[0];  当然left = a[0],right = [a.length - 1];
1.首先从右边,right开始遍历while(l<r&&v[r]>=base),right--直到找到有小于base的数,将该数给left所在位置v[l] = v[r];
2.下面第二不,从left开始遍历while(l<r&&v[l]<=base),left++直到找到大于base的数,将该数给right所在位置v[r] = v[l];
3.如果此时left和right仍然不相等,重复1和2,直到相等
4.将base的值给left或right所在位置(因为此时left和right在同一位置)。这就完成了一次
5.进行递归操作,递归左边和右边。
来看一看a[]数组。
初始a[] = {4,2,2,3,6,4,9}
赋值:left = 0;base = a[left];right = 6;             left,right分别指向a[0],a[6]
遍历right:9>4,right--(right指向a[5])............直到right指向a[3].....3<4.....把3赋给left......数组a[] = {3,2,2,3,6,4,9}
遍历left:此时left = 0 -> a[0] = 3;  3<4........left++,.....2<4.....left++.......2<4.......left++......注意此时left = 3->a[3],   left == right. 
插入base:a[left] = base;  a[] = {3,2,2,4,6,4,9},这就完成一次操作,之后遍历4的左边(3,2,2)和右边(6,4,9)

左边:3,2,2.....2,2,2......2,2,3
再遍历3的左边:2,2

右边:6,4,9 ......4,4,9.....4,6,9
再遍历6的左边后右边,但两边都只有1个数,故不变

结果2,2,3,4,4,6,9

  评论这张
 
阅读(80)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017