基本介紹
- 中文名：選擇排序
- 外文名：Selection sort
- 性質：不穩定的排序方法
- 代表：PERL選擇排序算法
- 適用範圍：數據元素
- 方法：通過比較
- 套用領域：計算機，數學
基本選擇排序,思想,解釋,算法性能,時間複雜度,穩定性,樹形選擇排序,輸入輸出,思想,參考代碼,C語言,C#,C,c++,Java,JavaScript,Golang,Python,Pascal,Perl,php,Ruby,vb,
排序算法複雜度對比 lgn = log2n基本選擇排序
選擇排序輸出的是原序列的一個重排<a1*,a2*,a3*,...,an*>；，使得a1*<=a2*<=a3*<=...<=an*
排序算法有很多，包括插入排序，冒泡排序，堆排序，歸併排序，選擇排序，計數排序，基數排序，桶排序，快速排序等。插入排序，堆排序，選擇排序，歸併排序和快速排序，冒泡排序都是比較排序，它們通過對數組中的元素進行比較來實現排序，其他排序算法則是利用非比較的其他方法來獲得有關輸入數組的排序信息。
思想
n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
解釋
對比數組中前一個元素跟後一個元素的大小，如果後面的元素比前面的元素小則用一個變數k來記住他的位置，接著第二次比較，前面“後一個元素”現變成了“前一個元素”，繼續跟他的“後一個元素”進行比較如果後面的元素比他要小則用變數k記住它在數組中的位置(下標)，等到循環結束的時候，我們應該找到了最小的那個數的下標了，然後進行判斷，如果這個元素的下標不是第一個元素的下標，就讓第一個元素跟他交換一下值，這樣就找到整個數組中最小的數了。然後找到數組中第二小的數，讓他跟數組中第二個元素交換一下值，以此類推。
算法性能
時間複雜度
選擇排序的交換操作介於 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的相對前後順序就被破壞了，所以選擇排序是一個不穩定的排序算法。
樹形選擇排序
輸入輸出
輸入輸出與基本選擇排序相同。
思想
利用滿二叉樹的性質，將輸入的數據存放到滿二叉樹的葉節點，通過比較樹中剩餘可用節點（從底層的葉節點開始）的大小，每次選擇最小的數值（比較複製到二叉樹的頂端），並且把最小數值賦給排序數組的前端，把最小數值原來葉節點的位置設定為不可用；依次循環直至最後一個可用葉節點。
template class TreeNode{ public: T data; int index; int active; TreeNode & operator=(TreeNode & treenode) { this->data=treenode.data; this->index=treenode.index; this->active=treenode.active; return *this; } }; 樹節點數據結構包括了data數值，index用來存放該數值在葉節點存放的位置（所有數據開始都是存放在葉節點），active表示激活沒有，最後如果該數據移植樹根部，則將active欄位置0無效。參考代碼
C語言
/* 版本一 */#include<stdio.h>#include<stdlib.h>void swap(int*a,int*b){ int temp; temp=*a; *a=*b; *b=temp;}void select_sort(int A[],int n){ register int i,j,min,m; for(i=0;i<n-1;i++) { min=i;//查找最小值 for(j=i+1;j<n;j++) { if(A[min]>A[j]) { min=j; } } if(min!=i) { swap(&A[min],&A[i]); printf("第%d趟排序結果為:\n",i+1); for(m=0;m<n;m++) { if(m>0) { printf(""); } printf("%d",A[m]); } printf("\n"); } }}int main(void){ int n; while(scanf("%d",&n)!=EOF) /* VS2013等版本中需使用scanf_s()，VC6.0中使用scanf() */ { int i; int*A=(int*)malloc(sizeof(int)*n); for(i=0;i<n;i++) { scanf("%d",&A[i]); } select_sort(A,n); printf("最終排序結果為:\n"); for(i=0;i<n;i++) { if(i>0){ printf(""); } printf("%d",A[i]); } printf("\n"); } return 0;}/* 版本二 */#include <stdio.h>#include <math.h>#define MAX_SIZE 101#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))void sort(int[], int); /* selection sort */void main(void){ int i, n; int list[MAX_SIZE]; printf("Enter the number of numbers to generate: "); scanf_s("%d", &n); if (n < 1 || n > MAX_SIZE){ fprintf(stderr, "Improper value of n\n"); exit(1); } for (i = 0; i < n; i++){ /* randomly generate numbers */ list[i] = rand() * 1000; printf("%d ", list[i]); } sort(list, n); printf("\n Sorted array:\n"); for (i = 0; i < n; i++) /* print out sorted numbers */ printf("%d ", list[i]); printf("\n");}void sort(int list[], int n){ int i, j, min, temp; for (i = 0; i < n - 1; i++){ min = i; for (j = i + 1; j < n; j++) if (list[j] < list[min]) min = j; SWAP(list[i], list[min], temp); }}C#
static void sort(int[]group){ int temp; int pos=0; for(int i=0;i< group.Length-1;i++) { pos=i; for(intj=i+1;j<group.Length;j++) { if(group[j]<group[pos]) { pos=j; } }//第i個數與最小的數group[pos]交換 temp=group[i]; group[i]=group[pos]; group[pos]=temp; }}C
void select_sort(int*a,int n){ register int i,j,min,t; for(i=0;i<n-1;i++) { min=i;//查找最小值 for(j=i+1;j<n;j++) if(a[min]>a[j]) min=j;//交換 if(min!=i) { t=a[min]; a[min]=a[i]; a[i]=t; } }}c++
#include<iostream>#include<time.h>#include<iomanip>using namespace std;const int N=10;int main(){ int a[N],i,j,temp,b; srand(time(NULL)); for(i=0;i<N;i++) a[i]=rand()%100; for(i=0;i<N;i++) cout<<setw(3)<<a[i]; cout<<endl; for(i=0;i<N-1;i++) { temp=i; for(j=i+1;j<N;j++) { if(a[temp]>a[j]) temp=j; } if(i!=temp) { b=a[temp]; a[temp]=a[i]; a[i]=b; } } for(i=0;i<N;i++) cout<<setw(3)<<a[i]; cout<<endl;}選擇排序法的第一層循環從起始元素開始選到倒數第二個元素，主要是在每次進入的第二層循環之前，將外層循環的下標賦值給臨時變數，接下來的第二層循環中，如果發現有比這個最小位置處的元素更小的元素，則將那個更小的元素的下標賦給臨時變數，最後，在二層循環退出後，如果臨時變數改變，則說明，有比當前外層循環位置更小的元素，需要將這兩個元素交換.
Java
public static void selectSort(int[] a) { if((a == null) || (a.length == 0)) return ; for(int i = 0;i < a.length - 1;i ++){ int minIndex = i; // 無序區的最小數據數組下標 for(int j = i + 1;j < a.length;j ++){ // 在無序區中找到最小數據並保存其數組下標 if(a[j] < a[minIndex]){ minIndex = j; } } // 將最小元素放到本次循環的前端 int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; }}JavaScript
var arr = new Array(1, 3, 2, 8, 9, 1, 5);function SelectionSort(arr) { if (arr == null || arr.length < 2) { return arr; } for (var i = 0; i < (arr.length - 1); i++) { let minIndex = i; for (let j = i + 1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; } let temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr;}console.log(arr);SelectionSort(arr);console.log(arr);Golang
func SelectionSort(nums []int32) { length := len(nums) for i := 0; i < length; i++ { min := i for j := i + 1; j < length; j++ { if nums[j] < nums[min] { min = j } } temp := nums[i] nums[i] = nums[min] nums[min] = temp } fmt.Println(nums)}Python
def selection_sort(list2): for i in range(0, len (list2)-1): min_ = i for j in range(i + 1, len(list2)): if list2[j] < list2[min_]: min_ = j list2[i], list2[min_] = list2[min_], list2[i] # swap
Pascal
var num,temp,k,loop1,loop2:longint;a:array[1..1000] of longint;beginreadln(num);//讀入數據個數for loop1:=1to num doread(a[loop1]);//讀入進行排序的數據for loop1:=1to num-1 dobegink:= loop1;for loop2:=loop1+1to num doifa[k]>a[loop2]thenk:=loop2;//比較得出最小數ifk<>loop1then//最佳化節省時間begintemp:=a[k];a[k]:=a[loop1];a[loop1]:=temp;//進行數據交換end;end;forloop1:=1to num dowrite(a[loop1],'');//輸出排序後的數據readln;readln;end.
Perl
#!/usr/bin/perlsubselect_sort{ my(*array)=@_; $length=@array; for($i=0;$i<$length-1;$i++) { $min=$i; for($j=$i+1;$j<$length;$j++) { if($array[$j]<$array[$min]) { $min=$j; } if($min!=$i) { $temp=$array[$i]; $array[$i]=$array[$min]; $array[$min]=$temp; } } return@array; }php
function selection_sort($array){ $count=count($array); for($i=0;$i<$count-1;$i++){ /*findtheminest*/ $min=$i; echo'$min-->'.$array[$min].'-->'; for($j=$i+1;$j<$count;$j++){ //由小到大排列 if($array[$min]>$array[$j]){ //表明當前最小的還比當前的元素大 $min=$j; //賦值新的最小的 } } echo$array[$min].'coco<br/>'; /*swap$array[$i]and$array[$min]即將當前內循環的最小元素放在$i位置上*/ if($min!=$i){ $temp=$array[$min]; $array[$min]=$array[$i]; $array[$i]=$temp; } } return$array;}$old_array=array(3,4,5,6,8,2,12);$new_array=selection_sort($old_array);print_r($new_array);Ruby
def selection_sort(array) result = [] array.size.times { result << array.delete_at(array.index(array.min)) } resultendvb
vb實現選擇排序：
Private Sub xzPaiXu(a()AsDouble,shengAsBoolean)'a為需要排序的數組，sheng為True則為升序排列，為False，則為降序排列。Dim i AsInteger,j As IntegerDim temp As DoubleDimm As IntegerFor i = LBound(a) To UBound(a)-1'進行數組大小-1輪比較m=i'在第i輪比較時，假定第'i個元素為最值元素For j = i+1 To UBound(a)'在剩下的元素中找出最'值元素的下標並記錄在m中If sheng Then'若為升序，則m記錄最小元素'下標,否則記錄最大元素下標If a(j)<a(m) Thenm=jElse If a(j) > a(m) Thenm=jEnd IfNext j'將最值元素與第i個元素交換temp=a(i)a(i)=a(m)a(m)=tempNext iEnd Sub
排序算法複雜度對比 lgn = log2n