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 楼主选择排序这样效率更好点
for(i=n-1;i>0;i--){

big=first;//把第一个位置看成最大值
for(j=first+1;j<=first+i;j++)
if(data[big]<data[j])

big=j;//最大值得位置

//交换位置//楼主在这一步每次比较都进行交换明显效率低下
temp=data[first+i];
data[first+i]=data[big];
data[big]=temp;
}



} 2 楼 LuckYes 2011-09-20 另外楼主的冒泡最好加一个哨兵booelan=true or false，就是当已经【排好序的时候就不用进行多次排序了
boolean isExchanged=false;
for(int out=total.length-1&&!isExchanged;out>1;out--)
{
for (int i = 0; i < out; i++)
{
if(total[i]>total[i+1])
{
swap(i,i+1);
break; //跳出循环
}
isExchanged=true//证明已经排好寻了，不用再比较了，你可以试验一下此时的out的数值
}
3 楼 348725767 2011-09-20 恩 学习了