直接選擇排序(Straight Select Sorting) 也是一種簡單的排序方法，它的基本思想是：第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R[1]~R[n-1]中選取最小值，與R[1]交換，....，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，.....，第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。
基本介紹
- 中文名：直接選擇排序
- 外文名：Straight Selection Sort
- 基本思想：從R[0]~R[n-1]中選取最小值
- 算法實現：elem
- 效率分析：直接插入排序
基本思想,排序算法,實現,效率分析,
基本思想
例如:給定n=8，數組R中的8個元素的排序碼為(8,3,2,1,7,4,6,5),則直接選擇排序的過程如下所示
由於百科不方便畫出關聯箭頭 所以用 n -- n 表示 ：
初始狀態 [ 8 3 2 1 7 4 6 5 ] 8 -- 1
第一次 [ 1 3 2 8 7 4 6 5 ] 3 -- 2
第二次 [ 1 2 3 8 7 4 6 5 ] 3 -- 3
第三次 [ 1 2 3 8 7 4 6 5 ] 8 -- 4
第四次 [ 1 2 3 4 7 8 6 5 ] 7 -- 5
第五次 [ 1 2 3 4 5 8 6 7 ] 8 -- 6
第六次 [ 1 2 3 4 5 6 8 7 ] 8 -- 7
第七次 [ 1 2 3 4 5 6 7 8 ] 排序完成
排序算法
C++ 實現：
// elemtype 為所需排序的類型void SelectSort(elemtype R[], int n) { int i, j, m; elemtype t; for (i = 0; i < n - 1; i++) { m = i; for (j = i + 1; j < n; j++) if (R[j] < R[m]) m = j; if (m != i) { t = R[i]; R[i] = R[m]; R[m] = t; } }}C#實現：
private static void SelectionSort(int[] numbers, int length) { for (int i = 0; i < length - 1; i++) { int temp = i; for (int j = i + 1; j < length; j++) if (numbers[j] < numbers[temp]) temp = j; if (temp != i) Swap(numbers, i, temp); }}實現
python3實現：
# selectionSortdef findSmallest(arr): # 找出數組中最小元素的函式 smallest = arr[0] # 將arr數組中的第一個元素作為最小值的初始化值 smallest_index = 0 # 對應上行代碼，初始化存儲最小元素的索引 for i in range(1,len(arr)): # 從數組中第二個元素開始遍歷 if smallest > arr[i]: smallest = arr[i] smallest_index = i return smallest,smallest_indexdef selectionSort(arr): newArr = [] # 定義新生成數組的類型以及分配記憶體空間 for i in range(len(arr)): smallest,smallest_index = findSmallest(arr) newArr.append(smallest) # 將每次得到的最小元素加在數組後面 arr.pop(smallest_index) # 刪除原數組中已經被查找出來的最小元素 return newArr# 示例：arr = [3,4,7,1,9,3,0,5]newArr = selectionSort(arr)print("經過選擇排序算法排序過後的序列為：{0}".format(newArr))# 選擇排序後的序列為[0, 1, 3, 3, 4, 5, 7, 9]//為了使用Random類，需要加入如下這行：import java.util.*;/** * 直接選擇排序算法的Java實現。<br/> * 1：從a[0]-a[N-1]中選出最小的數據，然後與a[0]交換位置<br/> * 2：從a[1]-a[N-1]中選出最小的數據，然後與a[1]交換位置（第1步結束後a[0]就是N個數的最小值）<br/> * 3：從a[2]-a[N-1]中選出最小的數據，然後與a[2]交換位置（第2步結束後a[1]就是N-1個數的最小值）<br/> * 以此類推，N-1次排序後，待排數據就已經按照從小到大的順序排列了。<br/> * 此代碼作為課件提供給學生參考，在學完數組、循環、判斷後練習。<br/> * @author luo_wenqiang@126點com * @version 1.0.0 */public class 直接選擇排序{ public static void main(String[] args) { //聲明一個數組 int[] array = new int[10]; //為這個數組隨機填入整型數字 Random random = new Random(); for (int i = 0; i < array.length ; i++) { array[i] = random.nextInt(500); } System.out.print("原始數組 ："); System.out.println(Arrays.toString(array)); /**************************************** 下面開始正式的“直接選擇排序”算法 直接選擇排序的關鍵： 1：從a[0]-a[N-1]中選出最小的數據，然後與a[0]交換位置 2：從a[1]-a[N-1]中選出最小的數據，然後與a[1]交換位置（第1步結束後a[0]就是N個數的最小值） 3：從a[2]-a[N-1]中選出最小的數據，然後與a[2]交換位置（第2步結束後a[1]就是N-1個數的最小值） 以此類推，N-1次排序後，待排數據就已經按照從小到大的順序排列了。 ****************************************/ //N個數組元素，就需要循環N輪 for(int i = 0; i < array.length-1; i++){ //最小數的索引，該索引每次都根據外層循環的計數器來覺得初始值。 int minIndex = i; for (int j = i + 1; j < array.length; j++) { //根據最小數的索引，判斷當前這個數是否小於最小數。 //如果小於，則把當前數的索引作為最小數的索引。 //否則不處理。 if(array[minIndex] > array[j]){ minIndex = j; } //直到循環完成的時候，minIndex肯定就是當前這輪循環中，最小的那個。 } //System.out.print(i + "輪，最小數" + array[minIndex] + "，"); //System.out.print("原索引" + minIndex + "，新索引" + i); //得到最小數的索引後，把該索引對應的值放到最左邊，並且把最左邊的值放到索引所在的位置. //最左邊的值 int temp = array[i]; //把最小數索引對應的值放到最左邊 array[i] = array[minIndex]; //把原來最左邊對應的值放到最小數索引所在的位置 array[minIndex] = temp; System.out.println(String.format("%2s",(i + 1)) + "輪排序後：" + Arrays.toString(array)); } }}python 實現def select_sort(lists): print 'input lists: ', lists count = len(lists) - 1 for i in range(count): min_index = i for j in range(i+1, count): if lists[min_index] > lists[j]: min_index = j lists[min_index], lists[i] = lists[i], lists[min_index] print i+1, ' times, result is', lists return liststmp_b = [2, 6, 8, 1, 5, 21, 0, 5, 3, 7]select_sort(tmp_b)程式輸出為：input lists: [2, 6, 8, 1, 5, 21, 0, 5, 3, 7]#第一次， 2 和 0 的位置調換，最小的值放到列表的最左側1 times, result is [0, 6, 8, 1, 5, 21, 2, 5, 3, 7]#第二次， 1 和 6 的位置調換2 times, result is [0, 1, 8, 6, 5, 21, 2, 5, 3, 7]3 times, result is [0, 1, 2, 6, 5, 21, 8, 5, 3, 7]4 times, result is [0, 1, 2, 3, 5, 21, 8, 5, 6, 7]5 times, result is [0, 1, 2, 3, 5, 21, 8, 5, 6, 7]6 times, result is [0, 1, 2, 3, 5, 5, 8, 21, 6, 7]7 times, result is [0, 1, 2, 3, 5, 5, 6, 21, 8, 7]8 times, result is [0, 1, 2, 3, 5, 5, 6, 7, 8, 21]9 times, result is [0, 1, 2, 3, 5, 5, 6, 7, 8, 21]10 times, result is [0, 1, 2, 3, 5, 5, 6, 7, 8, 21]