1 冒泡排序
冒泡排序从小到大排序：一开始交换的区间为0~N-1，将第1个数和第2个数进行比较，前面大于后面，交换两个数，否则不交换。再比较第2个数和第三个数，前面大于后面，交换两个数否则不交换。依次进行，最大的数会放在数组最后的位置。然后将范围变为0~N-2，数组第二大的数会放在数组倒数第二的位置。依次进行整个交换过程，最后范围只剩一个数时数组即为有序。
冒泡排序
冒泡排序原理即：从数组下标为0的位置开始，比较下标位置为0和1的数据，如果0号位置的大，则交换位置，如果1号位置大，则什么也不做，然后右移一个位置，比较1号和2号的数据，和刚才的一样，如果1号的大，则交换位置，以此类推直至最后一个位置结束，到此数组中最大的元素就被排到了最后，之后再根据之前的步骤开始排前面的数据，直至全部数据都排序完成。
就是传说中的大的沉到底原则，适用于小量数据
def bubbleSort(relist): len_ = len(relist) for i in range(len_): for j in range(0,len_-i-1): if relist[j] > relist[j+1]: relist[j+1], relist[j] = relist[j], relist[j+1] return relist print bubbleSort([1,5,2,6,9,3])
2 选择排序
选择排序从小到大排序：一开始从0~n-1区间上选择一个最小值，将其放在位置0上，然后在1~n-1范围上选取最小值放在位置1上。重复过程直到剩下最后一个元素，数组即为有序。
比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。
# 方法一
def selectSort(relist): len_ = len(relist) for i in range(len_): min_index = i for j in range(i+1,len_): # 这个循环会找到值比第i个索引所代表值小的索引 if relist[j] < relist[min_index]: min_index = j relist[i] ,relist[min_index] = relist[min_index], relist[i] # 互换两个索引位置 return relist print selectSort([1,5,2,6,9,3])
# 方法二，更加简便，但是注意和冒泡法进行区分
def selectSort(relist): for i in range(len(relist)): for j in range(len(relist)-i): if relist[i] > relist[i+j]: relist[i],relist[i+j] = relist[i+j],relist[i] return relist print selectSort([1,5,2,6,9,3])
3 插入排序
插入排序从小到大排序：首先位置1上的数和位置0上的数进行比较，如果位置1上的数大于位置0上的数，将位置0上的数向后移一位，将1插入到0位置，否则不处理。位置k上的数和之前的数依次进行比较，如果位置K上的数更大，将之前的数向后移位，最后将位置k上的数插入不满足条件点，反之不处理。
插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
默认序列中的第0个元素是有序的（因为只有一个元素a[0]嘛，自然是有序的）；
从下标为1（下标0没啥好插的）的元素开始，取当前下标i位置处的元素a[i]保存到一个临时变量waitInsert里；
waitInsert与对前半部分有序序列的循环遍历比较，直到遇到第一个比waitInsert大的元素（这里默认是从小到大排序），此时的下标为j，然后将其插入到j的位置即可；
因为前面的插入，导致后面元素向后推移一个位置，没关系，把原来下标i的元素弹出即可；
重复进行第2步到第4步，直到乱序序列中的元素被全部插入到有序序列中；
经过以上5个步骤之后，整体序列必然有序，排序完成。
# 直接插入排序
def insertSort(relist): len_ = len(relist) for i in range(1,len_): for j in range(i): if relist[i] < relist[j]: relist.insert(j,relist[i]) # 首先碰到第一个比自己大的数字，赶紧刹车，停在那，所以选择insert relist.pop(i+1) # 因为前面的insert操作，所以后面位数+1，这个位置的数已经insert到前面去了，所以pop弹出 break return relist print insertSort([1,5,2,6,9,3])
4 归并排序
归并排序从小到大排序：首先让数组中的每一个数单独成为长度为1的区间，然后两两一组有序合并，得到长度为2的有序区间，依次进行，直到合成整个区间。
假设我们有一个没有排好序的序列(14,12,15,13,11,16)，那么首先我们使用分割的办法将这个序列分割成一个个已经排好序的子序列。然后再利用归并的方法将一个个的子序列合并成排序好的序列。分割和归并的过程可以看下面的图例。这样通过先递归的分解数列，再合并数列就完成了归并排序。
通过对若干个有序结点序列的归并来实现排序。
所谓归并是指将若干个已排好序的部分合并成一个有序的部分。
归并排序基本思想
设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。
在具体的合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字，取关键字较小（或较大）的记录复制到 temp[p] 中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到 array 中即可。
若将两个有序表合并成一个有序表，称为2-路归并。
def merge(left,right): result = [] while left and right: result.append(left.pop(0) if left[0] <= right[0] else right.pop(0)) while left: result.append(left.pop(0)) while right: result.append(right.pop(0)) return result def mergeSort(relist): if len(relist) <= 1: return relist mid_index = len(relist)/2 left = mergeSort(relist[:mid_index]) # 递归拆解的过程 right = mergeSort(relist[mid_index:]) return merge(left,right) # 合并的过程 print mergeSort([1,5,2,6,9,3])
5 快速排序
快速排序从小到大排序：在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边，大于此数的放在右边，再对数组两边递归调用快速排序，重复这个过程。
通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
# 快排 分片的思想+递归的思想，这是取了第一个为基准值，栈高为O(log(n)),栈长O(n),所以运行时间为栈高x栈长，也就是算法平均运算时间为O(nlog(n))
def quickSort(array): if len(array) < 2: return array else: pivot = array[0] less = [i for i in array[1:] if i < pivot] greater = [j for j in array[1:] if j > pivot] return quickSort(less) + [pivot] + quickSort(greater) print quickSort([1,5,2,6,9,3])
6 堆排序
堆排序从小到大排序：首先将数组元素建成大小为n的大顶堆，堆顶（数组第一个元素）是所有元素中的最大值，将堆顶元素和数组最后一个元素进行交换，再将除了最后一个数的n-1个元素建立成大顶堆，再将最大元素和数组倒数第二个元素进行交换，重复直至堆大小减为1。
注：完全二叉树
假设二叉树深度为n，除了第n层外，n-1层节点都有两个孩子，第n层节点连续从左到右。
在这里我们借用wiki的定义来说明：
通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中
(1)父节点i的左子节点在位置(2*i+1);
(2)父节点i的右子节点在位置(2*i+2);
(3)子节点i的父节点在位置floor((i-1)/2);
堆操作
堆可以分为大根堆和小根堆，这里用最大堆的情况来定义操作:
(1)最大堆调整(MAX_Heapify):将堆的末端子节点作调整，使得子节点永远小于父节点。这是核心步骤，在建堆和堆排序都会用到。比较i的根节点和与其所对应i的孩子节点的值。当i根节点的值比左孩子节点的值要小的时候，就把i根节点和左孩子节点所对应的值交换，当i根节点的值比右孩子的节点所对应的值要小的时候，就把i根节点和右孩子节点所对应的值交换。然后再调用堆调整这个过程，可见这是一个递归的过程。
(2)建立最大堆(Build_Max_Heap):将堆所有数据重新排序。建堆的过程其实就是不断做最大堆调整的过程，从len/2出开始调整，一直比到第一个节点。
(3)堆排序(HeapSort):移除位在第一个数据的根节点，并做最大堆调整的递归运算。堆排序是利用建堆和堆调整来进行的。首先先建堆，然后将堆的根节点选出与最后一个节点进行交换，然后将前面len-1个节点继续做堆调整的过程。直到将所有的节点取出，对于n个数我们只需要做n-1次操作。
在介绍堆排序之前，首先需要说明一下，堆是个什么玩意儿。
堆是一棵顺序存储的完全二叉树。
其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
举例来说，对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;
如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。
堆中有两个父结点，元素3和元素8。
元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。
元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：
设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2*i+1];
(2) 它的右孩子结点是：R[2*i+2];
(3) 它的父结点是：R[(i-1)/2];
(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
要点
首先，按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；
然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；
如此反复，直到交换了R[0]和R[1]为止。
以上思想可归纳为两个操作：
（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。
当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。
创建最大堆:将堆所有数据重新排序，使其成为最大堆
最大堆调整:作用是保持最大堆的性质，是创建最大堆的核心子程序
堆排序:移除位在第一个数据的根节点，并做最大堆调整的递归运算
import random def MAX_Heapify(heap,HeapSize,root):#在堆中做结构调整使得父节点的值大于子节点 left = 2*root + 1 right = left + 1 larger = root if left < HeapSize and heap[larger] < heap[left]: larger = left if right < HeapSize and heap[larger] < heap[right]: larger = right if larger != root:#如果做了堆调整则larger的值等于左节点或者右节点的，这个时候做对调值操作 heap[larger],heap[root] = heap[root],heap[larger] MAX_Heapify(heap, HeapSize, larger) def Build_MAX_Heap(heap):#构造一个堆，将堆中所有数据重新排序 HeapSize = len(heap)#将堆的长度当独拿出来方便 for i in xrange((HeapSize -2)//2,-1,-1):#从后往前出数 MAX_Heapify(heap,HeapSize,i) def HeapSort(heap):#将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。 Build_MAX_Heap(heap) for i in range(len(heap)-1,-1,-1): heap[0],heap[i] = heap[i],heap[0] MAX_Heapify(heap, i, 0) return heap if __name__ == '__main__': a = [30,50,57,77,62,78,94,80,84] print a HeapSort(a) print a b = [random.randint(1,1000) for i in range(1000)] #print b HeapSort(b) print b
7 希尔排序
希尔排序是插入排序改良的算法，希尔排序步长从大到小调整，第一次循环后面元素逐个和前面元素按间隔步长进行比较并交换，直至步长为1，步长选择是关键。
希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。–From排序四 希尔排序
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法。
def shell_sort(relist): n = len(relist) gap = n/2 # 初始步长 while gap > 0: for i in range(gap, n): temp = relist[i] # 每个步长进行插入排序 j = i # 插入排序 while j >= gap and relist[j - gap] > temp: relist[j] = relist[j - gap] j -= gap relist[j] = temp gap = gap/2 # 得到新的步长 return relist print shell_sort([1,5,2,6,9,3])