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即可。

评论

3 楼 348725767 2011-09-20  

恩  学习了

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的数值
            }  

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;
}



}