資訊專(zhuān)欄INFORMATION COLUMN
摘要：具體可參考我寫(xiě)的這一篇文章數(shù)據(jù)結(jié)構(gòu)與算法冒泡排序，今天來(lái)看看另外兩種基礎(chǔ)的排序算法選擇排序和插入排序。正因如此，選擇排序比起冒泡排序和插入排序就顯得遜色很多了。冒泡排序在交換數(shù)據(jù)的時(shí)候，需要進(jìn)行三次賦值操作，而插入排序只需要一次。
1. 回顧
前面說(shuō)到了冒泡排序，這是一種時(shí)間復(fù)雜度為 O(n2) 、是原地排序和穩(wěn)定的的排序算法，具體思路是：根據(jù)相鄰兩個(gè)元素之間比較大小，然后交換位置，得出最后排序的結(jié)果。具體可參考我寫(xiě)的這一篇文章：數(shù)據(jù)結(jié)構(gòu)與算法——冒泡排序，今天來(lái)看看另外兩種基礎(chǔ)的排序算法：選擇排序和插入排序。
2. 選擇排序
先來(lái)看看選擇排序，選擇排序的思路其實(shí)很簡(jiǎn)單，將排序的數(shù)據(jù)分為已排序區(qū)間和未排序區(qū)間，一般是以第一個(gè)元素為已排序區(qū)間，然后依次遍歷未排序區(qū)間，找到其最小值，和未排序區(qū)間的最后一個(gè)值進(jìn)行比較，交換位置。未排序區(qū)間遍歷完畢，則排序結(jié)束。光說(shuō)可能有點(diǎn)抽象，我畫(huà)了一張圖來(lái)幫助你理解：
是不是很簡(jiǎn)單呢？下面是它的代碼實(shí)現(xiàn)：
public class SelectionSort {
public static void selectionSort(int[] data){
int length = data.length;
//如果只有一個(gè)元素，或者數(shù)組為空，則直接退出
if (length <= 1) return;
for (int i = 0; i < length - 1; i++) {
int min = i + 1;
//找到最小值
for (int j = i + 1; j < length; j++) {
if (data[j] < data[min]) min = j;
}
//交換位置
if (data[min] < data[i]){
int temp = data[min];
data[min] = data[i];
data[i] = temp;
}
}
}
}
結(jié)合代碼分析，選擇排序在最好、最壞和平均情況下的時(shí)間復(fù)雜度都是 O(n2)，并且沒(méi)有借助額外的存儲(chǔ)空間，是一種原地排序算法。那么選擇排序是穩(wěn)定的嗎？答案是否定的，舉個(gè)例子：排序的數(shù)組為 data[2, 2, 1, 3, 5, 4, 8]，第一次遍歷未排序的數(shù)組，找到最小值為 1，和第一個(gè) 2 交換位置，那么這兩個(gè) 2 的前后順序就被打亂了，所以穩(wěn)定性被破壞。正因如此，選擇排序比起冒泡排序和插入排序就顯得遜色很多了。
3. 插入排序
我們?cè)賮?lái)看看插入排序，其實(shí)思路和上面的選擇排序非常的類(lèi)似，也是將排序數(shù)據(jù)分為已排序區(qū)間和未排序區(qū)間，依次遍歷未排序區(qū)間，和已排序區(qū)間的值進(jìn)行比較，將其插入到合適的位置上，直至將未排序的區(qū)間數(shù)據(jù)遍歷完。
你可以結(jié)合下面的圖來(lái)理解：
可以看到，和選擇排序一樣，將第一個(gè)數(shù)據(jù)作為已排序區(qū)間，第一次遍歷到 2 ，將其插入到 4 后面，然后再依次遍歷。
下面是代碼實(shí)現(xiàn)：
public class InsertionSort {
public static void insertionSort(int[] data){
int length = data.length;
if (length <= 1) return;
for (int i = 1; i < length; i++) {
int value = data[i];
int j = i - 1;
for (; j >= 0; j --){
if (data[j] > value) data[j + 1] = data[j];
else break;
}
data[j + 1] = value;
}
}
}
很顯然，插入排序也是穩(wěn)定的，因?yàn)槲覀兪窃?data[j] > da[j + 1] 的時(shí)候，才進(jìn)行數(shù)據(jù)交換，不會(huì)影響到相同元素的前后位置。并且，插入排序是原地排序，最好情況下，數(shù)組本來(lái)就是有序的，所以我們只需要遍歷一次數(shù)組就可以了，時(shí)間復(fù)雜度是 O(n)，最壞情況和平均情況下，時(shí)間復(fù)雜度都是 O(n2)。
最后還有個(gè)問(wèn)題，為什么在實(shí)際中，插入排序的比冒泡排序使用的更加廣泛呢？雖然這兩個(gè)排序算法的平均時(shí)間復(fù)雜度都是 O(n2)，但是結(jié)合代碼，不難發(fā)現(xiàn)，它們涉及到的數(shù)據(jù)交換操作時(shí)略有差別的。
冒泡排序在交換數(shù)據(jù)的時(shí)候，需要進(jìn)行三次賦值操作，而插入排序只需要一次。
//插入排序的賦值操作
for (; j >= 0; j --){
if (data[j] > value) data[j + 1] = data[j];
else break;
}
//冒泡排序的賦值操作
for (int j = 0; j < n - i - 1; j++) {
//如果data[j] > data[j + 1]，交換兩個(gè)數(shù)據(jù)的位置
if (data[j] > data[j + 1]){
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
在數(shù)據(jù)規(guī)模小的時(shí)候，這樣的差別沒(méi)什么影響，但是如果我們要排序的是一組較大的數(shù)據(jù)，那么兩種排序算法的執(zhí)行時(shí)間的差別就會(huì)很明顯了。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/73773.html
摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類(lèi)似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，...
摘要：筆者寫(xiě)的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語(yǔ)言是，旨在入門(mén)數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。這應(yīng)該是目前較為簡(jiǎn)單的十大經(jīng)典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經(jīng)典排序算法冒泡排序思想冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就...
摘要：下面會(huì)介紹的一種排序算法快速排序甚至被譽(yù)為世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一。我們將討論比較排序算法的理論基礎(chǔ)并中借若干排序算法和優(yōu)先隊(duì)列的應(yīng)用。為了展示初級(jí)排序算法性質(zhì)的價(jià)值，我們來(lái)看一下基于插入排序的快速的排序算法希爾排序。 前言 排序就是將一組對(duì)象按照某種邏輯順序重新排列的過(guò)程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計(jì)算時(shí)代早期，大家普遍...
摘要：代碼實(shí)現(xiàn)六堆排序算法簡(jiǎn)介堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。九計(jì)數(shù)排序算法簡(jiǎn)介計(jì)數(shù)排序是一種穩(wěn)定的排序算法。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。 贊助我以寫(xiě)出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡(jiǎn)介 插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀(guān)的排序算法。它...
閱讀 982·2023-04-25 23:54
閱讀 3059·2021-11-08 13:21
閱讀 3810·2021-09-27 13:35
閱讀 3408·2021-07-26 23:41
閱讀 1069·2019-08-30 15:52
閱讀 3456·2019-08-30 11:27
閱讀 2115·2019-08-29 18:37
閱讀 559·2019-08-29 17:24
