前言
筆者屬于算法小白一枚，本系列文章屬于算法的學習筆記，也希望能給算法小小白起到些許的指引作用涡相。如果有算法大佬不小心點了進來，只能說一聲抱歉打擾了剩蟀。
正文
題目
請實現(xiàn)一個選擇排序催蝗，升序排列。
原理
- 在未排序隊列中找到最小元素育特，放在排序隊列的頭部丙号。
- 再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到已排序隊列的尾部缰冤。
- 重復第二步犬缨，直到所有元素均排序完畢。
實現(xiàn)
選擇排序需要兩層循環(huán)才能實現(xiàn)棉浸，個人建議先梳理清楚一層循環(huán)做了什么事情怀薛，得到了什么結果，最后再加上一層循環(huán)嵌套涮拗，思路會更清晰一些乾戏。
假設待排序的數(shù)組：[6, 4, 2, 1, 8, 3, 7, 9, 5]
我們在一層循環(huán)里面想要將最小的元素放在排序隊列的頭部，結合算法原理三热，不難寫出以下代碼：
public static void main(String[] args) {
int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
// 假設最小的元素索引是0
int minIndex = 0;
for (int j = 1; j < array.length; j++) {
// 找到了更小的元素鼓择，更新索引
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 將最小的元素放置在索引0
if (minIndex != 0) {
int tmp = array[minIndex];
array[minIndex] = array[0];
array[0] = tmp;
}
System.out.println(Arrays.toString(array));
}
得到數(shù)組：[1, 4, 2, 6, 8, 3, 7, 9, 5]
分析：
- 經(jīng)過一層循環(huán)，我們
選擇出了最小的元素就漾，并且將它放在了隊列頭部呐能。 - 接下來我們需要找到第二小的元素，將它放在隊列的第二個位置。
- 此時隊列頭部位置已經(jīng)放置了最小元素摆出，我們從第二個位置開始
選擇朗徊。
繼續(xù)寫代碼：
public static void main(String[] args) {
int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
// 假設最小的元素索引是0
int minIndex = 0;
for (int j = 1; j < array.length; j++) {
// 找到了更小的元素，更新索引
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 將最小的元素放置在索引0
if (minIndex != 0) {
int tmp = array[minIndex];
array[minIndex] = array[0];
array[0] = tmp;
}
// 假設最小的元素索引是1
minIndex = 1;
for (int j = 2; j < array.length; j++) {
// 找到了更小的元素偎漫，更新索引
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 將最小的元素放置在索引1
if (minIndex != 1) {
int tmp = array[minIndex];
array[minIndex] = array[1];
array[1] = tmp;
}
System.out.println(Arrays.toString(array));
}
得到數(shù)組：[1, 2, 4, 6, 8, 3, 7, 9, 5]
分析：
- 仔細觀察兩段代碼爷恳，不難發(fā)現(xiàn)：
- 當
minIndex = 0的時候，循環(huán)從 1 開始象踊，最終交換 minIndex 和 0 位置上的元素温亲。 - 當
minIndex = 1的時候，循環(huán)從 2 開始杯矩，最終交換 minIndex 和 1 位置上的元素栈虚。
- 當
- 可以推測：當
minIndex = i的時候，循環(huán)從 i+1 開始史隆，最終交換 minIndex 和 i 位置上的元素魂务。 - 那么我們最終需要進行多少次元素的
選擇呢？很簡單泌射，對9個元素排序粘姜，只需要進行8次即可。 - 就這樣魄幕，新的一層循環(huán)嵌套已經(jīng)呼之欲出了相艇。
int i = 0; i < array.length - 1; i++。
改進代碼：
public static void main(String[] args) {
int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
for (int i = 0; i < array.length - 1; i++) {
// 假設最小的元素索引是i
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
// 找到了更小的元素纯陨，更新索引
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 將最小的元素放置在索引i
if (minIndex != i) {
int tmp = array[minIndex];
array[minIndex] = array[i];
array[i] = tmp;
}
}
System.out.println(Arrays.toString(array));
}
到這里，一個完整的選擇排序就實現(xiàn)了留储。
總結
選擇排序是一個非常簡單的入門級排序翼抠，它具有如下特點:
- 時間復雜度是O(n2)，
- 空間復雜度是O(1)获讳。
- 是一個不穩(wěn)定排序阴颖。
請深入理解了它的實現(xiàn)以后，在純文本編輯的環(huán)境下手撕了它
