簡單選擇排序

tylin 發布于2019-08-14 15:11 / 2845人閱讀

摘要：因為每一趟確定元素的過程中都會有一個選擇最大值的子流程，所以人們形象地稱之為選擇排序。選擇排序的時間復雜度和空間復雜度分別為和。

概述

在要排序的一組數中，選出最小的一個數與第1個位置的數交換；然后在剩下的數當中再找最小的與第2個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最后一個數）比較為止。

換句話說：

以 i 代表當前需要排序的序號，則需要在剩余的 [i... n-1] 中找出其中的最小值，然后將找到的最小值與 i 指向的值進行交換。因為每一趟確定元素的過程中都會有一個選擇最大值的子流程，所以人們形象地稱之為選擇排序。選擇排序的時間復雜度和空間復雜度分別為 O(n²) 和 O(1) 。

直觀釋義圖：

步驟

從n 個記錄中找出關鍵碼最小的記錄與第一個記錄交換

從第2 個記錄開始的 n-1 個記錄中再選出最小的記錄與第2 個記錄交換

從第i (i是不斷+1的)個記錄開始的 n-i+1 個記錄中選出最小的與第i 個記錄交換

直到整個序列有序

實例

原始數據：

3 5 2 6 2

第一輪，找出 [5 2 6 2] 中最小的第三個位置 2 ，與第一個位置 3 進行交換

2 5 3 6 2

第二輪，找出 [3 6 2] 中最小的 2 與第一輪中第二個位置 5 進行交換

2 2 3 6 5

第三輪，找出 [6 5] 中最小的 5 與第二輪中第三個位置 3 不需交換

2 2 3 6 5

第四輪，找出 [5] 中最小的 5 與第三輪中的第四個位置 6 進行交換

2 2 3 5 6

第五輪，沒有了，最終結果

2 2 3 5 6

簡單選擇排序也可以認為是穩定的排序。

代碼實現(Java)

package com.coder4j.main.arithmetic.sorting;
    
public class SimpleSelection {

    /**
     * 簡單選擇排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.println("第" + (i + 1) + "輪比較結果：");
            int minPosition = i;
            // 找出i之后的數組中的最小索引
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minPosition]) {
                    minPosition = j;
                }
            }
            // 判斷是否需要調換位置
            if (array[i] > array[minPosition]) {
                int temp = array[i];
                array[i] = array[minPosition];
                array[minPosition] = temp;
            }
            // 輸出此輪排序結果
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最終結果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }
}

測試輸出結果：

第1輪比較結果：
2 5 3 6 2 
第2輪比較結果：
2 2 3 6 5 
第3輪比較結果：
2 2 3 6 5 
第4輪比較結果：
2 2 3 5 6 
第5輪比較結果：
2 2 3 5 6 
最終結果
2 2 3 5 6

經測試，與實例中結果一致。

GPU云服務器云服務器最簡單的排序算法簡單的c語言排序選擇排序選擇排序法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65415.html

選擇排序就這么簡單

摘要：選擇排序就這么簡單從上一篇已經講解了冒泡排序了，本章主要講解的是選擇排序，希望大家看完能夠理解并手寫出選擇排序的代碼，然后就通過面試了如果我寫得有錯誤的地方也請大家在評論下指出。選擇排序就這么簡單從上一篇已經講解了冒泡排序了，本章主要講解的是選擇排序，希望大家看完能夠理解并手寫出選擇排序的代碼，然后就通過面試了！如果我寫得有錯誤的地方也請大家在評論下指出。選擇排序介紹和穩定性說明...

wua_wua2012 2019-08-15 14:50 評論0 收藏0
數據結構與算法（三）：帶你讀懂選擇排序（Selection sort）

摘要：基本介紹選擇式排序也屬于內部排序法，是從欲排序的數據中，按指定的規則選出某一元素，再依規定交換位置后達到排序的目的。而移動次數與序列的初始排序有關?？臻g復雜度簡單選擇排序需要占用個臨時空間，在交換數值時使用。 showImg(https://img-blog.csdnimg.cn/20190509221741422.gif); showImg(https://segmentfault....

Kaede 2019-08-16 18:24 評論0 收藏0
【算法日積月累】1-選擇排序

摘要：選擇排序算法實現實現選擇排序，記錄最小元素的索引，最后才交換位置說明交換兩個數組中的元素，在中有更簡單的寫法，這是的語法糖，其它語言中是沒有的。和語言中比較器的實現前面我們說到了，我們為了突出排序算法的思想，將所有的例子僅限在數組排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

neuSnail 2019-07-31 11:21 評論0 收藏0
Github標星2w+，熱榜第一，如何用Python實現所有算法

摘要：歸并排序歸并排序，或，是創建在歸并操作上的一種有效的排序算法，效率為大符號。以此類推，直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的，因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯：周素云、蔣寶尚學會了Python基礎知識，想進階一下，那就來點算法吧！畢竟編程語言只...

zxhaaa 2019-07-31 10:23 評論0 收藏0
排序算法（Java）——那些年面試常見的排序算法

摘要：下面會介紹的一種排序算法快速排序甚至被譽為世紀科學和工程領域的十大算法之一。我們將討論比較排序算法的理論基礎并中借若干排序算法和優先隊列的應用。為了展示初級排序算法性質的價值，我們來看一下基于插入排序的快速的排序算法希爾排序。前言　　排序就是將一組對象按照某種邏輯順序重新排列的過程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計算時代早期，大家普遍...

Harpsichord1207 2019-08-15 14:50 評論0 收藏0