冒泡排序

冒泡排序网上有很多资料，只想强调几点：

1. 固定往哪个方向冒泡，个人喜欢从左向右冒泡，不要一会向左一会向右，思绪易乱。
2. 泡泡到达右边后，相应位置就固定住了，所以下一次无需再经过此处，于是内层循环还要减去外层循环已进行的次数。
3. 冒泡时是第 K 个与第 K+1 个元素相比较，所以外层循环次数为 size-1 次即可，最后一个位置无需单独比较。

void Bubblesort(int* arr, int n)
{
	for(int i = 0; i < n - 1; i++)//只需比较n-1次
	{
		bool flag = false;
		for(int k = n - 1; k > i; k—)//[i,n-1]无序，对此部分进行冒泡
		{
			if(arr[k-1] < arr[k])
			{
				swap(arr[k-1], arr[k]);
				flag = true;
			}
		}
		if(flag == false)//如果没有发生交换，则说明已经有序
			return;
	}
}

选择排序

选择排序也只须注意以下几个小坑：

1. 外层目标位置 K 确定后，内层从 K+1 位置开始往后遍历。
2. 初始 mIndex 值必须等于外层目标位置。
3. 由于第 1 点，所以外层 i<size-1，内层 k <size；

template<class T, class comparator>
void mySort(T* arr, int size,comparator cmp)
{
	int mIndex; //最大或最小值的下标
	for (int i = 0; i < size-1; i++)//注意-1!
	{
		mIndex = i; //这里是最容易忽略的！
		for (int k = i+1; k < size; k++)
		{
			if(!cmp(arr[mIndex], arr[k]))
				mIndex = k;
		}
		swap(arr[i], arr[mIndex]);
	}
}

插入排序

注意以下几点：

1. 由于是 arr[k] 与 arr[k-1] 比较，所以外层从 i=1 开始。当然这只是个人偏好，也可以 arr[k] 与 arr[k+1] 比较。
2. 内层从 i 开始。

template<class T, class comparator>
void insertSort(T* arr, int size, comparator cmp)
{
	for (int i = 1; i < size; i++)
	{
		for (int k = i; k > 0; k--) //注意是k>0而非k>=0
		{
			if (!cmp(arr[k-1], arr[k]))
				swap(arr[k-1], arr[k]);
			else
				break; //break是关键,容易忽略
		}
	}
}

另外，插入排序是一种不稳定算法，其速度随数据状况而变，即数组越有序其速度越快，而冒泡和选择排序则是稳定的 O(N²) 。

这三种排序是最基础的排序算法，即使如此，我们也须额外小心其中的边界处理！