排序算法

参考：http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.2.htm

http://www.stuhack.com/biancheng/c/39543.html

http://blog.csdn.net/agwujiang/article/details/5829443

 

冒泡排序：

package cn.edu.tju.sortArithmetic;

/*冒泡排序跟选择排序，貌似没啥区别啊
 * 时间复杂度：最差、平均O(n^2)，最好O(n)，空间复杂度1
 * 稳定排序
 */
public class BubbleSort {
	
	public static void bubble(int[] arr){
		for(int i = arr.length - 1; i > 0; i --){
			for(int j = 0; j < i; j ++){
				if(arr[i] < arr[j]){
					Util.swap(arr, i, j);
				}
			}
		}
	}

}

 

 选择排序：

package cn.edu.tju.sortArithmetic;

/*
 * 基本思想：首先在未排序的序列中找到最小元素，放到序列起始位置。
 * 然后从剩下的未排序的元素中继续寻找最小元素，放到已排好的序列末尾
 * 
 * 选择排序跟冒泡排序，貌似没啥区别啊
 * 时间复杂度：最差、平均O(n^2)，空间复杂度1
 * 不稳定排序
 */
 
public class SelectionSort {
	
	public static void selection(int[] arr){
		
		for(int i = 0; i < arr.length; i ++){
			for(int j = i + 1; j < arr.length; j ++){
				if(arr[i] > arr[j]){
					Util.swap(arr, i, j);
				}
			}
		}
	}

}

 

插入排序：

package cn.edu.tju.sortArithmetic;

/*
 * 插入排序基本思想：
 * 1从第一个元素开始，该元素默认已被排序
 * 2取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 3若新元素小于原元素（已排序），则将原元素后移
 * 重复3，直到找到新元素大于或等于原元素的位置，将新元素插入
 * 重复2
 * 
 * 时间复杂度：最差、平均都是O(n^2)，最好O(n)，空间复杂度1
 * 稳定排序
 */
public class InsertionSort {

	public static void insertion(int[] arr){
		for(int i = 0; i < arr.length; i ++){
			for(int j = i; j > 0; j --){
				if(arr[j] < arr[j - 1]){
					Util.swap(arr, j, j - 1);
					Util.output(arr);
				}
			}
		}
	}
}

 

希尔排序：动画演示

package cn.edu.tju.sortArithmetic;

/*
 * 希尔排序基本思想：
 * /2取增量d，将i = i + d的元素作为一组，分成几组之后，在各组内进行插入排序，直到d = 1时，也即每个元素一组时，完成排序
 * 如若有10个元素，则增量取为5,2,1，增量的取法不定
 * 第一次排序d=5； 分组：0,5；1,6；2,7；3,8；4,9 第一组作为已排好序的初始序列，然后后面各组分别通过插入排序插入
 * 第二组d=2；分组：0,2,4,6,8；1,3,5,7,9；
 * 第三组d=1；分组：0,1,2,3,4,5,6，7,8,9；
 * 
 * 希尔排序性能优于直接插入排序
 * 时间复杂度：O(nlogn)，空间复杂度：1
 * 不稳定排序
 */
public class ShellSort {
	
	public static void shell(int[] arr){
		int increment = arr.length;
		while((increment /= 2) > 0){
			for(int i = increment; i < arr.length; i ++){
				for(int j = i; j - increment >= 0; j -= increment){
					if(arr[j] < arr[j - increment]){
						Util.swap(arr, j, j - increment);
					}
				}
			}
		}
	}
}

 

快速排序：

package cn.edu.tju.sortArithmetic;

/*
 * 快速排序基本思想：
 * 1设置关键值X，一般为数组的第一个值，设定指针开始i=0，结束j=length-1
 * 2数组从后往前扫描，找到第一个小于X的元素，并与X交换
 * 3数组从前往后扫描，找到第一个大于X的元素，并与X交换
 * 4重复2，3步，直到i >= j结束一次快速排序，此时所有大于X的数全部在X之后，小于X的数全部在X之前
 * 递归此过程，对X之前的序列和X之后的序列分别进行快速排序，从而完成全部数据的快速排列
 * 
 * 时间复杂度：平均O(nlogn)，最坏O(n^2)，空间复杂度O(logn)
 * 不稳定排序
 */
public class QuickSort {

	public static void quick(int[] arr, int left, int right) {
		if (left >= right) {
			return;
		}
		int pivotpos = partion(arr, left, right);
		quick(arr, left, pivotpos - 1);
		quick(arr, pivotpos + 1, right);
	}

	public static int partion(int[] arr, int i, int j) {
		int pivotpos = i;//表示关键值位置
		
		while (i < j) {
			//2数组从后往前扫描，找到第一个小于X的元素，并与X交换
			while (i < j && arr[j] > arr[pivotpos]) {
				j--;
			}
			Util.swap(arr, pivotpos, j);
			pivotpos = j;
			//3数组从前往后扫描，找到第一个大于X的元素，并与X交换
			while (i < j && arr[i] < arr[pivotpos]) {
				i++;
			}
			Util.swap(arr, pivotpos, i);
			pivotpos = i;
		}
		return pivotpos;
	}
}

 

