java 冒泡排序，选择排序，插入排序,希尔排序
今天刚学习了点java数据结构，一开始就看到的排序的问题，就往下看了，java基本的排序方法有三种:冒泡，选择，插入。
以前一直认为选择排序就是冒泡排序。看了书中的解释，明白了冒泡排序和选择排序不能混为一谈。
经过消化，我稍微懂了它们的原理。
冒泡排序是取一个数据a，然后和这个数据右边的数据b进行比较，如果a比b大，a就往右移动，也就是变到b的右边（程序中可通过交换实现）。写两个循环，代码如下
?
?
//冒泡排序public class BubbleSort{private static int[] total={2,8,1,9,4,11,3,7,5,6,10};public static void main(String[] args){long start=System.currentTimeMillis();//此处out可>0，但没必要，三个数据只用一次冒泡排序即可得出结果for(int out=total.length-1;out>1;out--){for (int i = 0; i < out; i++){if(total[i]>total[i+1]){swap(i,i+1);}}}//打印结果for(int i=0;i<total.length;i++){System.out.print(total[i]+" ");}long end=System.currentTimeMillis();System.out.print("花费时间:"+(end-start));}public static void swap(int a,int b){int temp=total[a];total[a]=total[b];total[b]=temp;}}?
?这就是冒泡排序。
然后我理解选择排序为取一个数a,将a和其它未进行排序过的数据进行比较。如果哪个比a小，就和a交换位置，这样a就是未排序过的数据中最小的了.代码如下
?
?
//选择排序public class ChooseSort{private static int[] total={2,8,1,9,4,11,3,7,5,6,10};public static void main(String[] args){long start=System.currentTimeMillis();for(int i=0;i<total.length-1;i++){for(int j=i+1;j<total.length;j++){if(total[i]>total[j]){swap(i,j);}}}//打印结果for(int i=0;i<total.length;i++){System.out.print(total[i]+" ");}long end=System.currentTimeMillis();System.out.print("花费时间:"+(end-start));}public static void swap(int a,int b){int temp=total[a];total[a]=total[b];total[b]=temp;}} ?
?插入排序就是 ?一些数据部分排序过，比如左边1-5号位置排序过（小到大），6-10位置未排序，那么可以将第六个位置数据取出，然后1-5位置的数据向前移动（就是第六个位置移动）,移动之前必须比较与取出的第六个位置的数据进行比较，如果大于第六个位置的数据就向前移动，否则不移动并将取出的第六个数据重新填到空的位置里。代码如下
?
?
//插入排序public class InsertSort{private static int in;private static int[] total={2,8,1,9,4,11,3,7,5,6,10};public static void main(String[] args){for(int out=1;out<total.length;out++){int temp=total[out];in=out;while(in>0 && total[in-1]>=temp){total[in]=total[in-1];--in;}total[in]=temp;}//打印结果for(int i=0;i<total.length;i++){System.out.print(total[i]+" ");}}}另外还有一种排序叫希尔排序，是插入排序的一种。
?
public static<T extends Comparable<? super T>>void incrementalSort(T[] a,int first,int last,int space){int unsorted,index;for(unsorted=first+space;unsorted<=last;unsorted=unsorted+space){T firstUnsorted=a[unsorted];for(index =unsorted-space;index>=first&&firstUnsorted.compareTo(a[index])<0;index=index-space){a[index+space]=a[index];}a[index+space]=firstUnsorted;}}public static<T extends Comparable<? super T>> void shellSort(T[] a,int first,int last){int n=last-first+1;for(int space=n/2;space>0;space=space/2){for(int begin=first;begin<first+space;begin++){incrementalSort(a, begin, last, space);}}}?调用shellSort即可。
1 楼 LuckYes 2011-09-20 楼主选择排序这样效率更好点