Lecture 19-平方阶排序算法

直接插入排序

外循环：遍历所有元素，将当前R[i]记为K

内循环：从当前i-1开始，j往前遍历，从右往左找第一个<=当前K的元素R[j]，将该元素的右边的第一个元素修改为K

逐个插入，插入时即确定位置

/*直接插入排序*/
void InsertionSort(int R[], int n) {  //对R[1]...R[n]排序
	for (int i = 2; i <= n; i++) {
		int K = R[i], j = i - 1;
		while (j >= 1 && R[j] > K) {  //通过指针j扫描R[i-1]...R[1]，从右往左找第1个<=R[i]的元素
			R[j + 1] = R[j];
			j--;
		}
		R[j + 1] = K;
	}
}

时间复杂度及稳定性分析

简单冒泡排序

从左往右扫描数组，如果遇到反序对（两个相邻的元素，且前面的元素比后面大），则交换这两个元素。

扫描一趟之后，则最大元素被交换到最右边。

如果把数组立起来，最大元素就像气泡一样，浮到上面。此过程称为一趟冒泡。

外层循环：从n到2，从右向左，依次全部遍历

内层循环：从1到当前bound，从左到右，找逆序对进行交换

/*冒泡排序*/
void SimpleBubbleSort(int R[], int n) {
	for (int bound = n; bound >= 2; bound--) {
		for (int i = 1; i < bound; i++) {
			if (R[i] > R[i + 1])
				swap(R[i] , R[i + 1]);
		}
	}
}

 优化冒泡排序

在每趟冒泡过程中，当比较结束后，如果发现位置t是最后依次元素交换的位置，即说明从Rt+1~Rn已经排序。

从而下一趟比较只要进行到位置t即可。

这样可以减少算法的关键词比较次数。

void BubbleSort(int R[], int n) {
	int bound = n;  //每趟冒泡排序关键词比较终止位置
	while (bound > 0) {
		int t = 0;  //本趟冒泡元素交换的最后位置
		for (int i = 1; i < bound; i++) {
			if (R[i] > R[i + 1]) {
				swap(R[i], R[i + 1]);
				t = i;
			}
		}
		bound = t;
	}
}

时间复杂度及稳定性分析

直接选择排序

（1）在前n个元素里找最大元素，与R[n]交换，使R[n]就位

（2）在前n-1个元素里找最大元素，与R[n-1]交换，使R[n-1]就位

（3）在前n-2个元素里找最大元素，与R[n-2]交换，使R[n-2]就位

······

以此类推，最后形成递增的有序序列

注意的是，因为交换使得原始顺序被打乱，因此直接选择排序不稳定。

/*直接选择排序*/
void SelectionSort(int R[], int n) {
	for (int i = n; i >= 1; i--) {
		//i标识当前处理的子数组的右边界
		//在子数组R[i]...R[i]里找最大元素，和R[i]交换
		int max = 1;
		for (int j = 2; j <= i; i++) {
			if (R[j] > R[max]) max = j;
		}
		swap(R[max], R[i]);
	}
}

时间复杂度及稳定性分析 

希尔排序

亦称渐进增量排序，是对直接排序算法的改进（可看作直接插入算法的升级版）。

把记录按下标进行分组。

直接插入排序算法在“短文件”、“待排序文件基本有序”时速度快，希尔排序充分利用了这两个特点。

基本过程：

（1）将元素分为d组；

（2）对每组使用直接插入排序法排序；

（3）把d值减小，重复执行(1）（2），直至d减小到1。

随着增量d逐渐减小，组数越来越少，魅族包含的元素越来越多，当d值减少到1时，整个文件敲好被分成1组，算法终止。

原理：

开始时增量值比较大，每组中的元素较少，插入排序速度较快；

算法执行过程中，随着增量值逐渐变小，每组中元素个数逐渐变多，由于前面工作的基础，大多数元素已基本有序，而插入排序在元素接近有序时速度快。

实现：

分组及对每组插入排序：

无需新开数组，可在原来的大数组上操作；

组内相邻元素的下标间隔d。

/*希尔排序*/
void ShellSort(int R[], int n) {  //对R[1]...R[n]递增排序
	for (int d = n / 2; d > 0; d /= 2) {  //d为增量值
		for (int i = d + 1; i <= n; i++) {  //...R[i-3d],R[i-2d],R[i-d]
			int K = R[i], j = i - d;  //指针j从右往左扫描本组元素
			while (j > 0 && R[j] > K) {  //在本组中从右往左找第1个<=K的元素
				R[j + d] = R[j];
				j -= d;
			}
			R[j + d] = K;
		}
	}
}

时间复杂度及稳定性分析

算法的时间复杂度与所选的增量序列有很大关系；

一般认为平均时间复杂度介于O(N^2)和O(nlogn)之间；

稳定性：不稳定