看動畫學算法之:排序-選擇排序
簡介
選擇排序就是從數組中選擇出來最大或者最小的元素，然後將其和隊首或者隊尾的元素進行交互。
因為首先做的是一個選擇的過程，所以叫做選擇排序。
選擇排序的例子
假如我們有一個數組：29,10,14,37,20,25,44,15，怎麼對它進行選擇排序呢？
先看一個動畫：
選擇排序的原理如下：
8個數字，我們需要進行7輪排序。
以第一輪為例，我們對對所有的數據進行比較，找到其中最小的那個10，然後把10放在數組的第一個。
當第二輪時，因為數組的第一個元素10已經排好序了，我們只需要從第二個位置開始就行了，同樣的，第二輪我們找到後面幾個元素中最小的那個14，將其放在數組的第二個位置。
以此類推進行7輪排序就得到了最後的結果。
選擇排序的java代碼實現
我們把上面的邏輯用java代碼實現如下：
public class SelectionSort {
public void doSelectionSort(int[] array){
log.info("排序前的數組為:{}",array);
//外層循環,遍歷所有輪數
for(int i=0; i< array.length-1; i++){
//內層循環，找出最小的那個數字
int minIndex=i;
for(int j=i+1;j<array.length;j++)
{
if(array[j] < array[minIndex])
{
minIndex = j;
}
}
//每次選擇完成後，將minIndex所在元素和第i個元素互換
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
log.info("第{}輪排序後的數組為:{}", i+1, array);
}
}
public static void main(String[] args) {
int[] array= {29,10,14,37,20,25,44,15};
SelectionSort selectionSort=new SelectionSort();
selectionSort.doSelectionSort(array);
}
}
運行結果：
選擇排序的第二種java實現
上面的代碼中，我們每次查找的是最小的那個元素，同樣的，我們也可以查找最大的那個元素。
public class SelectionSort1 {
public void doSelectionSort(int[] array){
log.info("排序前的數組為:{}",array);
//外層循環,遍歷所有輪數
for(int i=0; i< array.length-1; i++){
//內層循環，找出最大的那個數字
int maxIndex=0;
for(int j=0;j<array.length-i;j++)
{
if(array[j] > array[maxIndex])
{
maxIndex = j;
}
}
//每次選擇完成後，將maxIndex所在元素和length-i-1的元素互換
int temp = array[array.length-i-1];
array[array.length-i-1] = array[maxIndex];
array[maxIndex] = temp;
log.info("第{}輪排序後的數組為:{}", i+1, array);
}
}
public static void main(String[] args) {
int[] array= {29,10,14,37,20,25,44,15};
SelectionSort1 selectionSort=new SelectionSort1();
selectionSort.doSelectionSort(array);
}
}
運行結果：
兩種排序大家要注意內部循環的比較條件是不一樣的。
選擇排序的時間複雜度
選擇排序和冒泡排序一樣，都需要進行n*n的循環，所以其時間複雜度也是O(n²)。
本文的代碼地址：
本文已收錄於 //www.flydean.com/algorithm-selection-sort/
最通俗的解讀，最深刻的乾貨，最簡潔的教程，眾多你不知道的小技巧等你來發現！
歡迎關注我的公眾號:「程序那些事」,懂技術，更懂你！
