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

2019-11-10 17:44:54

字體：大中小

供稿：網(wǎng)友

基本思想

n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：

初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空。第1趟排序：在無(wú)序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R[1] 交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)。……第i趟排序：第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R[i]交換，使R[1..i] 和R[i+1..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)。

這樣，n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。

算法實(shí)現(xiàn)

直接選擇排序算法，java實(shí)現(xiàn)，代碼如下所示：

public abstract class Sorter { public abstract void sort(int[] array); } public class StraightSelectionSorter extends Sorter { @Override public void sort(int[] array) { int tmp; // 用于交換數(shù)據(jù)的暫存單元 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++) { // 該循環(huán)可以找到右側(cè)無(wú)序區(qū)最小的元素array[k] if (array[k] > array[j]) { k = j; } } if (k != i) { // 如果array[i]不是無(wú)序區(qū)最小的，需要與無(wú)序區(qū)最小的進(jìn)行交換 tmp = array[i]; array[i] = array[k]; array[k] = tmp; } // 如果array[i]是無(wú)序區(qū)最小的元素，不需要執(zhí)行交換 } } }

排序過程

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

排序過程示例如下：假設(shè)待排序數(shù)組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數(shù)組大小為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不成立，不交換。此時(shí)數(shù)組狀態(tài)如下：{0,94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49}。此時(shí)，有序區(qū)為{0}，無(wú)序區(qū)為{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不成立，不交換。此時(shí)數(shù)組狀態(tài)如下：{0,5,94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。此時(shí)，有序區(qū)為{0,5}，無(wú)序區(qū)為{94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。

第3趟選擇排序

排序后數(shù)組狀態(tài)為：{0,5,9,94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。此時(shí)，有序區(qū)為{0,5,9}，無(wú)序區(qū)為{94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。

第4趟選擇排序

排序后數(shù)組狀態(tài)變化：{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}，此時(shí)，有序區(qū)為{0,5,9,12}，無(wú)序區(qū)為{94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}。……

第n-1趟選擇排序

依此類推，執(zhí)行n-1趟選擇排序，最后得到：有序區(qū)為{0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90}，無(wú)序區(qū)為{94}，此時(shí)整個(gè)數(shù)組已經(jīng)有序，n-1趟選擇排序后，排序完成。

算法分析

時(shí)間復(fù)雜度記錄比較次數(shù)：

無(wú)論待排序數(shù)組初始狀態(tài)如何，都要進(jìn)行n-1趟選擇排序：

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

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

記錄移動(dòng)次數(shù)：

如果待排序數(shù)組為正序，則記錄不需要交換，記錄移動(dòng)次數(shù)為0；如果當(dāng)排序數(shù)組為逆序，則：

第1趟：交換1次，移動(dòng)3次；第2趟：交換1次，移動(dòng)3次；……第n-1趟：交換1次，移動(dòng)3次。

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

空間復(fù)雜度

在選擇排序的過程中，設(shè)置一個(gè)變量用來交換元素，所以空間復(fù)雜度為O(1)。

排序穩(wěn)定性