简单选择排序

冒泡排序的思想就是不断地交换,通过交换完成最终排序。我们可不可以像只有在时机非常明确到来时才出手,也就是排序找到合适的关键字在做交换,并且只移动一次就完成相应的排序定位工作?这就是选择排序的基本思想。

选择排序是每一趟在 n - i + 1(i = 1,...,n-1)个记录中选取关键字最小的记录作为有序序列的第 i 个记录。

代码:

简单的选择排序法(Simple Selection Sort)就是通过 n-i 次关键字之间的比较,从 n-i+1个记录中选出关键字最小的记录,并和第 i 个记录交换。

	void SelectionSort(SqList *L) {
		int i,j,min;
		for (int i = 1; i < L->length; i++) {
			min = i; // 当前下标定义为最小值下标
			for(int j = i + 1;j<L->length;j++)  // 循环i之后的数据
			{
				if (L->r[min]>L->r[j]) { // 如果有小于min这个关键字的记录
					min = j;  // 把关键字的下标赋值给min
				} // Of if
			} // Of for j
			if (i!=min) { // 说明min已经更新,变了
				swap(L,i,min);
			} // Of if		
		} // Of for i
	} // Of SelectionSort

尽管冒泡排序和简单排序的时间复杂度都是O(n^2),但是选择排序性能还是要好一点。

上一篇:二叉树递归套路(2):判断二叉树是否是搜索二叉树、二叉树的最大距离


下一篇:css宽度高度自适应