[MOOC札记]排序专题(数据结构)

[MOOC笔记]排序专题(数据结构)

1.冒泡排序：

思路：将相邻的逆序元素交换为顺序排列，直到整个序列有序，算法如下：

/**
 * 冒泡排序-最初实现，时间复杂度O(n^2)	
 * @param arr 待排序的数组
 * @param lo 待排序区间的起始位置
 * @param hi 待排序区间的结束位置
 */
public static void bubbleSort(int[] arr, int lo, int hi) {
	//对序列进行规模n-1次扫描
	for (int i = lo; i < hi - 1; i++) {
		//每次扫描都会将当前区间最大的元素移到末尾，所以每次扫描的范围都可以减少1
		for (int j = lo; j < hi - i - 1; j++) {
			//判断相邻元素是否为逆序，是的话交换
			if (arr[j] > arr[j + 1]) {
				swap(arr, j, j + 1);
			}
		}
	}
}

以上算法在任何情况都会对一个规模为n的序列进行n-1次扫描，即使该序列在中途已经变成有序。所以需要一个标示位来记录每次扫描后该序列是否已经完成排序，改进算法如下：

/**
 * 冒泡排序-改进一:记录扫描结果，时间复杂度O(n^(3/2))	
 * @param arr 待排序的数组
 * @param lo 待排序区间的起始位置
 * @param hi 待排序区间的结束位置
 */
public static void bubbleSort(int[] arr, int lo, int hi) {
	//对序列进行规模n-1次扫描
	for (int i = lo; i < hi - 1; i++) {
		//设置一个标示位记录序列是否为有序状态
		boolean sorted = true;
		//每次扫描都会将当前区间最大的元素移到末尾，所以每次扫描的范围都可以减少1
		for (int j = lo; j < hi - i - 1; j++) {
			//判断相邻元素是否为逆序，是的话交换并将有序标示置为false
			if (arr[j] > arr[j + 1]) {
				swap(arr, j, j + 1);
				sorted = false;
			}
		}
		//当一次扫描后有序标示扔为true，则序列已经有序，停止扫描
		if (sorted) {
			break;
		}
	}
}

改进后的算法还是有缺陷，即使扫描的次数动态的减少了，但是每次扫描的范围还是固定的。于是接着改进：

/**
 * 冒泡排序-改进二:记录逆序范围，时间复杂度O(n)	
 * @param arr 待排序的数组
 * @param lo 待排序区间的起始位置
 * @param hi 待排序区间的结束位置
 */
public static void bubbleSort(int[] arr, int lo, int hi) {
	//在可能存在逆序的区间消失前一直扫描
	while (lo < hi) {
		//将秩设为区间的起始位置
		int last = lo;
		//扫描整个区间
		for (int j = lo; j < hi - 1; j++) {
			//判断相邻元素是否为逆序，是的话交换并记录下位置
			if (arr[j] > arr[j + 1]) {
				swap(arr, j, j + 1);
				last = j + 1;
			}
		}
		//将最后一次进行交换的位置设为区间的结束位置（之后的所有元素均为有序排列）
		hi = last;
	}
}

三种冒泡排序的时间成本如图所示：

[MOOC札记]排序专题(数据结构)

2.选择排序：

思路：每次选取区间内最大（小）的元素移动到区间前端，直到所有元素被选取完毕，算法如下：

/**
 * 选择排序，时间复杂度O(n^2)
 * @param arr 待排序的数组
 * @param lo 待排序区间的起始位置
 * @param hi 待排序区间的结束位置
 */
public static void selectionSort(int[] arr, int lo, int hi) {
	//对序列进行规模n-1次扫描
	for (int i = lo; i < hi - 1; i++) {
		int max = arr[i], index = i;
		//每次扫描都会记录当前区间最小的元素
		for (int j = i + 1; j < hi; j++) {
			if (arr[j] < max) {
				max = arr[j];
				index = j;
			}
		}
		//将最小元素移到区间最前面
		if (index != i) {
			swap(arr, i, index);
		}
	}
}

选择排序的主要时间成本在于选取区间内的最大元素，这个操作的时间复杂度是O(n)，而有种方法可以将这个时间成本降低至O(logn)，这将会在之后的堆排序中介绍。

3.归并排序

思路：将整个序列分为多个子序列，并依次将子序列排序，最后合并成有序序列，算法如下：

/**
 * 归并排序，时间复杂度O(nlogn)
 * @param arr 待排序的数组
 * @param lo 待排序区间的起始位置
 * @param hi 待排序区间的结束位置
 */
public static void mergeSort(int[] arr, int lo, int hi) {
	//如果该区间只剩下一个元素，则推出递归
	if (hi - lo < 2) {
		return;
	}
	//以中点为轴点分割两个区间
	int mid = (hi + lo) >> 1;
	//分别递归两个区间
	mergeSort(arr, lo, mid);
	mergeSort(arr, mid, hi);
	//将两个区间合并
	merge(arr, lo, mid, hi);
}

/**
 * 归并排序的合并区间
 * @param arr 待排序的数组
 * @param lo 待合并区间的起始位置
 * @param mid 区间分隔的点
 * @param hi 待合并区间的结束位置
 */
private static void merge(int[] arr, int lo, int mid, int hi) {
	//建立临时数组备份待排序区间
	int[] temp = new int[hi - lo];
	for (int i = lo; i < hi; i++) {
		temp[i - lo] = arr[i];
	}
	//设置两个秩分别指向两个临时区间的起始位置，设置一个秩指向整个区间的起始位置
	int i = 0, j = mid - lo, k = lo;
	//当整个区间的秩指向区间的结束位置时停止
	while (k < hi) {
		//将两个秩指向的元素中较小者存放到待排序区间
		if ((i < mid - lo) && (j >= hi - lo || temp[i] < temp[j])) {
			arr[k++] = temp[i++];
		}
		if ((j < hi - lo) && (i >= mid - lo || temp[j] < temp[i])) {
			arr[k++] = temp[j++];
		}
	}
	
}

4.插入排序

思路：将每个元素取出并插入到合适的位置，使该元素与它前一个和后一个元素均为顺序排列，直到所有元素插入完毕。算法如下：

/**
 * 插入排序，时间复杂度O(n^2)
 * @param arr 待排序的数组
 * @param lo 待排序区间的起始位置
 * @param hi 待排序区间的结束位置
 */
public static void insertionSort(int[]arr, int lo, int hi) {
	//扫描每一个元素
	for (int i = lo + 1; i < hi; i++) {
		//如果该元素比它前一个元素要小
		if (arr[i] < arr[i - 1]) {
			//记录下它的位置和值
			int temp = arr[i];
			int index = i;
			//将比它大的元素依次后移
			while (index > 0 && arr[index - 1] > temp) {
				arr[index] = arr[index - 1];
				index--;
			}
			//将它插入到合适的位置
			arr[index] = temp;
		}
	}
}

未完待续....

[MOOC札记]排序专题(数据结构)

相关推荐