本篇文章主要介紹的是Java和Android開發(fā)中常見的排序概念圾亏，由于篇幅的問題我將其分成了幾篇澜驮。主要有基礎篇和實戰(zhàn)篇缀匕。本篇主要學習的是基礎排序的內(nèi)容缀踪，主要學習以下四種基礎排序：冒泡排序、選擇排序腾务、插入排序毕骡。
冒泡排序：
對于冒泡排序，我們不是很陌生，因為這種排序很基礎且面試出現(xiàn)的頻率比較大未巫。?對于冒泡排序比較好的理解是：?對比數(shù)組內(nèi)相鄰的兩個元素窿撬，如果 元素值 [i] 大于 [i+1] 那么，這兩個元素就需要交換位置......直到數(shù)組最后一個索引對應的元素值最大叙凡。
根據(jù)上面的描述劈伴，我們可以思考，如果數(shù)組元素值 [i] 大于 [i+1] 才去交換位置握爷，那么交換位置以后我們需要將其屬性值給記錄下來跛璧，常見的做法是 使用第三方來記錄變化的值 ?
首先，我們定義一個數(shù)組新啼，然后根據(jù)上面的描述追城，不斷去判斷數(shù)組內(nèi)兩個相鄰的屬性值，然后通過臨時變量去記錄燥撞，于是座柱，就有了下面的參考代碼：
通過這樣一遍操作以后，數(shù)組內(nèi)的最大值就已經(jīng)在最后的索引位置了物舒，但這樣達不到我們對數(shù)組進行整體排序的要求色洞。因此還要對數(shù)組進行繼續(xù)判斷，由于上面的一次排序已經(jīng)將最大值給找出來了冠胯，所以最后一個索引對應的值我們就不需要在對其進行排序了火诸，因此第二次排序有以下的參考思路代碼：
關于以上參考代碼的思考：
如果我們的數(shù)組有4個屬性值：
那么第一趟需要比較3次，分別是 [0] [1] 荠察、?[1] [2] 置蜀、?[2] [3] ?這一趟排序比較出來的最大值:[3]
第二趟需要比較2次 ，分別是?[0] [1] 割粮、?[1] [2]?這一趟排序比較出來的較大值:[2]
第三趟需要比較1次盾碗，也就是?[0] [1]?這一趟排序比較出來的較大值:[1]
因此，通過以上試驗步驟可以了解這種排序的比較趟數(shù)規(guī)律以及每一趟需要比較的次數(shù)舀瓢，所以就可以通過循環(huán)去操作廷雅，下面是冒泡排序比較熟悉的寫法
冒泡排序優(yōu)化：
試想有下面這樣一個數(shù)組：int arr[ ] = { 1,2,3,4,6,5 } ; 根據(jù)對這個數(shù)組的直觀判斷，我們只需遍歷判斷一趟就可以將數(shù)組進行整體排序京髓，但是上面的寫法對于這種情況下的數(shù)組就會顯得有些冗余（判斷5趟航缀，每一趟依次遞減）。那有沒有比較好的方案去優(yōu)化這種情況堰怨？答案是有的芥玉，我們可以定義一個TAG，來判斷是否發(fā)生變化备图。我們知道發(fā)生位置變化的時機是在內(nèi)層循環(huán)里面進行操作的灿巧，因此我們可以這樣操作：
關于冒泡排序的內(nèi)容基本上就介紹到這里赶袄。
選擇排序：
選擇排序對Java開發(fā)來說也不是那么陌生，因為Java內(nèi)置了API方便我們快速調(diào)用抠藕，那么關于選擇排序的解釋是（來自百度百科）：選擇排序（Selection sort）是一種簡單直觀的排序算法饿肺。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素盾似，存放在序列的起始位置敬辣，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法（比如序列[5零院， 5溉跃， 3]第一次就將第一個[5]與[3]交換，導致第一個5挪動到第二個5后面）告抄∽ィ基于此思想的算法主要有簡單選擇排序、樹型選擇排序和堆排序玄妈。（這里只介紹常用的簡單選擇排序）乾吻。
簡單選擇排序的基本思想：給定數(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ù)上面的定義，選擇排序的邏輯就應該按照以下步驟去執(zhí)行：
第一趟排序： 原始數(shù)據(jù)：5??2??8??4??9??1 ? 最小數(shù)據(jù)1鹊奖，把1放在首位苛聘，也就是1和5互換位置，排序結果：1??2??8??4??9??5
第二趟排序：第1以外的數(shù)據(jù){ 2??8??4??9??5 }進行比較忠聚，2最小设哗。排序結果：1??2??8??4??9??5
第三趟排序：除1、2以外的數(shù)據(jù){ 8??4??9??5 }進行比較两蟀，4最小网梢，8和4交換。排序結果：1??2??4??8??9??5
第四趟排序：除第1赂毯、2战虏、4以外的其他數(shù)據(jù){8??9??5}進行比較拣宰，5最小，8和5交換烦感。排序結果：1??2??4??5??9??8
第五趟排序：除第1徐裸、2、4啸盏、5以外的其他數(shù)據(jù){9??8}進行比較重贺，8最小，8和9交換回懦。排序結果：1??2??4??5??8??9
通過以上試驗步驟有以下結論：
A：一個數(shù)組是需要n-1趟排序的(因為直到剩下一個元素時气笙，才不需要找最大值)
B：每交換1次，再次找最大值時就將范圍縮小1
C：查詢當前趟數(shù)最大值實際不用知道具體的屬性值是多少怯晕，也就是我們只需知道其索引即可潜圃，交換也可以根據(jù)角標來進行交換
根據(jù)以上結論結合循環(huán)的使用，我們可以有以下選擇排序的代碼：
在上面關于選擇排序的概念提到舟茶，這是一種不穩(wěn)定的排序方法谭期，那么什么叫排序的穩(wěn)定性？為了更好的理解這一概念吧凉，首先看下這個數(shù)組 int [ ] arr = { 6,6,2 } ; 排序的穩(wěn)定性是指：排序前2個相等的數(shù)在序列的前后位置順序和排序后它們兩個的前后位置順序相同隧出，如果相同，則是穩(wěn)定的排序方法阀捅；如果不相同胀瞪，則是不穩(wěn)定的排序方法。假定我們使用選擇排序的話饲鄙，那第一趟排序后結果就是[2,6,6]凄诞。因為這個數(shù)組在定義之初就有兩個相同的值，屬性值對應的索引分別是array [0] 和array [1]忍级，結果經(jīng)過排序帆谍，array[0]的跑到了array[2]上了。
那么這導致了：2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序不相同轴咱，因此汛蝙，我們就說它是不穩(wěn)定的
再回到上面的問題，為什么冒泡排序是穩(wěn)定的嗦玖，主要原因是：冒泡排序進行倆倆比較的時候患雇，沒有對相等的數(shù)據(jù)進行交換(因為沒必要)。因此它不存在2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序不相同宇挫。
那么穩(wěn)定排序的好處是什么苛吱？一種說法如下：如果我們只對一串數(shù)字排序，那么穩(wěn)定與否確實不重要器瘪，因為一串數(shù)字的屬性是單一的翠储，就是數(shù)字值的大小绘雁。但是排序的元素往往不只有一個屬性，例如我們對一群人按年齡排序援所，但是人除了年齡屬性還有身高體重屬性庐舟，在年齡相同時如果不想破壞原先身高體重的次序，就必須用穩(wěn)定排序算法住拭。
關于選擇排序和排序的穩(wěn)定性的內(nèi)容基本上就介紹到這里挪略。
插入排序：
什么是插入排序？插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中滔岳，從而得到一個新的杠娱、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序谱煤。插入排序是一種穩(wěn)定的排序方法摊求。那么如何更好的去理解插入排序？玩過斗地主的小伙伴都知道刘离，我們起手第一張手牌以后室叉，然后抽到第二張牌一般都會放到第一張手牌的左邊或者右邊，類似下圖：
插入排序就是借用了這種思想硫惕，先給定一個排好序的序列（通常設定為 給定要排序序列的第一個值）茧痕，然后陸續(xù)將后面的值與前面排好序的比較，如果是小于前面的值疲憋，就插到前面去凿渊。就這樣一直比較，然后最后總會插入到合適的位置缚柳，當然啦，如果是插入到第一位了搪锣，也算完成了插入秋忙。
插入排序執(zhí)行流程如下：
現(xiàn)在假設有一個數(shù)組，n是數(shù)組的長度构舟。
首先假設第一個元素被放置在正確的位置上灰追，這樣僅需從1 —— n-1 范圍內(nèi)對剩余元素進行排序。對于每次遍歷狗超，從0 —— i-1 范圍內(nèi)的元素已經(jīng)被排好序弹澎。每次遍歷的任務是：通過掃描前面已排序的子列表，將位置 i 處的元素定位到從0 到 i 的子列表之內(nèi)的正確的位置上努咐。
我們可以 arr[ i ] 賦值給名為target的臨時元素苦蒿。向下掃描列表，比較這個目標值target 與 arr[ i-1 ]渗稍、arr[i-2]的大小佩迟，依次類推团滥。這個比較過程在小于或等于目標值的第一個元素( arr[ j ] )處停止，或者在列表開始處停止（j = 0）报强。
如果出現(xiàn)arr[ i ]小于前面任何已排序元素時灸姊，后一個條件（j = 0）為true，因此秉溉，這個元素會占用新排序子列表的第一個位置力惯。在掃描期間，大于目標值target的每個元素都會向右滑動一個位置（arr[ j ] = arr[ j-1 ]）召嘶。一旦確定了正確位置 j父晶，目標值target（即原始的arr [ i ]）就會被復制到這個位置。
與選擇排序不同的是苍蔬，插入排序將數(shù)據(jù)向右滑動诱建，并且不會執(zhí)行交換。
有了上面的流程碟绑，可以有以下的代碼：
本篇文章主要學習的是基礎排序中的冒泡排序俺猿、選擇排序、插入排序格仲，下一篇學習快速排序押袍、歸并排序。
如果這篇文章對您有開發(fā)or學習上的些許幫助凯肋，希望各位看官留下寶貴的star谊惭，謝謝。
Ps:著作權歸作者所有,轉載請注明作者, 商業(yè)轉載請聯(lián)系作者獲得授權侮东，非商業(yè)轉載請注明出處(開頭或結尾請?zhí)砑愚D載出處圈盔，添加原文url地址),文章請勿濫用,也希望大家尊重筆者的勞動成果。
