C++实现选择排序（selectionSort）

本文实例为大家分享了Android九宫格图片展示的具体代码，供大家参考，具体内容如下

一、思路

每次取剩下没排序的数中的最小数，然后，填到对应位置。（可以使用a[0]位置作为暂存单元）

如下：

二、实现程序

#include <iostream>
using namespace std;

const int maxSize = 100;

template<class T>
void SelectSort(T arr[], int n); // 选择排序

int main(int argc, const char * argv[]) {
 int i, n, arr[maxSize];

 cout << "请输入要排序的数的个数：";
 cin >> n;
 cout << "请输入要排序的数：";
 for(i = 1; i <= n; i++) // arr[0]不存放值，用来做暂存单元
  cin >> arr[i];
 cout << "排序前：" << endl;
 for(i = 1; i <= n; i++)
  cout << arr[i] << " ";
 cout << endl;
 SelectSort(arr, n);
 cout << "排序后：" << endl;
 for(i = 1; i <= n; i++)
  cout << arr[i] << " ";
 cout << endl;
 return 0;
}

// 直接选择排序
template <class T>
void SelectSort(T arr[], int n) {
 int i, j, pos;

 for(i = 1; i < n; i++) { // 共作n-1趟选择排序
  pos = i; // 保存最小数的位置
  for(j = i; j <= n; j++) { // 找比arr[i]更小的值
   if(arr[j] < arr[pos]) {
    pos = j; // 指向更小的数的位置
   }
  }
  if(pos != i) { // 找到了更小的值，就交换位置
   arr[0] = arr[i]; // arr[0]作为暂存单元
   arr[i] = arr[pos];
   arr[pos] = arr[0];
  }
 } // for
} // SelectSort

测试数据：

7

20 12 50 70 2 8 40

