什麼是選擇排序
選擇排序是一種排序算法，時間複雜度簡單可以記為 O(n x n) ，算法靈巧但速度不是很快
大體思路：遍歷數組，每次取出遍歷數組中最小值放到結果數組中，同時數組縮容去除遍歷數組中最小值，繼續遍歷
即，取最小值放結果數組中 -> 縮容去最小 -> 重複第一步
選擇排序的步驟
給定數組
創建一個與原數組等長的結果數組
使用兩個變量分別記錄數組中的最小值與最小值座標
取原數組中第一個值與其他元素比較，如果被比較值小於當前最小值則替換最小值為當前值，反之繼續遍歷
遍歷完成返回當前數組最小值的下標，將原數組中的最小值放到結果數組的第一位，第一次遍歷得到2
接下來需要去除給定數組中的最小值，縮小數組，第二次遍歷得到3
每次遍歷縮小後的數組，找出最小值放到結果數組中，再次縮小上次縮小過的數組，直到將結果數組填滿
最後得到結果數組
Java實現
package com.github.hellxz.grokkingalgorithms.selectionsort;/** * 選擇排序 */public class SelectionSort { public static int[] selectionSort(int[] arr) { //創建結果數組 int[] solution = new int[arr.length]; for (int i = 0; i < solution.length; i++) { //獲得當前arr最小值下標 int smallestIndex = findSmallestIndex(arr); //將當前arr最小值放到結果數組 solution[i] = arr[smallestIndex]; //arr縮容，去除最小值 arr = newArrayWithoutLastSmallest(arr, smallestIndex); } return solution; } /** * 返回去掉給定值的新數組 */ private static int[] newArrayWithoutLastSmallest(int[] arr, int lastSmallestIndex) { int[] newArr = new int[arr.length - 1]; for (int i = 0; i < arr.length; i++) { if (i < lastSmallestIndex) { newArr[i] = arr[i]; } else if(i > lastSmallestIndex) { newArr[i-1] = arr[i]; } } return newArr; } /** * 查找給定數組最小值下標 */ private static int findSmallestIndex(int[] arr) { int smallest = arr[0]; int smallestIndex = 0; for (int i = 0; i < arr.length; i++) { if (smallest > arr[i]) { smallest = arr[i]; smallestIndex = i; } } return smallestIndex; } public static void main(String[] args) { int[] arr = {8, 6, 7, 5, 3, 2, 4}; int[] sortedArr = selectionSort(arr); for (int i = 0; i < sortedArr.length; i++) { System.out.print(sortedArr[i]); } }}分享到:
閱讀更多 sandag 的文章
