2011 年10 月 内 蒙 古 科 技 與 經 濟 O ctober 2011 第19 期 總第245 期 InnerM ongolia Science Technology & Economy No. 19 TotalNo. 245 基于Java 語言實作的直接選擇排序算法Ξ王素蘋 (内蒙古财經學院職業學院 計算機系, 内蒙古 呼和浩特 010000) 摘 要: 介紹了常用的排序算法, 詳細闡述了直接選擇排序算法, 最後給出基于Java 語言實作的直接選擇排序算法。 關鍵詞: 排序; 直接選擇排序; Java 語言 中圖分類号: TP312 文獻辨別碼:A 文章編号: 1007—6921 (2011) 19—0066—02 1 排序的基本概念 1. 1 什麼是排序? 排序就是把一組記錄按照其中的某個或某些關鍵字的大小遞增或遞減排列起來的操作。在排序過程中通常進行兩種操作: ①比較兩個關鍵字的大小; ②把記錄從一個位置移動到另外一個位置。 1. 2 排序算法的分類 排序算法按照是否涉及資料的内外存交換分為: 内排序算法和外排序算法。内排序算法是待排序的記錄個數比較少, 整個排序過程中所有的記錄都可以直接存放在記憶體中。外排序算法是待排序的記錄數量很大, 記憶體無法容納所有記錄, 排序過程中還需要通路外存[1]。筆者介紹的直接選擇排序算法屬于内排序算法。詳細的排序算法分類見圖1。 圖1 排序算法分類圖 2 直接選擇排序算法 2. 1 直接選擇排序的基本思想 直接選擇排序屬于選擇排序的一種。假設記錄為一組資料, 将資料進行升序即從小到大的順序排列, 下面介紹直接選擇排序算法的基本思想。降序排列與此相同。①首先在待排序的數中選擇最小的數, 将它放在第一個位置, 也就是将該數與第一個數進行位置交換; ②然後從剩下的數中選擇最小的數放 在第二個位置; 也就是将該數與第二個數進行位置交換; ③如此繼續⋯⋯; ④直到最後從剩下的兩個數中選擇最小的數放在倒數第二個位置, 最後一個數放在最後一個位置, 完成排序。 2. 2 如何找出一組數中的最小值? ——“打擂台” 法 在直接選擇排序算法中有一項工作就是找出一組數中的最小值(最大值) , 如何操作可以類比現實世界的“打擂台”。是以把這種找出一組資料中的最小值(最大值) 算法形象地稱為“打擂台”法。假設要找出8 個數中的最小數, 步驟如下: ①先将第一個數送上“擂台” ; ②其餘7 個數依次和“擂主”進行比較, 比第一個數小的就站在“擂台”上; ③最終站在台上的就是8 個數中的最小值。 2. 3 直接選擇排序算法的應用 給出一組資料45, 34, 78, 12, 34, 32, 29, 64, 用直接選擇排序算法進行升序排列。步驟如下: 第一步: 用“打擂台”法找出原始序列中的最小數即 12, 放在第一個位置, 也就是将 12 與第一個位置上的45 進行位置交換; 第二步: 繼續用“打擂台”法在剩餘的數中找出最小的數即 29, 放在第二個位置, 也就是将 29 與第二個位置上的34 進行位置交換; 第三步: 如此繼續⋯⋯, 最終完成排序。具體過程見圖2。 圖2 直接選擇排序算法的應用 ·66·Ξ收稿日期: 2011- 07- 30 王素蘋 · 基于Java 語言實作的直接選擇排序算法 2011 年第19 期 圖3 直接選擇排序流程 圖4 運作結果 2. 4 直接選擇排序算法分析 一個排序算法的性能可以從穩定性、時間複雜度和空間複雜度3 個方面來綜合考慮: ①穩定性。所有相等的