归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型的应用。它的基本操作是：将已有的子序列合并，达到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
归并排序其实要做两件事：
分解----将序列每次折半拆分
合并----将划分后的序列段两两排序合并因此，归并排序实际上就是两个操作，拆分+合并
如何合并？L[first...mid]为第一段，L[mid+1...last]为第二段，并且两端已经有序，现在我们要将两端合成达到L[first...last]并且也有序。
首先依次从第一段与第二段中取出元素比较，将较小的元素赋值给temp[]
重复执行上一步，当某一段赋值结束，则将另一段剩下的元素赋值给temp[]
此时将temp[]中的元素复制给L[]，则得到的L[first...last]有序
如何分解？在这里，我们采用递归的方法，首先将待排序列分成A,B两组；然后重复对A、B序列分组；直到分组后组内只有一个元素，此时我们认为组内所有元素有序，则分组结束。
代码实现
# 归并排序 #这是合并的函数 # 将序列L[first...mid]与序列L[mid+1...last]进行合并 def mergearray(L,first,mid,last,temp): #对i,j,k分别进行赋值 i,j,k = first,mid+1,0 #当左右两边都有数时进行比较，取较小的数 while (i <= mid) and (j <= last): if L[i] <= L[j]: temp[k] = L[i] i = i+1 k = k+1 else: temp[k] = L[j] j = j+1 k = k+1 #如果左边序列还有数 while (i <= mid): temp[k] = L[i] i = i+1 k = k+1 #如果右边序列还有数 while (j <= last): temp[k] = L[j] j = j+1 k = k+1 #将temp当中该段有序元素赋值给L待排序列使之部分有序 for x in range(0,k): L[first+x] = temp[x] # 这是分组的函数 def merge_sort(L,first,last,temp): if first < last: mid = (int)((first + last) / 2) #使左边序列有序 merge_sort(L,first,mid,temp) #使右边序列有序 merge_sort(L,mid+1,last,temp) #将两个有序序列合并 mergearray(L,first,mid,last,temp) # 归并排序的函数 def merge_sort_array(L): #声明一个长度为len(L)的空列表 temp = len(L)*[None] #调用归并排序 merge_sort(L,0,len(L)-1,temp) 基数排序
算法思想
基数排序.gif
基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[ ]对新形成的序列L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位，则排序结束
根据上述“基数排序”的展示，我们可以清楚的看到整个实现的过程
代码实现
#************************基数排序**************************** #确定排序的次数 #排序的顺序跟序列中最大数的位数相关 def radix_sort_nums(L): maxNum = L[0] #寻找序列中的最大数 for x in L: if maxNum < x: maxNum = x #确定序列中的最大元素的位数 times = 0 while (maxNum > 0): maxNum = (int)(maxNum/10) times = times+1 return times #找到num从低到高第pos位的数据 def get_num_pos(num,pos): return ((int)(num/(10**(pos-1))))%10 #基数排序 def radix_sort(L): count = 10*[None] #存放各个桶的数据统计个数 bucket = len(L)*[None] #暂时存放排序结果 #从低位到高位依次执行循环 for pos in range(1,radix_sort_nums(L)+1): #置空各个桶的数据统计 for x in range(0,10): count[x] = 0 #统计当前该位(个位，十位，百位....)的元素数目 for x in range(0,len(L)): #统计各个桶将要装进去的元素个数 j = get_num_pos(int(L[x]),pos) count[j] = count[j]+1 #count[i]表示第i个桶的右边界索引 for x in range(1,10): count[x] = count[x] + count[x-1] #将数据依次装入桶中 for x in range(len(L)-1,-1,-1): #求出元素第K位的数字 j = get_num_pos(L[x],pos) #放入对应的桶中，count[j]-1是第j个桶的右边界索引 bucket[count[j]-1] = L[x] #对应桶的装入数据索引-1 count[j] = count[j]-1 # 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表 for x in range(0,len(L)): L[x] = bucket[x] 后记写完之后运行了一下时间比较：