冒泡、选择、插入排序
冒泡排序
冒泡排序网上有很多资料,只想强调几点:
- 固定往哪个方向冒泡,个人喜欢从左向右冒泡,不要一会向左一会向右,思绪易乱。
- 泡泡到达右边后,相应位置就固定住了,所以下一次无需再经过此处,于是内层循环还要减去外层循环已进行的次数。
- 冒泡时是第 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;
}
}
选择排序
选择排序也只须注意以下几个小坑:
- 外层目标位置 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是关键,容易忽略
}
}
}
另外,插入排序是一种不稳定算法,其速度随数据状况而变,即数组越有序其速度越快,而冒泡和选择排序则是稳定的 O(N2) 。
这三种排序是最基础的排序算法,即使如此,我们也须额外小心其中的边界处理!
版权声明:
本站所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自
后端技术分享!
喜欢就支持一下吧