Python中經(jīng)典排序方法

1、python中經(jīng)典排序方法數(shù)據(jù)的排序是在解決實際問題時常常用到的步驟，也是數(shù)據(jù)結(jié)構(gòu)的考點之一，下面介紹10種經(jīng)典的排序辦法。 首先，排序辦法可以大體分為插入排序、挑選排序、交換排序、歸并排序和桶排序四大類，其中，插入排序又分為挺直插入排序、二分插入排序和希爾排序，挑選排序分為挺直挑選排序和堆排序，交換排序分為冒泡排序和迅速排序，桶排序以基數(shù)排序和計數(shù)排序為代表。這些排序辦法的時光復(fù)雜度和空間復(fù)雜度分離如下表所示。 排序辦法的穩(wěn)定性是這樣定義的：在待排序序列中假如存在ai和aj，ai=aj&&i1，不符合要求，轉(zhuǎn)變1的位置。首先比較1和8，1更小，交換1和8的位置

2、，序列成為6,1,8,4,3,9,5,0，然后繼續(xù)比較1和6，1更小，交換1和6的位置，序列成為1,6,8,4,3,9,5,0,注重此時前三個值已經(jīng)符合升序的要求。 c. 8>4，不符合要求，轉(zhuǎn)變4的位置，根據(jù)上面的辦法，依次與前面的值比較，分離與8和6交換位置，當(dāng)比較到1時，1=arr2i+1&amp;&amp;arri>=arr2i-1；小頂堆是父節(jié)點的值最小的二叉樹，即arri<=arr2i+1&amp;&amp;arri<=arr2i-1。 以升序排序為例，首先建立初始最大堆，以某個節(jié)點為入口，向下調(diào)節(jié)其子節(jié)點，使其符合大頂堆的特

3、點。建立初始大頂堆的過程會重復(fù)調(diào)節(jié)一些節(jié)點，是由于父節(jié)點和子節(jié)點的交換，會影響以子節(jié)點為根節(jié)點的子樹，中，9,1,7子樹原符合要求，6和9交換后，6,1,7不符合要求，就要再次調(diào)節(jié)該子樹。 初始大頂堆建立之后，將根節(jié)點的值置換到序列末尾，然后重新調(diào)節(jié)前面的序列，這時只從根節(jié)點向下調(diào)節(jié)即可，由于初始大頂堆已經(jīng)形成，中，即便交換了0和4的位置，父節(jié)點8也照舊是最大的。 堆排序不穩(wěn)定，空間復(fù)雜度為o(1)，但時光復(fù)雜度恒定為o(nlogn)。 (6) 冒泡排序 交換排序即通過交換元素位置，使序列有序。冒泡排序是最容易的交換排序，每次將最大值/最小值依次交換到序列末尾。冒泡排序是穩(wěn)定的，空間復(fù)雜度為o

4、(1)，時光復(fù)雜度最好為o(n)。 (7) 迅速排序 迅速排序可以說是用法頻率和考察頻率最高的排序辦法。迅速排序的基本思想是以序列中的某個值為標(biāo)準(zhǔn)，大于該值的被放在右邊，小于該值放在左邊，然后再繼續(xù)對該值左右兩兩邊的序列重復(fù)此步驟，思想很容易，代碼如下。 對于python，有一種越發(fā)容易明白的實現(xiàn)方式 迅速排序并沒有創(chuàng)建新的數(shù)組，但因為實現(xiàn)過程中利用了函數(shù)的遞歸調(diào)用，需要堆?？臻g，所以空間復(fù)雜度為o(nlogn)，時光復(fù)雜度最好為o(nlogn)。 (8) 歸并排序 歸并排序采納分而治之的思想，將序列分為多個小的序列，對小的序列排序之后，將小序列合并為大的序列，過程如下圖所示。 代碼如下 歸并

5、排序需要新的數(shù)組存放合并后的序列，空間復(fù)雜度為o(n)，時光復(fù)雜度恒定為o(nlogn)，是穩(wěn)定的。 (9) 計數(shù)排序 桶排序事實上是一類排序辦法的總稱。桶排序的思想是將全部數(shù)據(jù)根據(jù)一定的映射關(guān)系放到一定數(shù)量的桶中，將每個桶里的數(shù)據(jù)排序，再將全部的桶組合起來，所以不同的映射關(guān)系下可以產(chǎn)生不同的桶排序，并且桶排序是基于其他排序算法的，桶內(nèi)數(shù)據(jù)的排序需要用法其他排序算法。計數(shù)排序和基數(shù)排序是桶排序的兩種代表。 計數(shù)排序是采納的映射關(guān)系是最挺直的fi=i，即一個桶里的數(shù)字都是相同的，因此沒有桶內(nèi)排序的步驟。詳細(xì)過程為， 1.找出待排序的數(shù)組中最大和最小的元素 2.統(tǒng)計數(shù)組中每個值為i的元素浮現(xiàn)的次數(shù)，存入數(shù)組c的第i項，這時映射的過程 3.對全部的計數(shù)累加，ci的含義即是在數(shù)組中小于i的元素個數(shù)，即為排序后i應(yīng)放的位置 4.反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第c(i)項，每放一個 元素就將c(i)減去1。 代碼如下 (10) 基數(shù)排序 基數(shù)排序的映射辦法是根據(jù)數(shù)據(jù)特定位上數(shù)字放入不同的桶中， 將序列中的數(shù)組根據(jù)個位放到不同的桶中，然后根據(jù)個位0&mdash;&mdash;9的挨次依次取出，再根據(jù)十位放到不同的桶中，.直到達到數(shù)據(jù)的最高位，