Sort

insert sort

插入排序是《算法导论》中第一个介绍的算法，详细分析了插入排序的原理，执行过程，证明了算法的正确性。同时也引出了算法分析和算法分析常用的方法。 此文对原文作个转述，检验学到的知识。

文中使用了伪代码写出了插入排序的执行过程，在这里用C++重写：

void insertSort( int * arr, int count )
{
	if( arr == nullptr || count == 0 )
	{
		return;
	}
	for( int i = 0; i < count; i++ )
	{
		int tem = arr[ i ];
		int j = i;
		while( j > 0 && tem > arr[ j - 1 ] )
		{
			arr[ j ] = arr[ j - 1 ];
			--j;
		}
		arr[ j ] = tem;
	}
}

插入排序类似于许多人打扑克摸牌的整理方法一样，每次从桌面上摸起一张，与原有的牌比较，播放正确的位置，这样无论何时，手中的牌总下排好序的。

《导论》中使用循环不变式证明插入排序的正确性

循环不变式有三个性质：

• 初始化：循环开始时应该是正确的
• 保持：循环在某一次迭代开始之前是正确的，那么下一次迭代开始之前，它也是应该保持正确
• 终止：当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的

前两个性质成立时，就能保证循环不变式在每一论迭代开始之前，都是正确的。这是数学归纳法相似，只是多了终止。

《导论》是这么说的，怎么理解、使用，则需要实践和验证。

我理解的循环不变式的第二条是：在前一次操作正确的情况下，保证本次操作正确。这也应该是算法设计中的重点。
拿上面的算法来实践下循环不变式：

int * arr, int count

传入待排序的数组指针和数组大小，在本例中正在排序的元素前是排序好的（相当于手中的扑克），后是未排序的（相当于桌面的牌），tem 保存中间量

• 初始化：当 i = 0; 时，排序好的是 arr[0] ，正在排序的也是 arr[0] ，此时已经排好序了。

• 保持：第_i_个元素排序时，前面arr[0]~arr[i-1]是排好序的，进入_while_循环为_i_排序，这里得保证排序正确，不然下次排序的前提条件是错误的，算法也就错误了。那么来看下_while_循环做了什么：

首先 j = i，从排序好的部分尾部开始，向前比较每一个元素大小，当第 i 个元素大于第 j-1 个元素时 arr[ j ] = arr[ j - 1 ]; 即将排序好（小于第 i 个元素）的数向后移，当条件不成立时循环结束，第 i 个元素插入到_j_的位置，此时数组中 arr[0]~arr[i] 是排序好的，下次迭代前正确

• 终止：当 i == count; 时循环终止，数组的前 i-1 个数是排序好的，而数组大小为 conut 个，数组最后一个元素的下标是 conut-1 等于此时的 i-1 ，所以此时数组已排好序了，算法正确。

好了此时能条理清晰的说明插入排序是正确的，已经有点吃力了，后面的算法分析就放到后面再讨论，先抄一段：

算法分析是指对算法所需要的资源进行预测，内存、通信带宽或计算机硬件资源以及时间等
算法分析主要考察的最坏情况
算法的增长量级

---

select sort

选择排序是《导论》第一章课后习题，仿照插入排序，再次运用循环不变式来证明下算法的正确性，C++ 源码：

// 交换函数 
void swap( int& a, int& b )
{
	a = a^b;
	b = a^b;
	a = a^b;
}
void selectSort( int *arr, int count )
{
	if( arr == nullptr || count == 0 )
	{
		return;
	}
	for( int i = 1; i < count; i++ )
	{
		int tem = arr[ i - 1 ];
		for( int j = i; j < count; j++ )
		{
			if( tem > arr[j] )
			{
				swap( tem, arr[ j ] );
			}
		}
		arr[ i - 1 ] = tem;
	}
}

传入待排序数组指针和数组大小，同样正在排序的元素前面的是已经排序好的部分，未排序的在后面。

• 初始化： i = 1; tem = arr[ 0 ]; tem 等于第一个元素，依次和后面的元素比较，如果 tem 大则交换值，这样到和后面元素比较完后 tem 就是值最小的一个，赋值给 arr[ 0 ]， arr[ 0 ] 的原值在比较过程中赋值给后面的第一个小于它的元素，数组本身数据没有增加或减少。

• 保持：第 i 个元素排序时前面元素已经按从小到大的顺序排好了，依次各后面的元素比较，如果大于后面的元素则交换值，直到比较完全部剩余的元素，这时 tem 就是剩余元素中值最小的一个赋值给 arr[ i - 1 ]，0~（i-1）的元素已经排好序了，后面的则是无序的

• 终止： 当 i == count 时，循环条件不满足，跳出循环，此时 数组的前 i-1 个已排好顺序，而数组大小为 conut 个，数组最后一个元素的下标是 conut-1 等于此时的 i-1 ，所以此时数组已排好序了，算法正确。

循环不变式 的证明结束了，需要说明的一点是上面的交换函数：

// 交换函数 
void swap( int& a, int& b )
{
	a = a^b;
	b = a^b;
	a = a^b;
}

函数参数使用引用，可以修改参数原来的值，引用在 C++ 中是变量别名，即同一个变量可以有多个名字，区别定义是名字，其他的别名叫引用，引用可以像变量本身一样对数值操作，作为函数参数时，可以在函数内部修改变量；普通的函数参数，会将传递过来变量拷贝一份，在函数内部的修改不到影响外部变量的值。 函数内部使用 ^ 异或来交换值，异或是 位 运算符，位运算比一般的运算要快；异或有个特殊的性质，连续两次异或变量的值不会变，即第一次异或会变成奇怪的值，再次异或就会变成原值，这个交换函数就是利用这个性质，

a b 异或赋值 a, a是异或后的结果
a b 再次异或结果为原来的 a, 赋值 b,交换一个
a b(原a值)异或结果为原来的 b 赋值 a,交换完成

实践两次 循环不变式 下次尝试算法分析！