C/C++教程

C++知识:选择排序

本文主要是介绍C++知识:选择排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

选择排序（Select Sort） 是直观的排序，通过确定一个 Key 最大或最小值，再从待排序的的数中（无序区）找出最大或最小的交换到对应位置。再选择次之。双重循环时间复杂度为 O(n^2)

算法描述：
  1. 在一个长度为 N 的无序数组中，第一次遍历第1..第n个数找到最小的和第一个数交换。
  2. 第二次遍历第2..第n个数，找到最小的数和第二个数交换。
  3. 重复以上操作直到第 n-1 次遍历第n-1和第n个数找到最小的和第n-1个数交换，排序完成。
    算法可视化： 


代码实现：

cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
 
for(int i=1;i<n;++i)  //n-1趟，每趟从a[i]..a[n]中找最小的数和a[i]交换
{
    p=i;  //p存储a[i]..a[n]中最小数的位置，先假定在i。
    for(int j=i+1;j<=n;++j)  //枚举a[i+1]..a[n]
        if(a[j]<a[p]) p=i; //打擂台更新最小数位置
    swap(a[i],a[p]);
}

 

这篇关于C++知识:选择排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航