本篇文章主要介紹的是Java和Android開發(fā)中常見的排序概念，由于篇幅的問題我將其分成了幾篇。主要有基礎(chǔ)篇和實(shí)戰(zhàn)篇。本篇主要學(xué)習(xí)的是基礎(chǔ)排序的內(nèi)容，主要學(xué)習(xí)以下四種基礎(chǔ)排序：冒泡排序、選擇排序、插入排序。
冒泡排序：
對于冒泡排序，我們不是很陌生，因?yàn)檫@種排序很基礎(chǔ)且面試出現(xiàn)的頻率比較大。?對于冒泡排序比較好的理解是：?對比數(shù)組內(nèi)相鄰的兩個元素，如果 元素值 [i] 大于 [i+1] 那么，這兩個元素就需要交換位置......直到數(shù)組最后一個索引對應(yīng)的元素值最大。
根據(jù)上面的描述，我們可以思考，如果數(shù)組元素值 [i] 大于 [i+1] 才去交換位置，那么交換位置以后我們需要將其屬性值給記錄下來，常見的做法是 使用第三方來記錄變化的值 ?
首先，我們定義一個數(shù)組，然后根據(jù)上面的描述，不斷去判斷數(shù)組內(nèi)兩個相鄰的屬性值，然后通過臨時變量去記錄，于是，就有了下面的參考代碼：
通過這樣一遍操作以后，數(shù)組內(nèi)的最大值就已經(jīng)在最后的索引位置了，但這樣達(dá)不到我們對數(shù)組進(jìn)行整體排序的要求。因此還要對數(shù)組進(jìn)行繼續(xù)判斷，由于上面的一次排序已經(jīng)將最大值給找出來了，所以最后一個索引對應(yīng)的值我們就不需要在對其進(jìn)行排序了，因此第二次排序有以下的參考思路代碼：
關(guān)于以上參考代碼的思考：
如果我們的數(shù)組有4個屬性值：
那么第一趟需要比較3次，分別是 [0] [1] 、?[1] [2] 、?[2] [3] ?這一趟排序比較出來的最大值:[3]
第二趟需要比較2次 ，分別是?[0] [1] 、?[1] [2]?這一趟排序比較出來的較大值:[2]
第三趟需要比較1次，也就是?[0] [1]?這一趟排序比較出來的較大值:[1]
因此，通過以上試驗(yàn)步驟可以了解這種排序的比較趟數(shù)規(guī)律以及每一趟需要比較的次數(shù)，所以就可以通過循環(huán)去操作，下面是冒泡排序比較熟悉的寫法
冒泡排序優(yōu)化：
試想有下面這樣一個數(shù)組：int arr[ ] = { 1,2,3,4,6,5 } ; 根據(jù)對這個數(shù)組的直觀判斷，我們只需遍歷判斷一趟就可以將數(shù)組進(jìn)行整體排序，但是上面的寫法對于這種情況下的數(shù)組就會顯得有些冗余（判斷5趟，每一趟依次遞減）。那有沒有比較好的方案去優(yōu)化這種情況？答案是有的，我們可以定義一個TAG，來判斷是否發(fā)生變化。我們知道發(fā)生位置變化的時機(jī)是在內(nèi)層循環(huán)里面進(jìn)行操作的，因此我們可以這樣操作：
關(guān)于冒泡排序的內(nèi)容基本上就介紹到這里。
選擇排序：
選擇排序?qū)ava開發(fā)來說也不是那么陌生，因?yàn)镴ava內(nèi)置了API方便我們快速調(diào)用，那么關(guān)于選擇排序的解釋是（來自百度百科）：選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法（比如序列[5， 5， 3]第一次就將第一個[5]與[3]交換，導(dǎo)致第一個5挪動到第二個5后面）?；诖怂枷氲乃惴ㄖ饕泻唵芜x擇排序、樹型選擇排序和堆排序。（這里只介紹常用的簡單選擇排序）。
簡單選擇排序的基本思想：給定數(shù)組：int[]?arr={里面n個數(shù)據(jù)}；第1趟排序，在待排序數(shù)據(jù)arr[1]~arr[n]中選出最小的數(shù)據(jù)，將它與arrr[1]交換；第2趟，在待排序數(shù)據(jù)arr[2]~arr[n]中選出最小的數(shù)據(jù)，將它與r[2]交換；以此類推，第i趟在待排序數(shù)據(jù)arr[i]~arr[n]中選出最小的數(shù)據(jù)，將它與r[i]交換，直到全部排序完成。
舉例：首先定義一個數(shù)組?int [ ]?arr = { 5,2,8,4,9,1 } ; 那么根據(jù)上面的定義，選擇排序的邏輯就應(yīng)該按照以下步驟去執(zhí)行：
第一趟排序： 原始數(shù)據(jù)：5??2??8??4??9??1 ? 最小數(shù)據(jù)1，把1放在首位，也就是1和5互換位置，排序結(jié)果：1??2??8??4??9??5
第二趟排序：第1以外的數(shù)據(jù){ 2??8??4??9??5 }進(jìn)行比較，2最小。排序結(jié)果：1??2??8??4??9??5
第三趟排序：除1、2以外的數(shù)據(jù){ 8??4??9??5 }進(jìn)行比較，4最小，8和4交換。排序結(jié)果：1??2??4??8??9??5
第四趟排序：除第1、2、4以外的其他數(shù)據(jù){8??9??5}進(jìn)行比較，5最小，8和5交換。排序結(jié)果：1??2??4??5??9??8
第五趟排序：除第1、2、4、5以外的其他數(shù)據(jù){9??8}進(jìn)行比較，8最小，8和9交換。排序結(jié)果：1??2??4??5??8??9
通過以上試驗(yàn)步驟有以下結(jié)論：
A：一個數(shù)組是需要n-1趟排序的(因?yàn)橹钡绞Ｏ乱粋€元素時，才不需要找最大值)
B：每交換1次，再次找最大值時就將范圍縮小1
C：查詢當(dāng)前趟數(shù)最大值實(shí)際不用知道具體的屬性值是多少，也就是我們只需知道其索引即可，交換也可以根據(jù)角標(biāo)來進(jìn)行交換
根據(jù)以上結(jié)論結(jié)合循環(huán)的使用，我們可以有以下選擇排序的代碼：
在上面關(guān)于選擇排序的概念提到，這是一種不穩(wěn)定的排序方法，那么什么叫排序的穩(wěn)定性？為了更好的理解這一概念，首先看下這個數(shù)組 int [ ] arr = { 6,6,2 } ; 排序的穩(wěn)定性是指：排序前2個相等的數(shù)在序列的前后位置順序和排序后它們兩個的前后位置順序相同，如果相同，則是穩(wěn)定的排序方法；如果不相同，則是不穩(wěn)定的排序方法。假定我們使用選擇排序的話，那第一趟排序后結(jié)果就是[2,6,6]。因?yàn)檫@個數(shù)組在定義之初就有兩個相同的值，屬性值對應(yīng)的索引分別是array [0] 和array [1]，結(jié)果經(jīng)過排序，array[0]的跑到了array[2]上了。
那么這導(dǎo)致了：2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序不相同，因此，我們就說它是不穩(wěn)定的
再回到上面的問題，為什么冒泡排序是穩(wěn)定的，主要原因是：冒泡排序進(jìn)行倆倆比較的時候，沒有對相等的數(shù)據(jù)進(jìn)行交換(因?yàn)闆]必要)。因此它不存在2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序不相同。
那么穩(wěn)定排序的好處是什么？一種說法如下：如果我們只對一串?dāng)?shù)字排序，那么穩(wěn)定與否確實(shí)不重要，因?yàn)橐淮當(dāng)?shù)字的屬性是單一的，就是數(shù)字值的大小。但是排序的元素往往不只有一個屬性，例如我們對一群人按年齡排序，但是人除了年齡屬性還有身高體重屬性，在年齡相同時如果不想破壞原先身高體重的次序，就必須用穩(wěn)定排序算法。
關(guān)于選擇排序和排序的穩(wěn)定性的內(nèi)容基本上就介紹到這里。
插入排序：
什么是插入排序？插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序。插入排序是一種穩(wěn)定的排序方法。那么如何更好的去理解插入排序？玩過斗地主的小伙伴都知道，我們起手第一張手牌以后，然后抽到第二張牌一般都會放到第一張手牌的左邊或者右邊，類似下圖：
插入排序就是借用了這種思想，先給定一個排好序的序列（通常設(shè)定為 給定要排序序列的第一個值），然后陸續(xù)將后面的值與前面排好序的比較，如果是小于前面的值，就插到前面去。就這樣一直比較，然后最后總會插入到合適的位置，當(dāng)然啦，如果是插入到第一位了，也算完成了插入。
插入排序執(zhí)行流程如下：
現(xiàn)在假設(shè)有一個數(shù)組，n是數(shù)組的長度。
首先假設(shè)第一個元素被放置在正確的位置上，這樣僅需從1 —— n-1 范圍內(nèi)對剩余元素進(jìn)行排序。對于每次遍歷，從0 —— i-1 范圍內(nèi)的元素已經(jīng)被排好序。每次遍歷的任務(wù)是：通過掃描前面已排序的子列表，將位置 i 處的元素定位到從0 到 i 的子列表之內(nèi)的正確的位置上。
我們可以 arr[ i ] 賦值給名為target的臨時元素。向下掃描列表，比較這個目標(biāo)值target 與 arr[ i-1 ]、arr[i-2]的大小，依次類推。這個比較過程在小于或等于目標(biāo)值的第一個元素( arr[ j ] )處停止，或者在列表開始處停止（j = 0）。
如果出現(xiàn)arr[ i ]小于前面任何已排序元素時，后一個條件（j = 0）為true，因此，這個元素會占用新排序子列表的第一個位置。在掃描期間，大于目標(biāo)值target的每個元素都會向右滑動一個位置（arr[ j ] = arr[ j-1 ]）。一旦確定了正確位置 j，目標(biāo)值target（即原始的arr [ i ]）就會被復(fù)制到這個位置。
與選擇排序不同的是，插入排序?qū)?shù)據(jù)向右滑動，并且不會執(zhí)行交換。
有了上面的流程，可以有以下的代碼：
本篇文章主要學(xué)習(xí)的是基礎(chǔ)排序中的冒泡排序、選擇排序、插入排序，下一篇學(xué)習(xí)快速排序、歸并排序。
如果這篇文章對您有開發(fā)or學(xué)習(xí)上的些許幫助，希望各位看官留下寶貴的star，謝謝。
Ps:著作權(quán)歸作者所有,轉(zhuǎn)載請注明作者, 商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處(開頭或結(jié)尾請?zhí)砑愚D(zhuǎn)載出處，添加原文url地址),文章請勿濫用,也希望大家尊重筆者的勞動成果。
