我在北京找工作(二):java实现算法<1> 冒泡排序+直接选择排序

工作、工作、找工作。经过1个多星期的思想斗争还是决定了找JAVA方面的工作,因为好像能比PHP的工资高点。呵呵 :-)  (其实我这是笑脸,什么QQ输入法,模拟表情都没有,忒不人性化了。)

言归正传,既然决定了。就得抓紧时间回顾一下之前的知识,毕竟是我找工作而不是工作找我哈……

排序显然是笔试、面试过程中必定需要掌握的东西。

假定所有排序默认为从小到大排序

1、冒泡排序

设数组长度为N。

第一步:比较相邻的两个元素的大小,如果前面的元素大于后面的元素的值,就将这两个元素的位子进行交换。
第二步:对数组的第0个元素(0是下标)到第N-1个元素 使用第一步的方法顺序进行一次遍历后,最大的一个元素也就像大泡泡会更容易浮出水面一样,“冒”到了最上面。
第三步:对区间范围进行缩减操作,即N=N-1,如果N不为0就重复第二步操作,否则排序就已经完成。

下面按照我们所说的步骤 可以很容易的写出下面代码:

public void bubbleSort(int[] arr){
//外层for循环定义最大数组搜索区间
for(int i=0;i<arr.length;i++) {
//内层for循环定义当前一轮所需要搜索的元素区间,而且从1开始与前一个元素比较,到已经排过序的位子结束
for(int j=1;j<arr.length-i;j++) {
if(arr[j-1]>arr[j]) {
//如果前面一个元素大于当前元素,则对两个元素的位子进行交换
int temp = arr[j-1] ;
arr[j-1] = arr[j] ;
arr[j] = temp ;
}
}//end of for(j)
}//end of for(i)
}

代码中的交换两个元素,其实也是一个小小小考点,如果是写一个swap(int  num1,int num2)方法,则据我所知java全都是值传递,根本就达不到预期的结果。到底还是可以传递整个数组,再传递要交换的两个下标值,可以实现写出交换的swap方法,但是未免有些绕弯的感觉,所以最好还是直接在排序function中直接交换。

另外,就算是交换两个元素的值,也还是有多种方法的!!

最常见的就是像我所写的代码这样:新建一个中间临时变量temp,用于周转,3步可以简单实现交换。

int temp = num1;
num1= num2;
num2= temp ;

还有一种方法,不需要新建中间变量,可能会比第一种稍微有点绕,不过也是很简单就能理解的。如果觉得不太好记住,就画个图吧,保证你能够很快的记住并使用上的。

num1=num1+num2;
num2=num1-num2;
num1=num1-num2;

其他的,还有很多小方法。各种各样的都能够达到这样交换的目的。自己去尝试吧~~~  (用^符号等等都行@!)

总结:再值得一提的是,冒泡排序想哪个看过代码,知道原理的人都应该知道,它的效率是非常低的。

还有2种优化的方法,第一个就是在内循环开始的时候设置一个标志位,如果某一次内循环没有进行一次交换,则说明排序完成,就不需要完整的遍历完2层for循环才结束了。

第二个就是设置一个记录器变量,记录上一次内循环时,最后进行交换的元素的下标,这个记录器变量的意义是,某一次循环的最后一次进行元素交换的位子说明,该位子之后的元素肯定是有序的。下一轮就只需要对记录器变量标识的下标的前段进行排序就行了,以此类推,应该可以减少一些不必要的操作吧。

代码就先不给了,一定要自己实现出来,明白了原理的代码才是自己的代码。千万不可故作装懂,逞一时之快!

2、直接选择排序

数组长度依然为N。

没有原理,我说个毛线!别的不说,先上原理:将数组分为有序区和无序区,在无序区中选择一个最小的元素直接放在有序区的最后。直到无序区没有一个元素或者只剩下一个元素。

第一步:初始化时,默认数组全为无序区。
第二步:在无序区中选取一个值最小的元素,将其与有序区的后一个元素的位子进行交换。交换之后,有序区就像后扩展了一个。
第三步:一直重复第二步的操作,直到无序区元素个数为0或者为1,排序完成。

小二,给客官上代码喽!!!

//直接选择排序算法
public void selectSort(int[] arr) {
int minIndex = -1 ;
for(int i=0;i<arr.length;i++) {
minIndex = i;//默认最小元素的小标为当前无需区间的第一个元素
for(int j=i+1;j<arr.length;j++) {
//在寻找过程中,只记录下标
if(arr[j]<arr[minIndex]) {
minIndex = j ;
}
}
//内循环完毕后即可进行交换,交换小标为i和minIndex的元素
int temp = arr[i] ;
arr[i] = arr[minIndex] ;
arr[minIndex] = temp ;
}
}

重新回到前面的交换两个元素的问题。代码是这样的:

num1=num1+num2;
num2=num1-num2;
num1=num1-num2;

前面 所说的第二种方法还是有些许BUG的,可能是因为代码在虚拟机里的运行顺序问题,还是会导致BUG的产生。读者们可以自己去实验一下。我们人为的原理理论是成立的!但是  代码在机器里的运行顺序不一样就会导致问题了,   这就叫同步的问题了。。。。

提供第三种交换方法:

if(num1 != num2) {
num1 ^= num2;
num2 ^= num1;
num1 ^= num2;
}
采用位运算的方法也可以实现这简单的交换问题。 有人问为什么要加个判断,当两个数不相等的时候才进行位运算。

这个熟悉位运算法则的童鞋都应该明白的!相等或相同的两个数位运算可是为0的。这不就是隐患么,而且,退一万步来说,相等了干嘛还换位子啊。神经呀!嫌运行太快?呵呵.............    0.0

今天就写到这里吧,每天都要不断的提高自己。下次整一点面试题来分析分析~~~  顺便再讲讲其他排序算法。尤其是直接插入排序和直接选择排序的相同和不同。

记住一点:只有懂原理的程序员才是好程序员,而且也更轻松的说。不懂,就要死记硬背。何必呢~~  你说是吧?  何必呢.......必呢..........呢..........

上一篇:校招有感:计算机专业毕业生如何找工作(Java方向)


下一篇:js 里面的键盘事件对应的键码