常用排序算法总结（一）----冒泡排序，归并排序

整理一下这几天总结的九种常用排序算法。这篇先介绍两种。先贴出测试用例Test.java。每种算法类都继承接口Sort。

import java.util.Arrays;


/**
 * @author Biang Hoo
 *
 * 2013年9月12日
 */
public class Test {


	public static void main(String[] args) {
		int array[]={10,4,9,7,23,0,5,79,1,8,0};
//		int array[]={4, 1, 1, 1, 1, 1, 5, 3, 2};
		System.out.println(Arrays.toString(array));
		System.out.println("Sorting...");
//		new BubbleSort().Sorting(array);
//		new SelectSort().Sorting(array);
//		new InsertSort().Sorting(array);
		new HeapSort().Sorting(array);
//		new QuickSort().Sorting(array);
//		new MergeSort().Sorting(array);
//		new BucketSort().Sorting(array);
//		new ShellSort1().Sorting(array);
		System.out.println(Arrays.toString(array));
		

	}

}

接口Sort

/**
 * @author Biang Hoo
 *
 * 2013年9月12日
 */
public interface Sort {
	
	public void Sorting(int array[]);

}

1 BubbleSort

一种简单的排序算法，重复遍历要排序的数列，交换乱序的元素直到没有再需要交换为止

冒泡排序算法执行顺序如下：

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这时，第一个的元素应该会是最小的数。
3、针对所有的剩余元素重复步骤1，2。直到没有任何一对数字需要比较
算法的最差时间复杂度为O(n^2),最优为O(n),平均时间复杂度为O(n^2),
空间复杂度为O（n）,需要辅助空间O（1）
代码

import java.util.Arrays;


/**
 * @author Biang Hoo
 *
 * 2013年9月12日
 */
public class BubbleSort implements Sort {
	
		public void Sorting(int array[]) {
			
			int tmp;
			
			for (int i=0;i<array.length;i++){
				for(int j =i+1;j<array.length;j++){
					if(array[i]>array[j]){
						tmp =array[i];
						array[i]=array[j];
						array[j]=tmp;
					}
				}
				System.out.println(Arrays.toString(array));
			}
		
		}
		
}

2 MergeSort

归并排序是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并

归并排序具体工作原理如下（假设序列共有n个元素）：

1、将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素

2、将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素

3、重复步骤2，直到所有元素排序完毕。

归并排序的最差时间复杂度是O（nlgn）,最优时间复杂度为O(n),平均时间复杂度为O(nlgn),空间复杂度O(n).

代码

import java.util.Arrays;


/**
 * @author Biang Hoo
 *
 * 2013年9月12日
 */
public class MergeSort implements Sort {

	@Override
	public void Sorting(int[] array) {
		
		int len = array.length;
		int [] tmp = new int[len];
		MeSort(array,0,len-1,tmp);
		
	}
	
	static  private void MergeArray(int[]a,int first,int mid,int last,int[]tmp){//将排好序的两个数组进行Merge
		
		int index =0;
		int i=first;
		int j=mid+1;
		
		while(i<=mid&&j<=last){//将两个数组的值从小到达依次赋给tmp
			if(a[i]<a[j]){
				tmp[index++] = a[i++];
			}else{
				tmp[index++] = a[j++];
			}
		}
		
		while(i<=mid){//若第第二个数组都赋给tmp后，第一个数组仍有剩余元素，则将剩余元素依次赋给tmp
			tmp[index++] = a[i++];
		}
		
		while(j<=last){
			tmp[index++] = a[j++];
		}
		for(i=0;i<index;i++){//将tmp的值取出，赋给一个数组
			a[first+i] = tmp[i];
		}
		
	}
	static private void MeSort(int[]a,int first,int last,int[] tmp){//递归
		if(first<last){
			int mid =(first+last)/2;
			MeSort(a,first,mid,tmp);
			MeSort(a,mid+1,last,tmp);
			MergeArray(a,first,mid,last,tmp);
		}
	}
}