點擊上面↑「
愛開發
」關注我們
每晚10點，捕獲技術思考和創頁澩洞察
面試時，演算法經常會遇到，特別是一些常見的演算法，
張工畢業3年了，一直在一家創業公司做java開發，最近到某知名互聯網公司面試，做了筆試題后，面試官看了覺得還不錯，于是想進一步考察張工的編碼能力，就讓他手寫選擇排序演算法，張工寫不出來，面試官說：你都畢業3年了，連個選擇排序法都寫不出來，
我參加計算機等級考試就會這個了
，
張工一臉的無助，不過確實不應該，類似選擇排序這樣基礎的演算法，平時應該要掌握好才對，
小編之前參加的筆試也遇到了手寫排序演算法的情況，關于選擇排序可能基本都能寫出來，但要是能把程式再優化一下，那就更好了，相信能給面試官留下更好的印象，
我們先來看什么選擇排序法：
選擇排序法是一種
不穩定
的排序演算法，它的作業原理是每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，以此類推，直到全部待排序的資料元素排完，
穩定性
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了，那么，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了，
舉個例子，序列6 8 6 3 9，我們知道第一遍選擇第1個元素6會和3交換，那么原序列中兩個6的相對前后順序就被破壞了，所以選擇排序是一個不穩定的排序演算法，
關于時間復雜度
選擇排序的交換操作介于 0 和 (n - 1） 次之間，選擇排序的比較操作為 n (n - 1） / 2 次之間，選擇排序的賦值操作介于 0 和 3 (n - 1） 次之間，比較次數O(n^2），比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1）+(n-2）+...+1=n*(n-1）/2，交換次數O(n），最好情況是，已經有序，交換0次；最壞情況交換n-1次，逆序交換n/2次，交換次數比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快，其中直接選擇排序的時間復雜度為O（n*n），空間復雜度為O（1），樹形選擇排序的時間復雜度為O（nlog2n），空間復雜度為O（n），堆排序的平均時間復雜度為O（nlog2n），效率高，但是實作相對復雜，空間代價為O（1），
我們來看用java撰寫的選擇排序演算法代碼
/**
* 選擇排序
*
* @param arr
*/
public static void selectionSort(int[] arr) {
int min;
int length = arr.length;
for ( int i = 0; i < length; i++) {
// 初始化未排序序列中最小資料陣列下標
min = i;
for ( int j = i + 1; j < length; j++) {
// 在未排序元素中繼續尋找最小元素，并保存其下標
if (arr[j] < arr[min]) {
min = j;
}
}
// 將未排序列中最小元素放到已排序列末尾
if (min != i) {
swap(min, i, arr);
}
}
}
/**
* 交換順序
*
* @param x
* @param y
* @param arr
*/
private static void swap(int x, int y, int[] arr) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
* 選擇排序
*
* @param arr
*/
public static void selectionSort(int[] arr) {
int min;
int length = arr.length;
for ( int i = 0; i < length; i++) {
// 初始化未排序序列中最小資料陣列下標
min = i;
for ( int j = i + 1; j < length; j++) {
// 在未排序元素中繼續尋找最小元素，并保存其下標
if (arr[j] < arr[min]) {
min = j;
}
}
// 將未排序列中最小元素放到已排序列末尾
if (min != i) {
swap(min, i, arr);
}
}
}
/**
* 交換順序
*
* @param x
* @param y
* @param arr
*/
private static void swap(int x, int y, int[] arr) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
呼叫實體
public static void main(String[] args) {
int arr[] = { 2, 17, 2, 11, 7, 6, 19, 9, 14, 20, 17, 13, 14, 2, 10};
System.out.println(String.format( "original array = %s\n", Arrays.toString(arr)));
selectionSort(arr);
System.out.println(String.format( "sorted array = %s\n", Arrays.toString(arr)));
}
int arr[] = { 2, 17, 2, 11, 7, 6, 19, 9, 14, 20, 17, 13, 14, 2, 10};
System.out.println(String.format( "original array = %s\n", Arrays.toString(arr)));
selectionSort(arr);
System.out.println(String.format( "sorted array = %s\n", Arrays.toString(arr)));
}
輸出結果
對于選擇排序演算法，要是還是不太好理解，我們來看一下影片圖，這樣會更容易理解些，
不知你對選擇排序演算法是否完全理解，
選擇排序法基本來說還是挺不錯的，資料規模不大時，還是推薦使用的，但相對于其他的排序演算法（譬如快速排序）效率還是明顯有些不足，
小編認為，關于選擇排序法思想還是挺重要，要重視，
-END-
往期精選推薦
更關注精彩內容，請長按識別關注
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/303998.html
標籤：其他