-
選擇排序
鎖定
- 最好複雜度
- O(n^2) [1]
- 最差複雜度
- O(n^2) [1]
- 方 法
- 通過比較 [1]
- 應用領域
- 計算機，數學 [1]
選擇排序選擇排序思路
選擇排序具體實現方法
②第1趟排序
設置一個變量i，讓i從0至n-2循環的同時，在對比數組中元素i跟元素i+1的大小，如果R[i+1]比R[i]小，則用一個變量k來記住他的位置（即k=i+1）。等到循環結束的時候，我們應該找到了R中最小的那個數的位置了。然後進行判斷，如果這個最小元素的不是R的第一個元素，就讓第一個元素跟他交換一下值，使R[0..0]和R[1..n-1]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
[1]
[2]
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[0..i-1]和R[i..n-1]。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[0..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
[1]
[2]
圖1 選擇排序（最小值）實例
選擇排序算法性能
選擇排序時間複雜度
選擇排序的交換操作介於 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值較小時，選擇排序比冒泡排序快。
[1]
[2]
選擇排序穩定性
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩餘元素裏面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那麼，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素後面，那麼交換後穩定性就被破壞了。舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中兩個5的相對前後順序就被破壞了，所以選擇排序是一個不穩定的排序算法。
[3]
選擇排序參考代碼
用C++實現選擇排序的偽代碼如圖2所示。
[4]
圖2 C++偽代碼實現選擇排序
import java.util.Arrays;
/*選擇排序*/
public class example2 {
public static void main(String[] args) {
int[] selectNums = {25, 63, 78, 45, 132, 7};
System.out.println("排序之前：" + Arrays.toString(selectNums));
selectSort(selectNums);
System.out.println("排序之後：" + Arrays.toString(selectNums));
}
public static void swap(int[]nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
public static void selectSort(int[] nums){
for(int i=0;i<nums.length-1;i++){
int temp=i;
for(int j=i+1;j<nums.length;j++){
if(nums[j]<nums[temp])
swap(nums,j,temp);
}
System.out.println("第"+i+"次排序："+Arrays.toString(nums));
}
}
}
Python3.8代碼
def selection_sort(data_sort_selection_list):
minimum_to_maximum = []while len(data_sort_selection_list) > 0:#次數minimum,
time = data_sort_selection_list[0],
for times in range(len(data_sort_selection_list)):#開始尋找最小值
if data_sort_selection_list[times] < minimum:#如果找到最小值
minimum = data_sort_selection_list[times]
time = times#查找最小值的位置
minimum_to_maximum.append(minimum)#添加最小值
del data_sort_selection_list[time]#刪除最小值
return minimum_to_maximumprint(selection_sort([4,6,2,3,3]))#輸出為[2, 3, 3, 4, 6]Go代碼
func SelectionSort(nums []int) []int {
length := len(nums)
var minIndex, tmp int
for i := 0; i < length-1; i++ {
minIndex = i
for j := i + 1; j < length; j++ {
if nums[j] < nums[minIndex] { // 尋找最小的數
minIndex = j // 將最小數的索引保存
}
}
tmp = nums[i]
nums[i] = nums[minIndex]
nums[minIndex] = tmp
}
return nums
}Javascript代碼
function selectionSort(arr) {
function swap(a, b) {
let temp = arr[b];
arr[b] = arr[a];
arr[a] = temp;
}
for (let i = 0; i < arr.length; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
swap(i, minIndex);
}
}- 參考資料
-
- 1. Ajay Kumar．Data Structure for C Programming：Firewall Media，2004：268-270
- 2. Hosam M.Mahmoud．Sorting: A Distribution Theory：John Wiley&Sons, Inc，2000：139-142
- 3. David R.Richardson．The Book on Data Structures, Volume 1：Writers Club Press，2002：44
- 4. Richard Neapolitan, Kumarss Namipour．Foundations of Algorithms Using C++ Pseudocode：Jones and Bartlett Publishers，1996：274
- 5. Java排序算法 ．CSDN[引用日期2022-11-09]
