排序算法总结

排序算法总结

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
　　输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
　　输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

排序的稳定性

当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。
　在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

注意：排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

排序方法的分类

1、在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。

注意：

①内排序适用于记录个数不很多的小文件
　② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。

2、按策略划分内部排序方法

可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。

一、插入排序

基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

1、直接插入排序

基本思想：假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

算法分析：稳定性，时间复杂度O(n*n)，空间复杂度：O(1)。

代码如下：

public static void insertSort(int[] arr){
		int i,j;
		int len = arr.length;
		for (i = 1; i < len; i++) {
			int temp = arr[i];
			j = i;
			while (temp < arr[j-1]) {
				arr[j] = arr[j-1];
				j--;
				if (j<=0) {
					break;
				}
			}
			arr[j] = temp;
		}
	}

2、希尔排序

基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

算法分析：不稳定，时间复杂度：O(n*n)，空间复杂度：O(1)。

代码如下：

public static void shellSort(int[] arr) {
		int len = arr.length;
		for (int h = len / 2; h > 0; h /= 2) {
			for (int i = h; i < len; i++) {
				int j = i % h;
				while (j <= i && arr[i] > arr[j])
					j += h;// 找到element[i]应该摆放的位置
				if (j < i) {
					// 将j之后的数据移动h位，然后把elements[i]移动到j处
					int temp = arr[i];
					for (int k = i - h; k >= j; k -= h) {
						arr[k + h] = arr[k];
					}
					arr[j] = temp;
				}
			}
		}
	}

二、交换排序

基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

1、冒泡排序

基本思想：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

算法分析：稳定，时间复杂度：O(n*n)，空间复杂度：O(1)。

代码如下：

public static void bulleSort(int[] arr){
		boolean exchange;
		int len = arr.length;
		for (int i = 0; i < len; i++) {
			exchange = false;
			for (int j = len-1; j > i; j--) {
				if (arr[j-1]>arr[j]) {
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
					exchange = true;
				}
			}
			if (!exchange) {
				return;
			}
		}
	}

2、快速排序

基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法分析：不稳定，时间复杂度：O(n*log2(n))，空间复杂度：O()。

代码如下：

//递归算法

public static void quickSort(int[] arr,int low,int hight){
		int pivotpos;
		if (low<hight) {
			pivotpos = partition(arr,low,hight);
			quickSort(arr, low, pivotpos-1);
			quickSort(arr, pivotpos+1, hight);
		}
	}

	public static int partition(int[] arr,int low,int hight){
		int pivot,pos,temp;
		int len = arr.length;
		pos = low;
		pivot = arr[pos];
		for (int i = low+1; i < len; i++) {
			if (arr[i]<pivot) {
				pos++;
				temp = arr[i];
				arr[i] = arr[pos];
				arr[pos] = temp;
			}
		}
		temp = arr[pos];
		arr[pos] = arr[low];
		arr[low] = temp;
		return pos;
	}

待续。。