1 # 冒泡算法:是一种简单排序,重复的遍历要排序的数列,一次比较两种元素,如果顺序错误,就交换两者的位置,重复的的进行知道没有在需要交换 2 # 步骤如下: 3 # 冒泡排序算法的运作如下： 4 # 第一次进行遍历,进行n-1次两两比较,将最大(小)的元素,进行放入最后一位,下一次,对前n-2的元素进行两两进行比较.放入最后第二位.... 5 # 时间复杂度为:(稳定) 6 # 最小为o(n),即该序列的有序的序列,最大为o(n),即,第一次要n-1,n-2,n-3...即最大为o(n^2) 7 import random 8 def produce_num(n): 9 return_nums=[] 10 for i in range(n): 11 num=random.randint(1,n) 12 return_nums.append(num) 13 return return_nums 14 def bubble_sort_high(list_): 15 # 进行升序排序 16 # 控制循环轮数 17 for i in range(len(list_)-1): 18 # 每一次遍历,两两比较,得到最大(小)的元素放入,当前循环长度的最后一位 19 for j in range(len(list_)-i-1): 20 # 如果取出的元素大于剩余的元素,则进行交换元素 21 if list_[j]>list_[j+1]: 22 temp=list_[j+1] 23 list_[j+1]=list_[j] 24 list_[j]=temp 25 return list_ 26 def bubble_sort_low(list_): 27 # 进行降序排序 28 for i in range(len(list_)-1): 29 for j in range(len(list_)-i-1): 30 if list_[j]<list_[j+1]: 31 temp=list_[j] 32 list_[j+1]=list_[j] 33 list_[j]=temp 34 return list_
1 # 选择排序: 2 # 原理:第一次从下标为0的开始下标为0的这个数与后面的n-1个进行比较；找出最小或者最大的放在下标为0的这个位置；第二次从下标为1的开始比较；查询剩下的最大或者最小值；放在 下标为1的位置；以此类推；直到排序完成 3 # 时间复杂度 4 # 最优时间复杂度：O(n^2) 5 # 最坏时间复杂度：O(n^2) 6 # 稳定性：不稳定（考虑升序每次选择最大的情况） 7 import random 8 def produce_num(n): 9 return_nums=[] 10 for i in range(n): 11 num=random.randint(1,n) 12 return_nums.append(num) 13 return return_nums 14 def choose_sort_high(list_): 15 # 进行升序排序 16 # 控制循环轮数 17 for i in range(len(list_)-1): 18 # 获得第一个元素,将其与剩余的元素进行比较,如果大于即交换位置 19 for j in range(i+1,len(list_)): 20 if list_[i]>list_[j]: 21 temp=list_[j] 22 list_[j]=list_[i] 23 list_[i]=temp 24 return list_ 25 def choose_sort_low(list_): 26 # 进行降序排序 27 for i in range(len(list_)-1): 28 for j in range(i+1,len(list_)): 29 if list_[i]<list_[j]: 30 temp=list_[j] 31 list_[j]=list_[i] 32 list_[i]=temp 33 return list_ 34 35 nums=produce_num(10) 36 num=choose_sort_low(nums) 37 print num
1 # 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2 # 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。） 3 #最优时间复杂度：O(n) （升序排列，序列已经处于升序状态） 4 #最坏时间复杂度：O(n2) 5 #稳定性：稳定 6 7 #比较次数：在第一轮排序中，插入排序最多比较一次；在第二轮排序中插入排序最多比较二次；以此类推，最后一轮排序时，最多比较N-1次，因此插入排序的最多比较次数为1+2+...+N-1=N*(N-1)/2。尽管如此，实际上插入排序很少会真的比较这么多次，因为一旦发现左侧有比目标元素小的元素，比较就停止了，因此，插入排序平均比较次数为N*(N-1)/4。 8 9 #移动次数：插入排序的移动次数与比较次数几乎一致，但移动的速度要比交换的速度快得多。 10 11 #综上，插入排序的速度约比冒泡排序快一倍（比较次数少一倍），比选择排序还要快一些，对于基本有序的数据，插入排序的速度会很快，是简单排序中效率最高的排序算法。 12 def insert_sort_high(list_): 13 # 进行升序排序 14 print '原始序列',list_ 15 # 原始序列被分为,i的左边为有序,右边为无序 16 for i in range(1,len(list_)): 17 x=list_[i] 18 j=i 19 # 对左边元素(j-1)与x比较,小于则j-1往前一位 20 while j>0 and x<list_[j-1]: 21 list_[j]=list_[j-1] 22 j-=1 23 if j!=i: 24 list_[j]=x 25 return list_
目录
- 快速排序的介绍
- 快速排序的Python实现
快速排序的介绍
快速排序(quick sort)的采用了分治的策略。
- 分治策略指的是：
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 - 快排的基本思想是：
在序列中找一个划分值，通过一趟排序将未排序的序列排序成 独立的两个部分，其中左边部分序列都比划分值小，右边部分的序列比划分值大，此时划分值的位置已确认，然后再对这两个序列按照同样的方法进行排序，从而达到整个序列都有序的目的。 -
基准值若能把数据分为平均的两块，划分次数O(logn)，每次划分遍历比较一遍O(n)，时间复杂度O(nlogn)。
额外空间开销出在暂存基准值，O(logn)次划分需要O(logn)个，空间复杂度O(logn)
快速排序的Python实现
主要体现在以下方面：
- 分组基准的选取过于随便，不一定可以取到列表的中间值
- 空间复杂度大，使用了两个列表解析式，而且每次选取进行比较时需要遍历整个序列。
- 若序列长度过于小(比如只有几个元素)，快排效率就不如插入排序了。
- 递归影响性能，最好进行优化。
下面用Python写一个C风格的快排(这里可以体会到快排的精髓)：
def quick_sort(L): return q_sort(L, 0, len(L) - 1) def q_sort(L, left, right): if left < right: pivot = Partition(L, left, right) q_sort(L, left, pivot - 1) q_sort(L, pivot + 1, right) return L def Partition(L, left, right): pivotkey = L[left] while left < right: while left < right and L[right] >= pivotkey: right -= 1 L[left] = L[right] while left < right and L[left] <= pivotkey: left += 1 L[right] = L[left] L[left] = pivotkey return left L = [5, 9, 1, 11, 6, 7, 2, 4] print quick_sort(L)
快速排序需要提供三个参数：待排序序列 、序列最小下标值left、序列最大下标值right。让用户提供这三个参数很麻烦。这里写个函数进行封装：
def quick_sort(L): return q_sort(L, 0, len(L) - 1)
下面看一下q_sort函数：
def q_sort(L, left, right): if left < right: pivot = Partition(L, left, right) q_sort(L, left, pivot - 1) q_sort(L, pivot + 1, right) return L
这个函数的核心是pivot = Partition(L, left, right)，在执行它之前，列表的值为[5, 9, 1, 11, 6, 7, 2, 4]，而Partition函数做的事情是找到一个分组标准，然后进行分组，让它左边的值比它小，右边的值比它大。
在经过Partition函数分组后，列表变为[4, 2, 1, 5, 6, 7, 11, 9]，并把5的下标值(也就是3)返回给pivot，此时列表变成两个小列表[4, 2, 1]和[5, 6, 7, 11, 9] ，之后调用q_sort，就是调用q_sort(L,0, 2)和q_sort(L, 4 ,7)，对其进行Partition操作，直到整个列表有序为止。
下面看看关键的Partition函数是如何做的：
def Partition(L, left, right): pivotkey = L[left] while left < right: while left < right and L[right] >= pivotkey: right -= 1 L[left] = L[right] while left < right and L[left] <= pivotkey: left += 1 L[right] = L[left] L[left] = pivotkey return left
以一趟排序为例[5, 9, 1, 11, 6, 7, 2, 4]：
-
开始排序时，left=0，right=7，首先用表的第一个下标值作为 分组关键字pivot，
第一趟排序过程 -
进行
while left < right and L[right] >= pivotkey:判断，其中L[right]=4 不满足条件，跳出循环，执行L[left] = L[right]，执行后列表变成：
第一趟排序结果 -
然后进行
while left < right and L[left] <= pivotkey:，L[left] = 4 <= 5，条件成立，left向右边移动，然后L[left] = 9 不满足条件，执行L[right] = L[left]，执行后列表变为：
第一趟排序过程 -
然后进行
while left < right判断，条件成立，继续进行判断while left < right and L[right] >= pivotkey:，L[right] = 9，满足条件，right向左移动1，继续判断，不满足条件，执行L[left] = L[right]，执行后列表变为：
第一趟排序过程 -
然后进行
while left < right and L[left] <= pivotkey:判断，L[left] = 2,满足条件，left向右移动，然后L[left] = 1，满足条件，left向右移动，L[left] = 11，不满足条件，执行L[right] = L[left]，执行后列表变为：
第一趟排序过程 -
然后进行
while left < right判断，条件成立，继续进行判断：while left < right and L[right] >= pivotkey:，满足条件，right向左移动，一直移动到这样的状态：
第一趟排序过程
此时不满足条件：left < right，跳出循环。然后执行L[left] = pivotkey，并返回left下标值。此时序列变为:
-
第一趟结束
接下来就是用递归分别对子列表进行排序。读者可以自己试试。
#完整代码 def quick_sort1(L): return q_sort(L,0,len(L)-1) # 起到分区作用 def q_sort(L,left,right): if left<right: pivot=Partition(L,left,right) # 递归解决 q_sort(L,left,pivot-1) q_sort(L,pivot+1,right) return L # 对区间选取第一个数作为pivotkey，进行划分区间 def Partition(L,left,right): # 选取第一个元素 pivotkey=L[left] # 退出条件根据当前pivotkey以确定其的左右区间，即left==right while left<right: # 选取区间最右边的一个数，进行与pivotkey进行比较，如果比pivotkey大，则对right索引进行往左移，（即该right索引对应的取值在pivotkey的右边） while left<right and L[right]>=pivotkey: right-=1 # 找到元素比当前pivotkey小，则对left位置的值进行替换（将right索引对应取值对left索引对应取值进行替换，）（1.第一次的left取值为pivotkey） L[left]=L[right] #从left索引开始，依次判断当前元素L[left]是否比pivotkey小，如比pivotkey大，则left索引往前右移。 while left<right and L[left]<=pivotkey: left+=1 # 找到元素，替换 L[right]=L[left] # 对上述流程总有两个位置的元素是相等的，因而在left==right的时候，对left的位置进行赋值pivotkey。 L[left]=pivotkey return left
归并排序：
有两种类型，一种递归和迭代，递归法的核心思想是把列表分解为两个子列表，单独排序子列表在合并子列表。你可以将他理解为一个二分树，其列表为根节点，，子列表为子节点。首先对子列表进行排序，然后进行归并子列表
迭代主要思想。将列表看成一个n个长度为1的子列表。然后，利用循环把相邻的两个子列表排序合并。然后可以得到n/2长度为2的子列表。之后，依次利用循环进行相邻的两个列表进行合并。最后得到一二长度为n的列表。想过程想象成一个倒二叉树，对独立的子列表进行多次得带，知道到达跟部。
归并排序划分子问题采用二分法，共需O(logn)次划分，当然需要相当次合并；每次合并遍历比较O(n)。时间复杂度O(nlogn)。
额外空间开销出在合并过程中的一个暂存数组，空间复杂度O(n)。
#递归
def mergeSort(myList): #传入参数myList
if len(myList)<2: #如果myList只有一个元素即停止
return
cut=len(myList)//2 #找到数据的二分点
listA=myList[:cut] #左子列表
listB=myList[cut:] #右子列表
mergeSort(listA) #将左子列表递归排序
mergeSort(listB)
#print(listA,listB)
pointerA=0 #指针A
pointerB=0 #指针B
counter=0 #排序后元素的位置
while pointerA<len(listA) and pointerB<len(listB): #两个指针没有走到尽头
if listA[pointerA]<listB[pointerB]: #比较元素的大小，将小的部分插入原列表counter位置
myList[counter]=listA[pointerA]
pointerA+=1
else:
myList[counter]=listB[pointerB]
pointerB+=1
counter+=1
while pointerA<len(listA): #如果一个指针走到尽头，那么另一个指针的元素必定都在counter的后面
myList[counter]=listA[pointerA]
pointerA+=1
counter+=1
while pointerB < len(listB):
myList[counter] = listB[pointerB]
pointerB += 1
counter += 1
#例子 myList=[23,5,2,8,21,3,4,11,19] mergeSort(myList) print(myList)
输出结果：
[23] [5] [2] [8] [5, 23] [2, 8] [21] [3] [11] [19] [4] [11, 19] [3, 21] [4, 11, 19] [2, 5, 8, 23] [3, 4, 11, 19, 21] [2, 3, 4, 5, 8, 11, 19, 21, 23]
迭代实现
#迭代实现 def mergeSort(mList): length=len(mList) # n为子数组长度，当n等于length时，即数组合并完成 n=1 while n<length: # 遍历整个数组，通过间隔为n*2 for i in range(0,length,n*2): listA=mList[i:i+n] listB=mList[i+n:i+n*2]
#print(listA,listB) # 指针A pointerA=0 # 指针B pointerB=0 # 排序后元素的位置 counter=i while pointerA<len(listA) and pointerB<len(listB): if listA[pointerA]<listB[pointerB]: mList[counter]=listA[pointerA] pointerA+=1 else: mList[counter]=listB[pointerB] pointerB+=1 counter+=1 while pointerA<len(listA): mList[counter]=listA[pointerA] counter+=1 pointerA+=1 while pointerB<len(listB): mList[counter]=listB[pointerB] counter+=1 pointerB+=1 # 一轮合并后子数组的长度是成倍增长 n=n*2
myList=[6,3,-2,0,-1,5,9,7] mergeSort(myList) print(myList)
#运行结果 [6] [3] [-2] [0] [-1] [5] [9] [7] [3, 6] [-2, 0] [-1, 5] [7, 9] [-2, 0, 3, 6] [-1, 5, 7, 9] [-2, -1, 0, 3, 5, 6, 7, 9]
递归第一步排序左子列表，第二步排序右子列表，迭代法每一步都排序所有的子列表，两者的时间复杂度是一样的。