工作、工作、找工作。经过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实现( 冒泡排序+快速排序直接插入排序+希尔排序+选择排序+归并排序+基数排序)
C_算法源码(冒泡排序+基数排序+插入排序+快速排序+归并排序 C_算法源码(冒泡排序+基数排序+插入排序+快速排序+归并排序 C_算法源码(冒泡排序+基数排序+插入排序+快速排序+归并排序 C_算法源码(冒泡排序+基数排序+...
* 基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序 2冒泡排序 * 基本思想:在要排序...
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
sort 排序算法实现_支持插值排序+选择排序+冒泡排序_sort
这里提供了两种常见的排序算法实现:冒泡排序和选择排序。 冒泡排序(Bubble Sort) 是一种基本的排序算法,它通过多次遍历数组,比较相邻元素的大小并交换它们,从而使最大(或最小)的元素逐渐移动到数组的最后。...
* 冒泡排序: * 每次在无序队列里将相邻两个数一次进行比较, * 将小数调到前面,逐次比较,直至将最大的数移到 * 最后。将剩下的N-1个数继续比较,将次大数移至 * 倒数第二位。
算法(冒泡,选择,插入,数组排序) package Teacher; import java.io.*; import java.util.Scanner; public class Tset { public static void main(String args[]) throws IOException { // 需要排序的数组,...
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
java算法,快速排序、冒泡排序、选择排序 快速排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51822361 冒泡排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51819045
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
用C编写的冒泡排序算法:#include<stdio.h> void main() { int i=0,j=0,t; int a[10]; for(i=0;i<10;i++) scanf("%d",&a[i]); for(i=0;i<9;i++) for(j=0;j<9-i;j++) if(a[j]>a[j+1]) {t=a[j]; a[j]=a[j+1]; ...
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
但是内层循环的结束条件i<array.length-1-i,这里一定要-1,原因很简单,因为在内层循环中分表使用i和i+1作为索引获取数组的元素,就要保证i和i+1都不能超出数组的索引范围,即i<array.length && i+1<array.length 推导出...
1冒泡排序 2改进的冒泡排序,在一次冒泡的过程中,如果没有发生交换,则已经有序 3进一步改进的冒泡排序,如果在某次冒泡过程中,最后一次进行交换的位置为flag,则表示flag之后的序列已经有序,那么下一次冒泡就...
Verilog/C++实现排序算法:Verilog/C++实现排序算法:冒泡排序、选择排序、并行全比较排序、串行全比较排序。
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
hadoop k-means算法实现java工程的打包类,可直接在terminal中运行,运行命令为: $HADOOP_HOME/bin/hadoop jar ClusterDemo.jar main.Cluster 然后直接确定就可以看到提示的运行参数或者参考下面: +"<input> ...