冒泡、选择、插入排序

冒泡排序

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

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

template<class T, class comparator>
void mySort(T* arr, int size,comparator cmp)
{
	for(int i=0;i<size-1;i++)//注意-1！！！
		for (int k = 0; k < size - i - 1; k++)//注意-i-1！！！
		{
			if (cmp(arr[k], arr[k + 1]))//使用比较器
				swap(arr[k], arr[k + 1]);
		}
}

选择排序

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

外层目标位置 K 确定后，内层从 K+1 位置开始往后遍历。
初始 mIndex 值必须等于外层目标位置。
由于第 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]);
	}
}

插入排序

注意以下几点：

由于是 arr[k] 与 arr[k-1] 比较，所以外层从 i=1 开始。当然这只是个人偏好，也可以 arr[k] 与 arr[k+1] 比较。
内层从 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是关键,容易忽略
		}
	}
}