排序

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

看圖使理解更清晰深刻：

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

常見排序算法

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

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

1. 冒泡排序（Bubble Sort）

算法原理：

已知一組無序數(shù)據(jù)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]的值一定是這組數(shù)據(jù)中最大的。再對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]則交換兩者的值，否則不變，后面以此類推。 總的來講，每一輪排序后最大（或最小）的數(shù)將移動(dòng)到數(shù)據(jù)序列的最后，理論上總共要進(jìn)行n(n-1）/2次交換。

優(yōu)點(diǎn)：穩(wěn)定；
缺點(diǎn)：慢，每次只能移動(dòng)相鄰兩個(gè)數(shù)據(jù)。

python代碼實(shí)現(xiàn)：

#!/usr/bin/env python
#coding:utf-8
'''
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123.com
desc:python實(shí)現(xiàn)八大排序算法
'''
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]:
   #對比相鄰兩個(gè)元素的大小，小的元素上浮
    lst1[j],lst1[j-1] = lst1[j-1],lst1[j]
  i += 1
  print 'sorted{}: {}'.format(i, lst1)
 print '-------------------------------'
 return lst1
bubble_sort_basic(lst1)

冒泡排序算法的改進(jìn)

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

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]:
   #使用標(biāo)記記錄本輪排序中是否有數(shù)據(jù)交換
    change = j
    lst2[j],lst2[j-1] = lst2[j-1],lst2[j]
  print 'sorted{}: {}'.format(times,lst2)
  #將數(shù)據(jù)交換標(biāo)記作為循環(huán)條件，決定是否繼續(xù)進(jìn)行排序
  i = change
 return lst2
bubble_sort_improve(lst2)

兩種情況下運(yùn)行截圖如下：

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

2.選擇排序（Selection Sort）

算法原理：

每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。
n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：

①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。
②第1趟排序
在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個(gè)記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。
……
③第i趟排序
第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。
這樣，n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。

優(yōu)點(diǎn)：移動(dòng)數(shù)據(jù)的次數(shù)已知（n-1次）；
缺點(diǎn)：比較次數(shù)多，不穩(wěn)定。

python代碼實(shí)現(xiàn)：

# -*- 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開始循環(huán)遍歷尋找最小的索引
   if lst[min] > lst[j]:
    min = j
  lst[min],lst[i] = lst[i],lst[min]
  #一層遍歷結(jié)束后將最小值賦給外層索引i所指的位置，將i的值賦給最小值索引  
  print('The {} sorted: {}'.format(i+1,lst))
 return lst
sorted = selection_sort(lst)
print('The sorted result is: {}'.format(sorted))

運(yùn)行結(jié)果截圖：

3. 插入排序

算法原理：

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

算法復(fù)雜度

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

python代碼實(shí)現(xiàn)：

# -*- 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 lst
sorted = insert_sort(lst)
print('The sorted result is: {}'.format(sorted))

運(yùn)行結(jié)果截圖：

由排序過程可知，每次往已經(jīng)排好序的序列中插入一個(gè)元素，然后排序，下次再插入一個(gè)元素排序。。。直到所有元素都插入，排序結(jié)束

4. 希爾排序

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

算法原理

算法核心為分組（按步長）、組內(nèi)插入排序

已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。發(fā)現(xiàn)當(dāng)n不大時(shí)，插入排序的效果很好。首先取一增量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]……列為最后一組以次類推，在各組內(nèi)用插入排序，然后取d'<d，重復(fù)上述操作，直到d=1。

python代碼實(shí)現(xiàn)：

#!/usr/bin/env python
#coding:utf-8
'''
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123.com
desc:python實(shí)現(xiàn)八大排序算法
'''
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 lists
shell_sort(lst)

運(yùn)行測試結(jié)果截圖：

過程分析：

第一步：

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

然后各組內(nèi)進(jìn)行插入排序，經(jīng)過5（5組*1次）次組內(nèi)插入排序得到了序列：

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

第二步：

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

然后各組內(nèi)進(jìn)行插入排序，經(jīng)過8（2組*4次）次組內(nèi)插入排序得到了序列：

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

第三步：

888888888：對上一個(gè)排序結(jié)果得到的完整序列進(jìn)行插入排序：

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

經(jīng)過9（1組*10 -1）次插入排序后：

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

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

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論