归并排序：貌似有些问题。。。待解决

package cn.edu.tju.sortArithmetic;

/*
 * 归并排序的算法思想：把待排序序列分成相同大小的两个部分，依次对这两部分进行归并排序，
 * 完毕之后再按照顺序进行合并。
 * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 
 * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个
 * 有序表，称为2-路归并。
 * 
 * 工作原理：
 * 1将序列每相邻的两个数字进行归并操作merge，形成floor(n/2)个序列，排序后每个序列包含两个元素
 * 2将上述序列再次归并，形成floor(n/4)个序列，每个序列包含4个元素
 * 3重复2，直到所有元素排序完毕
 * 
 * 时间复杂度：最差、平均和最好都是O(nlogn)，空间复杂度O(n)
 * 稳定排序
 */
public class MergeSort {
	
	public static void mergeSort(int[] arr, int left, int right){
		if(left < right){
			int mid = (left + right)/2;
			mergeSort(arr, left, mid);
			mergeSort(arr, mid + 1, right);
			merge(arr, left, mid, mid + 1, right);
			
		}
	}
	
	public static void merge(int[] arr, int start1, int end1, int start2, int end2){
		int i = start1;//前半段指针
		int j = start2;//后半段指针
		int k = 0;//整个序列的指针
		int[] temp = new int[end2 - start1 + 1];//建立临时数组，长度为两段序列的长度之和
		while(i <= end1 && j <= end2){//依次从两个子序列中取出元素较小的放入temp
			System.out.println(i + ", " + j);
			if(arr[i] < arr[j]){
				temp[k++] = arr[i++];//等价于temp[k] = arr[i]; k ++; i ++;
			}else{
				temp[k++] = arr[j++];
			}
		}
		//把剩下的元素一次放入temp，肯定只剩下一方
		while(i <= end1){
			temp[k++] = arr[i++];
		}
		while(j <= end2){
			temp[k++] = arr[j++];
		}
		//System.out.println(tem)
		for(int m = start1; m < temp.length; m ++){
			arr[m] = temp[m];
		}
	}
}

 

归并排序：貌似有些问题。。。待解决

package cn.edu.tju.sortArithmetic;

/*
 * 归并排序的算法思想：把待排序序列分成相同大小的两个部分，依次对这两部分进行归并排序，
 * 完毕之后再按照顺序进行合并。
 * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 
 * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个
 * 有序表，称为2-路归并。
 * 
 * 工作原理：
 * 1将序列每相邻的两个数字进行归并操作merge，形成floor(n/2)个序列，排序后每个序列包含两个元素
 * 2将上述序列再次归并，形成floor(n/4)个序列，每个序列包含4个元素
 * 3重复2，直到所有元素排序完毕
 * 
 * 时间复杂度：最差、平均和最好都是O(nlogn)，空间复杂度O(n)
 * 稳定排序
 */
public class MergeSort {
	
	public static void mergeSort(int[] arr, int left, int right){
		if(left < right){
			int mid = (left + right)/2;
			mergeSort(arr, left, mid);
			mergeSort(arr, mid + 1, right);
			merge(arr, left, mid, mid + 1, right);
			
		}
	}
	
	public static void merge(int[] arr, int start1, int end1, int start2, int end2){
		int i = start1;//前半段指针
		int j = start2;//后半段指针
		int k = 0;//整个序列的指针
		int[] temp = new int[end2 - start1 + 1];//建立临时数组，长度为两段序列的长度之和
		while(i <= end1 && j <= end2){//依次从两个子序列中取出元素较小的放入temp
			System.out.println(i + ", " + j);
			if(arr[i] < arr[j]){
				temp[k++] = arr[i++];//等价于temp[k] = arr[i]; k ++; i ++;
			}else{
				temp[k++] = arr[j++];
			}
		}
		//把剩下的元素一次放入temp，肯定只剩下一方
		while(i <= end1){
			temp[k++] = arr[i++];
		}
		while(j <= end2){
			temp[k++] = arr[j++];
		}
		//System.out.println(tem)
		for(int m = start1; m < temp.length; m ++){
			arr[m] = temp[m];
		}
	}
}

 

工具类：包括交换两个元素以及输出。

package cn.edu.tju.sortArithmetic;

public class Util {
	
	public static void swap(int[] arr, int i, int j){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public static void output(int[] arr){
		for(int i = 0; i < arr.length; i ++){
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

}

 

 

测试类：

package cn.edu.tju.sortArithmetic;

public class Test {
	
	public static void main(String[] args){
		int[] arr = {5, 7, 9, 3, 4, 1, 2, 6, 8, 0};
		//int[] arr = {49, 38, 65, 97, 76, 13, 27};
		//BubbleSort.bubble(arr);
		//SelectionSort.selection(arr);
		//InsertionSort.insertion(arr);
		//ShellSort.shell(arr);
		//QuickSort.quick(arr, 0, arr.length - 1);
                MergeSort.mergeSort(arr, 0, arr.length - 1);
                 Util.output(arr);
	}
}