C++选择排序


  凉凉给自己      118   
  2021-01-20      C++      

第i次“选择”数组中第i小的记录,并将该记录放到数组的第i个位置。换句话说,每次从未排序的序列中找到最小元素,放到未排序数组的最前面
代码

template<class Elem>
void selsort(Elem A[],int n)
{
    for(int i = 0;i < n - 1;i++){
        int lowindex = i;
        for(int j = i + 1;j < n;j++)
            if(A[j] < A[lowindex])
                lowindex = j;
        swap(A,i,lowindex);//n次交换
    }
}

性能
不管数组是否有序,在从未排序的序列中查找最小元素时,都需要遍历完最小序列,所以时间复杂度为O(n^2)
优化
每次内层除了找出一个最小值,同时找出一个最大值(初始为数组结尾)。将最小值与每次处理的初始位置的元素交换,将最大值与每次处理的末尾位置的元素交换。这样一次循环可以将数组规模减小2,相比于原有的方案(减小1)会更快
作者:it_xiangqiang

ps:以上是C++选择排序全部内容,希望文章能够帮你解决C++选择排序所遇到的游戏开发问题。
本文收录在 游戏编程 🕹️ - 学习C++专题,分享走一走~

猜你喜欢 全系列


您可以在登录后,发表评论




    关于作者
    游戏开发者 - 101
  • 凉凉给自己
  • 码神
  • 653 文章  √   3 提问  ?
    此作者缺少注释。


    目录