测试结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • C++选择排序算法实例

    选择排序 选择排序是一种简单直观的排序算法,它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常

  • c++选择排序详解

    c++选择排序详解

    选择排序,作为八大经典算法之一,虽不如插入,快速,希尔等排序高效,但其结构简单,思路清晰,适合新手理解算法, 了解排序,适合数据较少时的排序情况. 如下是选择排序的图解原理 如果说冒泡排序是顶向下,那么选择排序就是由底向上了,先解决第一个数,再解决第二个数,依次解决整个数组的排序 如下是全部代码的实现 #include <iostream> #include <math.h>//待会会用到swap交换函数 using namespace std; int main() { int

  • VC++实现选择排序算法简单示例

    本文以一个非常简单的实例说明VC++选择排序算法的实现方法,对n个记录进行n-1趟简单选择排序,在无序区中选取最小记录. 具体实现代码如下: #include<iostream> using namespace std; //简单选择排序 void SelectSort(int r[ ], int n) { int i; int j; int index; int temp; for (i=0; i<n-1; i++) //对n个记录进行n-1趟简单选择排序 { index=i; for

  • C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

  • C++选择排序算法实例详解

    本文实例为大家分享了C++选择排序算法的具体代码,供大家参考,具体内容如下 基本思想 每一趟从无序区中选出最小的元素,顺序放在有序区的最后,直到全部元素排序完毕. 由于选择排序每一趟总是从无序区中选出全局最小(或最大)的元素,所以适用于从大量元速度中选择一部分排序元素.例如,从10000个元素中选出最小的前10位元素. 直接选择排序 1.排序思路 从第i趟开始,从当前无序区arr[i-n-1]中选出最小元素arr[k],将它与有序区的最后一个元素,也就是无序区的第一个元素交换.每趟排序后,有序区

  • Java经典算法汇总之选择排序（SelectionSort）

    Java经典算法汇总之选择排序（SelectionSort）

    a)原理:每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕.也就是:每一趟在n-i+1(i=1,2,-n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录.基于此思想的算法主要有简单选择排序.树型选择排序和堆排序.(这里只介绍常用的简单选择排序) b)简单选择排序的基本思想:给定数组:int[]arr={里面n个数据}:第1趟排序,在待排序数据arr[1]~arr[n]中选出最小的数据,将它与arrr[1]交换:第2趟,在待排序数据arr[2]~ar

  • C++实现选择排序（selectionSort）

    本文实例为大家分享了Android九宫格图片展示的具体代码,供大家参考,具体内容如下 一.思路 每次取剩下没排序的数中的最小数,然后,填到对应位置.(可以使用a[0]位置作为暂存单元) 如下: 二.实现程序 #include <iostream> using namespace std; const int maxSize = 100; template<class T> void SelectSort(T arr[], int n); // 选择排序 int main(int a

  • Java对数组实现选择排序算法的实例详解

    Java对数组实现选择排序算法的实例详解

    一. 算法描述     选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成. 以下面5个无序的数据为例: 56 12 80 91 20(文中仅细化了第一趟的选择过程) 第1趟:12 56 80 91 20 第2趟:12 20 80 91 56 第3趟:12 20 56 91 80 第4趟

  • Python实现冒泡，插入，选择排序简单实例

    本文所述的Python实现冒泡,插入,选择排序简单实例比较适合Python初学者从基础开始学习数据结构和算法,示例简单易懂,具体代码如下: # -*- coding: cp936 -*- #python插入排序 def insertSort(a): for i in range(len(a)-1): #print a,i for j in range(i+1,len(a)): if a[i]>a[j]: temp = a[i] a[i] = a[j] a[j] = temp return a #

  • java简单选择排序实例

    一.基本概念 每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止. 二.实现思路 从待排序序列中,找到关键字最小的元素: 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换: 从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1).(2)步,直到排序结束. 三.代码实现 public class SelectionSort { public static void selectionSort(int[] list){ //需要遍历获得

  • JAVA简单选择排序算法原理及实现

    简单选择排序:(选出最小值,放在第一位,然后第一位向后推移,如此循环)第一位与后面每一个逐个比较,每次都使最小的置顶,第一位向后推进(即刚选定的第一位是最小值,不再参与比较,比较次数减1) 复杂度: 所需进行记录移动的操作次数较少 0--3(n-1) ,无论记录的初始排列如何,所需的关键字间的比较次数相同,均为n(n-1)/2,总的时间复杂度为O(n2):空间复杂度 O(1) 算法改进:每次对比,都是为了将最小的值放到第一位,所以可以一比到底,找出最小值,直接放到第一位,省去无意义的调换移动操作

  • JS排序算法之冒泡排序，选择排序与插入排序实例分析

    本文实例讲述了JS排序算法之冒泡排序,选择排序与插入排序.分享给大家供大家参考,具体如下: 冒泡排序: 对数组的中的数据,依次比较相邻两数的大小. 如果前面的数据大于后面的数据,就交换这两个数. 时间复杂度O(n^2) function bubble(array){ var temp; for(var i=0; i<arr.length; i++){ for(var j=0; j<arr.length; j++){ if(arr[j]>arr[j+1]){ temp = arr[j+1]

  • Python排序搜索基本算法之选择排序实例分析

    Python排序搜索基本算法之选择排序实例分析

    本文实例讲述了Python排序搜索基本算法之选择排序.分享给大家供大家参考,具体如下: 选择排序就是第n次把序列中最小的元素排在第n的位置上,一旦排好就是该元素的绝对位置.代码如下: # coding:utf-8 def selectionSort(seq): length=len(seq) for i in range(length): mini=min(seq[i:]) if seq[i]>mini: j=seq.index(mini,i) seq[i],seq[j]=seq[j],seq[

  • Java排序算法之选择排序

    Java排序算法之选择排序

    一.选择排序 选择排序就是在每一次遍历过程中将数组中值最小的排到当前的第一位. 总共需要(数组长度-1)次遍历,在每次遍历中假定第一位索引的值为最小值,然后与下一个值对比,如果最小索引所在值大于其他值就将小的那一个索引当作最小值索引,接着继续对比最小索引所在值与下一个索引的值,重复此操作,最终就会在此次遍历中得到最小值及其索引,将最小值与第一位的值进行交换,这样就将最小值放到了数组开头,完成本次遍历. 选择排序的时间复杂度为O(N^2) 二.代码实现 package com.example.al

  • 手把手教你搞懂冒泡排序和选择排序

    手把手教你搞懂冒泡排序和选择排序

    目录 冒泡排序 原理: 选择排序 原理: 总结 冒泡排序 原理: 从头(左边)开始比较每一对相邻的元素,如果第1个比第2个大,就交换它们的位置,执行完一轮后,最末尾(最右边)就是最大的元素. 举例: 假设存在数组nums={6,8,2,9,4},对nums数组进行排序 从左往右开始,拿出两个元素进行对比,出现两种情况: 1.左边元素 <= 右边元素,不变 2.左边元素 > 右边元素,交换他们的位置(这里可以写成>=吗?不行,因为会造成排序不稳定) 接下来就是新的一轮排序,逻辑跟上图的流程

随机推荐