排序

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

看圖使理解更清晰深刻：

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，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)