C++實(shí)現(xiàn)選擇性排序（SelectionSort）

更新時間：2020年04月26日 09:56:39 作者：kevinmeanscool

這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)選擇性排序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

“選擇性排序”是數(shù)列排序的算法之一。
其思路引點(diǎn)來源于經(jīng)典的“可樂雪碧問題”

“現(xiàn)有兩杯飲料，一杯是雪碧，一杯是可樂，試問如何可以將兩杯飲料交換？”
“答：最簡單的解決方案就是利用一個空杯，創(chuàng)造一個緩存區(qū)。”

選擇性排序就是利用線性搜索數(shù)列并找到當(dāng)前最小值，通過不斷的將當(dāng)前最小值放置當(dāng)前位置索引的算法。

1、算法思路

這是一個未排序的數(shù)列。

首先，線性搜索數(shù)列，找到最小值。

將最小值替換為列中左端的數(shù)字并進(jìn)行排序，如果最小值已經(jīng)在左端，則不執(zhí)行任何操作。

重復(fù)相同操作，直到所有的數(shù)字都被排序。

3、動畫演示

4、代碼清單及其測試結(jié)果

#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;//初始化當(dāng)前范圍內(nèi)最小值索引
 for(int j=i+1;j<size;j++){//查找當(dāng)前范圍內(nèi)最小值索引
  if(ss[j]<ss[minimalIndex]){
  minimalIndex = j;
  }
 }
 if(minimalIndex!=i){//如果當(dāng)前范圍內(nèi)最小值索引不為初始化索引，才進(jìn)行交換
  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<< "原數(shù)列:";

 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. 算法分析

時間復(fù)雜度

選擇排序的交換操作介于 0 和 (n - 1）次之間。選擇排序的比較操作為 n (n - 1） / 2 次之間。選擇排序的賦值操作介于 0 和 3 (n - 1）次之間。
比較次數(shù)O(n^2），比較次數(shù)與關(guān)鍵字的初始狀態(tài)無關(guān)，總的比較次數(shù)N=(n-1）+(n-2）+…+1=n*(n-1）/2。交換次數(shù)O(n），最好情況是，已經(jīng)有序，交換0次；最壞情況交換n-1次，逆序交換n/2次。交換次數(shù)比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。

穩(wěn)定性

選擇排序是給每個位置選擇當(dāng)前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因?yàn)橹皇Ｏ滤粋€最大的元素了。那么，在一趟選擇，如果一個元素比當(dāng)前元素小，而該小的元素又出現(xiàn)在一個和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前后順序就被破壞了，所以選擇排序是一個不穩(wěn)定的排序算法。 [1]

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: