排序算法

排序算法是最基本是算法，通常是解決其他問(wèn)題的第一步，需要進(jìn)行結(jié)果驗(yàn)證，也要評(píng)估排序算法的性能，性能主要看兩個(gè)方面：運(yùn)行時(shí)間和額外的內(nèi)存使用（即時(shí)間復(fù)雜度和空間復(fù)雜度）。
對(duì)于非基本數(shù)據(jù)類型的分組，需要讓該數(shù)據(jù)類型實(shí)現(xiàn)Comparable接口，該數(shù)據(jù)類型中要實(shí)現(xiàn)一個(gè)comparaTo()方法來(lái)定義自然次序，這個(gè)方法必須實(shí)現(xiàn)一個(gè)完整的比較序列，即滿足：

自反性，對(duì)所有的V都有V=V；
反對(duì)稱性，對(duì)于所有的V

初級(jí)排序算法

主要有選擇排序，插入排序，交換排序

  • 選擇排序
    一種最簡(jiǎn)單的排序算法是這樣的：首先，找到數(shù)組中最小的那個(gè)元素，其次，將它和數(shù)組的第 一個(gè)元素交換位置（如果第一個(gè)元素就是最小元素那么它就和自己交換）。再次，在剩下的元素中 找到最小的元素，將它與數(shù)組的第二個(gè)元素交換位置。如此往復(fù)，直到將整個(gè)數(shù)組排序。這種方法 叫做選擇排序，因?yàn)樗诓粩嗟剡x擇剩余元素之中的最小者。

  • 直接選擇排序
    有兩個(gè)鮮明的特點(diǎn)：
    運(yùn)行時(shí)間與輸入無(wú)關(guān)，一個(gè)已經(jīng)有序的數(shù)組或 是主鍵全部相等的數(shù)組和一個(gè)元素隨機(jī)排列的數(shù)組所用的排序時(shí)間一樣長(zhǎng)！，其 他算法會(huì)更善于利用輸入的初始狀態(tài)
    數(shù)據(jù)移動(dòng)是最少的，每次交換都會(huì)改變兩個(gè)數(shù)組元素的值，因此選擇排序用了N次交換——交 換次數(shù)和數(shù)組的大小是線性關(guān)系。我們將研究的其他任何算法都不具備這個(gè)特征（大部分的增長(zhǎng)數(shù) 量級(jí)都是線性對(duì)數(shù)或是平方級(jí)別）。

  • 插入排序
    插入排序的意思就是說(shuō)，我們把數(shù)據(jù)分成兩個(gè)部分，一部分是已經(jīng)排好序的數(shù)據(jù)，一部分是當(dāng)前還沒(méi)有完成排序的數(shù)據(jù)。那么這么說(shuō)來(lái)的話，排序的過(guò)程是不是就是把沒(méi)有排序的數(shù)據(jù)逐個(gè)插入到已經(jīng)排好序的隊(duì)列中的過(guò)程呢。
    與選擇排序一樣，當(dāng)前索引左邊的所有元素都是有序的，但它們的最終位置還不確定，為了給 更小的元素騰出空間，它們可能會(huì)被移動(dòng)。但是當(dāng)索引到達(dá)數(shù)組的右端時(shí)，數(shù)組排序就完成了。
    和選擇排序不同的是，插入排序所需的時(shí)間取決于輸入中元素的初始順序。例如，對(duì)一個(gè)很大 且其中的元素已經(jīng)有序（或接近有序）的數(shù)組進(jìn)行排序?qū)?huì)比對(duì)隨機(jī)順序的數(shù)組或是逆序數(shù)組進(jìn)行排序要快得多。

  1. 下面是幾種典型的部分有序的數(shù)組： ?

  2. 數(shù)組中每個(gè)元素距離它的最終位置都不遠(yuǎn)； ?

  3. 一個(gè)有序的大數(shù)組接一個(gè)小數(shù)組； ?
    數(shù)組中只有幾個(gè)元素的位置不正確。 插入排序?qū)@樣的數(shù)組很有效，而選擇排序則不然。事實(shí)上，當(dāng)?shù)怪玫臄?shù)量很少時(shí)，插入排序 很可能比本章中的其他任何算法都要快

  • 直接插入排序
    與自身比較的話，第一輪有序的只有一個(gè)元素也就是第一個(gè)元素，要從第二個(gè)元素開(kāi)始往前逐一比較。也就是說(shuō)，第一輪會(huì)幫第二個(gè)元素找到正確的位置，以此類推，第N輪幫第N+1個(gè)元素找到正確的位置，每一輪都需要比較1次到N次。

  • Shell排序
    對(duì)于大規(guī)模亂序數(shù)組，直接插入排序很慢，因?yàn)樗粫?huì)交換相鄰的元素，因此元素只能一點(diǎn)一點(diǎn)地從數(shù)組 的一端移動(dòng)到另一端。
    希爾排序的思想是使數(shù)組中任意間隔為h的元素都是有序的。這樣的數(shù)組被稱為h有序數(shù)組。
    iOS培訓(xùn),Swift培訓(xùn),蘋果開(kāi)發(fā)培訓(xùn),移動(dòng)開(kāi)發(fā)培訓(xùn)

希爾排序，可以看成是冒泡排序的變種。它的基本思想是：首先按照一個(gè)序列遞減的方法逐漸進(jìn)行排序。比如說(shuō)有10個(gè)數(shù)據(jù)，我們按照序列5、3、1的順序進(jìn)行排序。首先是5，那么我們對(duì)1和6、2和7、3和8、4和9、5和10進(jìn)行排列；第二輪是3，那么對(duì)數(shù)據(jù)1、4、7、10排列，再對(duì)2、5、8進(jìn)行排列，以及3、6、9排列；第三輪就和冒泡排序一樣了，以此對(duì)每個(gè)數(shù)據(jù)進(jìn)行排列。它的優(yōu)勢(shì)就是讓整個(gè)隊(duì)列基本有序，減少數(shù)據(jù)移動(dòng)的次數(shù)，從而降低算法的計(jì)算復(fù)雜度。