选择排序算法从难到易实现

难实现：

代码语言：javascript复制

/*
编写一个程序，将一个整型数组中的数据从大到小排列，要求使用选择排序
*/

#include <iostream>
using namespace std;

//每次选择序列中的最小元素，让他它未排序的第一个元素交换
void selectSort(int data[],int len)
{
  
   int tmp;
   int i,j;
   int min;
   for(i=0;i<len-1;i  )
   {
       min=i;

       for(j=i 1;j<len;j  )
       {
           if(data[min]>=data[j])
           {
               min=j;//记录最小元素的位置
           }
       }

       if(min!=i)
       {
           tmp=data[min];
           data[min]=data[i];
           data[i]=tmp;
       }

   }
     
    
}

int main()
{
    int data[9]={0,3,1,2,4,6,6,10,5};
    selectSort( data,9);
    for(int i=0;i<9;i  )
        cout<<data[i]<<endl;

    return 0;
}

易实现：

代码语言：javascript复制

#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <iostream>

using namespace std;
//每次选择序列中的最小元素，让他它未排序的第一个元素交换

//选择排序，总体交换次数最少
//重复使用 std::min_element 发现最小元素，然后 iter_swap 将它交换到相应位置

template <class FwdIt, class Compare=std::less<FwdIt>>

void selection_sort(FwdIt first, FwdIt last, Compare cmp=Compare{})
{
    for (auto it=first; it != last;   it)
    {
        auto const selection = std::min_element(it,last,cmp);
        std::iter_swap(selection,it);
        assert(std::is_sorted(first,std::next(it),cmp));
    }
    //[first,it) 中的元素已经排好序
}

int main()
{
    std::vector<int> data={0,3,1,2,4,6,6,10,5};
    
    selection_sort(data.begin(),data.end(),std::less<int>());

    for(int i=0;i<data.size();i  )
        cout<<data[i]<<endl;
    return 0;
}

排序算法

0 人点赞