排序

排序是計算機內經常進行的一種操作，其目的是將一組”無序”的記錄序列調整為”有序”的記錄序列。分內部排序和外部排序。若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。反之，若參加排序的記錄數量很大，整個序列的排序過程不可能完全在內存中完成，需要訪問外存，則稱此類排序問題為外部排序。內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。

看圖使理解更清晰深刻：

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

常見排序算法

快速排序、希爾排序、堆排序、直接選擇排序不是穩定的排序算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸并排序是穩定的排序算法

本文將用Python實現冒泡排序、插入排序、希爾排序、快速排序、直接選擇排序、堆排序、歸并排序、基數排序這八大排序算法。

1. 冒泡排序（Bubble Sort）

算法原理：

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大于a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大于a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最后比較a[n-1]與a[n]的值。這樣處理一輪后，a[n]的值一定是這組數據中最大的。再對a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪后a[1]、a[2]、……a[n]就以升序排列了。降序排列與升序排列相類似，若a[1]小于a[2]則交換兩者的值，否則不變，后面以此類推。 總的來講，每一輪排序后最大（或最小）的數將移動到數據序列的最后，理論上總共要進行n(n-1）/2次交換。

優點：穩定；
缺點：慢，每次只能移動相鄰兩個數據。

python代碼實現：

#!/usr/bin/env python#coding:utf-8'''file:python-8sort.pydate:9/1/17 9:03 AMauthor:lockeyemail:lockey@123.comdesc:python實現八大排序算法'''lst1 = [2,5435,67,445,34,4,34]def bubble_sort_basic(lst1): lstlen = len(lst1);i = 0 while i < lstlen:  for j in range(1,lstlen):   if lst1[j-1] > lst1[j]:   #對比相鄰兩個元素的大小，小的元素上浮    lst1[j],lst1[j-1] = lst1[j-1],lst1[j]  i += 1  print 'sorted{}: {}'.format(i, lst1) print '-------------------------------' return lst1bubble_sort_basic(lst1)

冒泡排序算法的改進

對于全員無序或者沒有重復元素的序列，上述算法在同一思路上是沒有改進余地的，但是如果一個序列中存在重復元素或者部分元素是有序的呢，這種情況下必然會存在不必要的重復排序，那么我們可以在排序過程中加入一標志性變量change，用于標志某一趟排序過程中是否有數據交換，如果進行某一趟排序時并沒有進行數據交換，則說明數據已經按要求排列好，可立即結束排序，避免不必要的比較過程，改進后示例代碼如下：

lst2 = [2,5435,67,445,34,4,34]def bubble_sort_improve(lst2): lstlen = len(lst2) i = 1;times = 0 while i > 0:  times += 1  change = 0  for j in range(1,lstlen):   if lst2[j-1] > lst2[j]:   #使用標記記錄本輪排序中是否有數據交換    change = j    lst2[j],lst2[j-1] = lst2[j-1],lst2[j]  print 'sorted{}: {}'.format(times,lst2)  #將數據交換標記作為循環條件，決定是否繼續進行排序  i = change return lst2bubble_sort_improve(lst2)

兩種情況下運行截圖如下：

由上圖可以看出，對于部分元素為有序排列的序列，優化后的算法減少了兩輪排序。

2.選擇排序（Selection Sort）

算法原理：

每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：

①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。

優點：移動數據的次數已知（n-1次）；
缺點：比較次數多，不穩定。

python代碼實現：

# -*- coding: UTF-8 -*-'''Created on 2017年8月31日Running environment：win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def selection_sort(lst): lstlen = len(lst) for i in range(0,lstlen):  min = i  for j in range(i+1,lstlen):  #從 i+1開始循環遍歷尋找最小的索引   if lst[min] > lst[j]:    min = j  lst[min],lst[i] = lst[i],lst[min]  #一層遍歷結束后將最小值賦給外層索引i所指的位置，將i的值賦給最小值索引    print('The {} sorted: {}'.format(i+1,lst)) return lstsorted = selection_sort(lst)print('The sorted result is: {}'.format(sorted))

運行結果截圖：

3. 插入排序

算法原理：

已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、b[2]、……b[m]，需將二者合并成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大于a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大于a[2]，則繼續跳過，直到b[1]小于a數組中某一數據a[x]，則將a[x]~a[n]分別向后移動一位，將b[1]插入到原來a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1的數組a）
優點：穩定，快；
缺點：比較次數不一定，比較次數越多，插入點后的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決這個問題。

算法復雜度

如果目標是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1）次。平均來說插入排序算法的時間復雜度為O(n^2）。因而，插入排序不適合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。

python代碼實現：

# -*- coding: UTF-8 -*-'''Created on 2017年8月31日Running environment：win7.x86_64 eclipse python3@author: Lockey'''lst = [65,568,9,23,4,34,65,8,6,9]def insert_sort(lst): count = len(lst) for i in range(1, count):  key = lst[i]  j = i - 1  while j >= 0:   if lst[j] > key:    lst[j + 1] = lst[j]    lst[j] = key   j -= 1  print('The {} sorted: {}'.format(i,lst)) return lstsorted = insert_sort(lst)print('The sorted result is: {}'.format(sorted))

運行結果截圖：

由排序過程可知，每次往已經排好序的序列中插入一個元素，然后排序，下次再插入一個元素排序。。。直到所有元素都插入，排序結束

4. 希爾排序

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因DL．Shell于1959年提出而得名。

算法原理

算法核心為分組（按步長）、組內插入排序

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最后一組以次類推，在各組內用插入排序，然后取d'<d，重復上述操作，直到d=1。

python代碼實現：

#!/usr/bin/env python#coding:utf-8'''file:python-8sort.pydate:9/1/17 9:03 AMauthor:lockeyemail:lockey@123.comdesc:python實現八大排序算法'''lst = [65,568,9,23,4,34,65,8,6,9]def shell_sort(lists): print 'orginal list is {}'.format(lst) count = len(lists) step = 2 times = 0 group = int(count/step) while group > 0:  for i in range(0, group):   times += 1   j = i + group   while j < count:    k = j - group    key = lists[j]    while k >= 0:     if lists[k] > key:      lists[k + group] = lists[k]      lists[k] = key     k -= group    j += group    print 'The {} sorted: {}'.format(times,lists)  group = int(group/step) print 'The final result is: {}'.format(lists) return listsshell_sort(lst)

運行測試結果截圖：

過程分析：

第一步：

1-5：將序列分成了5組（group = int(count/step)）,如下圖，一列為一組：

然后各組內進行插入排序，經過5（5組*1次）次組內插入排序得到了序列：

The 1-5 sorted：[34, 65, 8, 6, 4, 65, 568, 9, 23, 9]

第二步：

6666-7777：將序列分成了2組（group = int(group/step)）,如下圖，一列為一組：

然后各組內進行插入排序，經過8（2組*4次）次組內插入排序得到了序列：

The 6-7 sorted: [4, 6, 8, 9, 23, 9, 34, 65, 568, 65]

第三步：

888888888：對上一個排序結果得到的完整序列進行插入排序：

[4, 6, 8, 9, 23, 9, 34, 65, 568, 65]

經過9（1組*10 -1）次插入排序后：

The final result is: [4, 6, 8, 9, 9, 23, 34, 65, 65, 568]

希爾排序時效分析很難，關鍵碼的比較次數與記錄移動次數依賴于增量因子序列的選取，特定情況下可以準確估算出關鍵碼的比較次數和記錄的移動次數。目前還沒有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數的，也有取質數的，但需要注意：增量因子中除1 外沒有公因子，且最后一個增量因子必須為1。希爾排序方法是一個不穩定的排序方法

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網。