八大排序算法詳解——選擇排序

2019-11-10 17:00:44

字體：大中小

來源：轉載

供稿：網友

基本思想

n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：

初始狀態：無序區為R[1..n]，有序區為空。第1趟排序：在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1] 交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區?！趇趟排序：第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[i]交換，使R[1..i] 和R[i+1..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。

算法實現

直接選擇排序算法，java實現，代碼如下所示：

public abstract class Sorter { public abstract void sort(int[] array); } public class StraightSelectionSorter extends Sorter { @Override public void sort(int[] array) { int tmp; // 用于交換數據的暫存單元 for (int i = 0; i < array.length - 1; i++) { // 這里只要從0~array.length-2即可 int k = i; for (int j = i + 1; j < array.length; j++) { // 該循環可以找到右側無序區最小的元素array[k] if (array[k] > array[j]) { k = j; } } if (k != i) { // 如果array[i]不是無序區最小的，需要與無序區最小的進行交換 tmp = array[i]; array[i] = array[k]; array[k] = tmp; } // 如果array[i]是無序區最小的元素，不需要執行交換 } } }

排序過程

首先，從0~n-1個元素中找到最小的元素，交換到0位置上；其次，再從1~n-1中找到次最小的元素，交換到1位置上；……；最后從n-2~n-1中找到最小的元素，交換到n-2位置上。n-1位置上一定是最大的元素，所以總共進行n-1趟選擇排序。需要注意的是：每次確定無序區后，其中除了第一個元素之外的其它元素（設為e）與第一個元素（設為E）比較，只有滿足e<E的時候才需要交換一次。

排序過程示例如下：假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20。

第1趟選擇排序

從array[1,n-1]中找到最小的元素：array[0] = 94>array[1] = 12，交換array[0]與array[1]，即array[0] = 12array[2] = 34不成立，不交換；array[0] = 12>array[3] = 76不成立，不交換；array[0] = 12>array[4] = 26不成立，不交換；array[0] = 12>array[5] = 9，交換array[0]與array[5]，即array[0] = 9array[6] = 0，交換array[0]與array[6]，即array[0] = 0array[7] = 37不成立，不交換；array[0] = 0>array[8] = 55不成立，不交換；array[0] = 0>array[9] = 76不成立，不交換；array[0] = 0>array[10] = 37不成立，不交換；array[0] = 0>array[11] = 5不成立，不交換；array[0] = 0>array[12] = 68不成立，不交換；array[0] = 0>array[13] = 83不成立，不交換；array[0] = 0>array[14] = 90不成立，不交換；array[0] = 0>array[15] = 37不成立，不交換；array[0] = 0>array[16] = 12不成立，不交換；array[0] = 0>array[17] = 65不成立，不交換；array[0] = 0>array[18] = 76不成立，不交換；array[0] = 0>array[19] = 49不成立，不交換。此時數組狀態如下：{0,94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49}。此時，有序區為{0}，無序區為{94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49}。

第2趟選擇排序

從array[2,n-1]中找到最小的元素：array[1] = 94>array[2] = 34，交換array[1]與array[2]，即array[1] = 34array[3] = 76不成立，不交換；array[1] = 34>array[4] = 26，交換array[1]與array[4]，即array[1] = 26array[5] = 12，交換array[1]與array[5]，即array[1] = 12array[6] = 9，交換array[1]與array[6]，即array[1] = 9array[7] = 37不成立，不交換；array[1] = 0>array[8] = 55不成立，不交換；array[1] = 0>array[9] = 76不成立，不交換；array[1] = 0>array[10] = 37不成立，不交換；array[1] = 9>array[11] = 5，交換array[1]與array[11]，即array[1] = 5array[12] = 68不成立，不交換；array[1] = 5>array[13] = 83不成立，不交換；array[1] = 5>array[14] = 90不成立，不交換；array[1] = 5>array[15] = 37不成立，不交換；array[1] = 5>array[16] = 12不成立，不交換；array[1] = 5>array[17] = 65不成立，不交換；array[1] = 5>array[18] = 76不成立，不交換；array[1] = 5>array[19] = 49不成立，不交換。此時數組狀態如下：{0,5,94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。此時，有序區為{0,5}，無序區為{94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。

第3趟選擇排序

排序后數組狀態為：{0,5,9,94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。此時，有序區為{0,5,9}，無序區為{94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。

第4趟選擇排序

排序后數組狀態變化：{0,5,9,76,94,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}，{0,5,9,34,94,76,26,37,55,76,37,12,68,83,90,37,12,65,76,49}，{0,5,9,26,94,76,34,37,55,76,37,12,68,83,90,37,12,65,76,49}，{0,5,9,12,94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}，{0,5,9,12,94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}，此時，有序區為{0,5,9,12}，無序區為{94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}。……

第n-1趟選擇排序

依此類推，執行n-1趟選擇排序，最后得到：有序區為{0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90}，無序區為{94}，此時整個數組已經有序，n-1趟選擇排序后，排序完成。

算法分析

時間復雜度記錄比較次數：

無論待排序數組初始狀態如何，都要進行n-1趟選擇排序：

第1趟：比較n-1次；第2趟：比較n-2次；……第n-1趟：比較1次。

從而，總共的比較次數為：1+2+……+(n-1) = n(n-1)/2

記錄移動次數：

如果待排序數組為正序，則記錄不需要交換，記錄移動次數為0；如果當排序數組為逆序，則：

第1趟：交換1次，移動3次；第2趟：交換1次，移動3次；……第n-1趟：交換1次，移動3次。

從而，總共的移動次數為：3(n-1) = 3(n-1)。因此，時間復雜度為O(n2)。

空間復雜度