C++实现选择性排序（SelectionSort）

“选择性排序”是数列排序的算法之一。
其思路引点来源于经典的“可乐雪碧问题”

“现有两杯饮料，一杯是雪碧，一杯是可乐，试问如何可以将两杯饮料交换？”
“答：最简单的解决方案就是利用一个空杯，创造一个缓存区。”

选择性排序就是利用线性搜索数列并找到当前最小值，通过不断的将当前最小值放置当前位置索引的算法。

1、算法思路

这是一个未排序的数列。

首先，线性搜索数列，找到最小值。

将最小值替换为列中左端的数字并进行排序，如果最小值已经在左端，则不执行任何操作。

重复相同操作，直到所有的数字都被排序。

3、动画演示

4、代码清单及其测试结果

#include <iostream>
template <class T>

int getSizeOfArray(T& ss){
 return sizeof(ss)/ sizeof(ss[0]);
}

void selectionSort(int * ss,int size){
 for(int i=0;i<size-1;i++){
 int minimalIndex = i;//初始化当前范围内最小值索引
 for(int j=i+1;j<size;j++){//查找当前范围内最小值索引
  if(ss[j]<ss[minimalIndex]){
  minimalIndex = j;
  }
 }
 if(minimalIndex!=i){//如果当前范围内最小值索引不为初始化索引，才进行交换
  int cup = 0;
  cup = ss[i];
  ss[i] = ss[minimalIndex];
  ss[minimalIndex] = cup;
 }
 }
}

int main() {
 using namespace std;

 int ss[] = {2,3,5,1,0,8,6,9,7};
 int size = getSizeOfArray(ss);

 cout<< "原数列:";

 for(int i = 0;i<size;i++)
 {
 cout<< ss[i] << " ";
 }

 cout<< "\n" << "选择性排序后:";

 selectionSort(ss,size);

 for(int i = 0;i<size;i++)
 {
 cout<< ss[i] << " ";
 }

 return 0;
}

6. 算法分析

时间复杂度

选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。
比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+…+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。 [1]

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

赞 (0)

相关推荐

  • C++冒泡排序算法实例

    冒泡排序 大学学习数据结构与算法最开始的时候,就讲了冒泡排序:可见这个排序算法是多么的经典.冒泡排序是一种非常简单的排序算法,它重复地走访过要排序的数列,每一次比较两个数,按照升序或降序的规则,对比较的两个数进行交换.比如现在我要对以下数据进行排序: 10 3 8 0 6 9 2 当使用冒泡排序进行升序排序时,排序的步骤是这样的: 3 10 8 0 6 9 2  // 10和3进行对比,10>3,交换位置 3 8 10 0 6 9 2  // 10再和8进行对比,10>8,交换位置 3 8 0

  • 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

  • C++实现冒泡排序（BubbleSort）

    本文实例为大家分享了C++实现冒泡排序的具体代码,供大家参考,具体内容如下 一.思路: 冒泡排序算法原理: 1.比较相邻的元素.如果第一个数比第二个数大,就交换他们两个. 2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 3.针对所有的元素重复以上的步骤,除了最后一个.(因为最后一个已经排好,是最大的数) 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.(接着排第二大的数,一直下去) 如:使用冒泡排序:25 16 9

  • C++ 关于STL中sort()对struct排序的方法

    C++ 关于STL中sort()对struct排序的方法

    前言 一直没有系统去看过c++,因为懂得一些c的基本语法,在实际编程中用到c++,只能用到哪些看哪些,发现这样虽然能够完成大部分工作,但是有时候效率实在太低,比如说这节要讲的Std::sort()函数的使用,调了半天才调通.开通c/c++序列博客是记录在使用c++中一些难题,避免以后重犯错,当然以后会尽量挤出时间来较系统学习下c++. 开发环境:QtCreator2.5.1+OpenCV2.4.3 实验基础 首先来看看std中的快速排序算法sort的使用方法: template <class R

  • C++归并排序算法实例

    归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std;   //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int

  • C++实现折半插入排序（BinaryInsertSort）

    本文实例为大家分享了C++实现折半插入排序的具体代码,供大家参考,具体内容如下 一.思路: 较插入排序,减少了比较的次数,但是插入时间还是一样. (1)按二分查找的方法,查找V[i]在V[0],V[1]-V[i-1]中插入的位置: (2)将插入位置的元素向后顺移. 二.实现程序: // 二分插入:较插入排序,减少了比较的次数,但是插入时间还是一样 // 时间复杂度还是:O(n*n) #include <iostream> using namespace std; const int maxSi

  • C++堆排序算法的实现方法

    C++堆排序算法的实现方法

    本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

  • C++实现希尔排序（ShellSort）

    本文实例为大家分享了C++实现希尔排序的具体代码,供大家参考,具体内容如下 一.思路: 希尔排序:又称缩小增量排序,是一种改进的插入排序算法,是不稳定的. 设排序元素序列有n个元素,首先取一个整数gap<n作为间隔,将全部元素分为gap个子序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别施行直接插入排序.然后缩小间隔gap,重复上述的子序列和排序工作. 二.实现程序: #include <iostream> using namespace std; const int

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

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

  • C++实现归并排序（MergeSort）

    本文实例为大家分享了C++实现归并排序的具体代码,供大家参考,具体内容如下 一.思路:稳定排序 (1)划分:一直调用划分过程,直到子序列为空或只有一个元素为止,共需log2(n): (2)归并:将两个子序列从小到大合并为一个序列 二.实现程序: // 归并排序:(二路归并) // (1)递归分解数组: // (2)合并有序的序列 #include <iostream> using namespace std; // 合并两个有序的序列 template <typename T> v

随机推荐