经典排序算法及其python实现。
这是常见的几种排序算法,另外还有归并排序:
之后我将以此介绍每种排序算法并用python实现。
由于排序问题的计算时间下界是O(nlogn),所以归并排序和快速排序都是渐进最优排序算法。
插入排序是将一个数插入到已经排好序的序列中 L。升序排列的具体步骤是:
(1)外循环:依次遍历每一个元素;
(2)当某个位置 k 上的数小于它相邻的前面位置 k - 1 的数,则开始依次比较;
(3)内循环:将 L[k] 和前面的每个位置(逆序比较,依次为 k-1,k-2,…)的数进行比较,如果小于,就交换两个位置的数,继续比较;如果大于,就停止内循环;
空间复杂度:交换两个位置的数值时,需要1个临时空间,所以空间复杂度为 1 。
时间复杂度:排序经历内外循环,所以时间复杂度是n方。
#coding:utf-8 num = raw_input("输入需要排序的数字集合,以空格分隔:") num_list = num.split() num_list = [int(i) for i in num_list] for i in range(1,len(num_list)): if num_list[i-1] > num_list[i]: temp = num_list[i] index = i while temp < num_list[index-1] and index > 0: num_list[index] = num_list[index-1] index -= 1 num_list[index] = temp print "res",num_list
冒泡排序是参照水中气泡依次往上冒得情景得来的。例如,从前往后依次将大数移动到后面,这样一轮下来,最大的数肯定在最后。
我觉得插入排序和冒泡排序的关键步骤很像:都是相邻数之间的比较;都需要经历内外循环;一个是将大数往后移动,一个是将小数往前移动。
具体步骤如下:
(1)外循环:主要是用来控制内循环的次数 i ,一共经历 n 轮训还;
(2)内循环:每次都从位置 i = 0 开始比较,如果 L[ i ] > L [i + 1],就将L[ i ]元素和 L [i + 1]元素交换,相当于大的数向后移动了一位,然后继续移动 i + 1,依次比较,知道这轮循环结束,最大的数肯定在 L [ n-1 ]处;
(3)注意:在内循环时有一个缩短时间的方法,就是在控制循环次数时,不在考虑之前已经排好序的“大数”,也就是从后往前已经排好序的数。经过每轮外循环,都会有一个排好序的大数。
空间复杂度:交换两个位置的数值时,需要1个临时空间,所以空间复杂度为 1 。
时间复杂度:排序经历内外循环,所以时间复杂度是n方。
#coding:utf-8 num = raw_input("输入要排序的数字集合,以空格分隔:") number = [int(i) for i in num.split()] count = 0 for i in range(0,len(number)): count += 1 for j in range(len(number)-1-i): #如果没有-i,那么最坏复杂度是n方 count += 1 if number[j] > number[j+1]: temp = number[j] number[j] = number[j+1] number[j+1] = temp print number print count ''' input:9 8 7 6 5 4 3 2 1 count:45 去掉第二个for循环的-i,结果count=81 '''
从所有序列中先找到最小的,然后放到第一个位置。之后再看剩余元素中最小的,放到第二个位置……以此类推,就可以完成整个的排序工作了。可以很清楚的发现,选择排序是固定位置,找元素。相比于插入排序的固定元素找位置,是两种思维方式。
具体步骤如下:
(1)外循环:固定某个位置,从 i =0 开始,然后再在内循环中找对应位置的元素,到i = n-1 结束;
(2)内循环:找到位置 i 之后的所有数中最小的数,和 位置 i 的数交换;
空间复杂度:交换两个位置的数值时,需要1个临时空间,所以空间复杂度为 1 。
时间复杂度:排序经历内外循环,所以时间复杂度是n方。
#coding:utf-8 num = raw_input("请输入要排序的集合,用空格分隔:") data = [int(i) for i in num.split()] for i in range(len(data)): minest = data[i] index = i for j in range(i+1,len(data)): if data[j] < minest: minest = data[j] index = j temp = data[i] data[i] = minest data[index] = temp data = [str(k) for k in data] print " ".join(data)
快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“分治”的思想。
具体步骤如下:
(1)外循环:令列表第一个元素作为基准点base;
(2)内循环:设置两个指针 i 和 j , j 先从后往前找 比base小的数,找到后,i 从前往后找比base 大的元素,直到都找到了,然后交换两个位置的元素;如果还没有找到同时符合条件的元素,却有 i = j ,则有两种情况发生:j 移动到了一个符合条件的位置后, i 也移动过来了,此时可以交换 base 和 i 位置的元素;另一种是,j 一直移动都没有找到符合条件的元素,此时已经到了base,也就是 i 的初始位置,此时也可以交换 i 和base位置的元素,因为他们是同一个元素。综上,只要 i=j ,就可以交换 i 和base的元素。
(3)一轮结束后,基准点已经移动到了合适的位置:左边的元素比它小,右边的元素比它大,但是左边的元素之间还没有排序,还需要递归的调用刚才的内循环的方法,参数分别为左右两侧的信息。
时间复杂度:快速排序的交换跨度大于插入排序和冒泡排序的交换跨度,但是如果选取的基准是最大值或者最小值的话,存在一种情况,i 或 j 位置的元素会一直和 base基准元素交换位置,而不是i 和 j 位置交换元素,这样导致快排和之前的相邻元素比较的算法差别不大,所以最坏情况的复杂度是 n 方;最好情况下,每次找到的基准点都可以平均划分后面的元素,时间减少。
空间复杂度:由于每次确定基准点后,都需要对后面的数进行交换,所以空间复杂度为 n 。
#coding:utf-8 num = raw_input("请输入要排序的集合,用空格分隔:") data = [int(i) for i in num.split()] def q_sort(L,left,right): if left >= right: return base = L[left] i = left j = right while i != j: while L[j] >= base and i < j: j -= 1 while L[i] <= base and i < j: i += 1 if (i < j): temp = L[j] #交换 i ,j 位置的元素 L[i] = L[j] L[j] = temp L[left] = L[i] L[i] = base if left < right: q_sort(L,left,i-1) q_sort(L,j+1,right) q_sort(data,0,len(data)-1) data = [str(i) for i in data] print " ".join(data)
归并排序也是采用分治的思想实现对n个元素进行排序。具体实现步骤是:
(1)外循环:将元素集合递归的划分成大致相等的两个子集合,直到不能划分;
(2)内循环:合并两个有序子集合得到一个大的有序集合,即比较每个元素。在这个过程中,产生一个新的数组b,用于存放排好序的元素集合。
时间复杂度: 递归的划分元素集合瞎相当于两个一半元素的时间复杂度,而合并和复制操作可在O(n)时间完成,所以T(n) = 2 T(n/2) + O(n),求解后是O(nlogn)。
空间复杂度:归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间:n + logn;所以空间复杂度为: O(n)。
以时间换空间: 我看到网上很多blog分享空间复杂度只有O(1)的归并排序法;因为传统的归并排序所消耗的空间主要是在归并函数(把两个有序的函数合并成一个有序的函数),所以如果要让时间复杂度为 O(1) ,那么也只能在归并函数中做文章了。代码就不列出来了,其主要思想就是借助于快速排序(其实就是相当于归并函数被快速排序函数替换了);这样的方法虽然可以减少内存的消耗,但是却会在时间上带来损失,因为这样时间复杂度却变成了 O(n^2) 了;所以这种方法并不是一个两全其美的idea;
#coding:utf-8 def merge(a,left,mid,right): #合并两个排好序的数组 b = [] #空间:O(n) i = left j = mid + 1 while i <= mid and j <= right: if a[i] <= a[j]: b.append(a[i]) i += 1 else: b.append(a[j]) j += 1 if i <= mid: for k in a[i:mid+1]: b.append(k) if j <= right: for k in a[mid+1:right+1]: b.append(k) print "b",b return b def mergeSort(a,left,right): if left < right: mid = (left + right)/2 mergeSort(a,left,mid) #T(n/2) mergeSort(a,mid+1,right) #T(n/2) print "merge",a,left,mid,right b = merge(a,left,mid,right) for j in range(len(b)): a[left + j] = b[j] else: return num = raw_input() data = [int(i) for i in num.split()] mergeSort(data,0,len(data)-1) print data
用1次对集合的扫描找出所有已经排好序的子集合,然后再将相邻的子集合进行两两合并。其中,和归并算法相较,merge步骤是不变的,只是mergeSort方法改变。在极端情况下,如果给定数组有序,那么自然合并算法不需要执行合并步,而mergeSort还需要执行logn次合并。通常情况下,自然合并算法的合并次数较少。