总结了一下常见集中排序的算法
归并排序
归并排序也称合并排序, 是分治法的典型应用分治思想是将每个问题分解成个个小问题, 将每个小问题解决, 然后合并
具体的归并排序就是, 将一组无序数按 n/2 递归分解成只有一个元素的子项, 一个元素就是已经排好序的了然后将这些有序的子元素进行合并
合并的过程就是 对 两个已经排好序的子序列, 先选取两个子序列中最小的元素进行比较, 选取两个元素中最小的那个子序列并将其从子序列中
去掉添加到最终的结果集中, 直到两个子序列归并完成
代码如下:
- #!/usr/bin/python
- import sys
- def merge(nums, first, middle, last):
- '''''merge'''
- # 切片边界, 左闭右开并且是了 0 为开始
- lnums = nums[first:middle+1]
- rnums = nums[middle+1:last+1]
- lnums.append(sys.maxint)
- rnums.append(sys.maxint)
- l = 0
- r = 0
- for i in range(first, last+1):
- if lnums[l] < rnums[r]:
- nums[i] = lnums[l]
- l+=1
- else:
- nums[i] = rnums[r]
- r+=1
- def merge_sort(nums, first, last):
- ''''' merge sort
merge_sort 函数中传递的是下标, 不是元素个数
- '''
- if first < last:
- middle = (first + last)/2
- merge_sort(nums, first, middle)
- merge_sort(nums, middle+1, last)
- merge(nums, first, middle,last)
- if __name__ == '__main__':
- nums = [10,8,4,-1,2,6,7,3]
- print 'nums is:', nums
- merge_sort(nums, 0, 7)
- print 'merge sort:', nums
稳定, 时间复杂度 O(nlog n)
插入排序
代码如下:
- #!/usr/bin/python
- import sys
- def insert_sort(a):
''''' 插入排序
有一个已经有序的数据序列, 要求在这个已经排好的数据序列中插入一个数,
但要求插入后此数据序列仍然有序刚开始 一个元素显然有序, 然后插入一
个元素到适当位置, 然后再插入第三个元素, 依次类推
- '''
- a_len = len(a)
- if a_len = 0 and a[j] > key:
- a[j+1] = a[j]
- j-=1
- a[j+1] = key
- return a
- if __name__ == '__main__':
- nums = [10,8,4,-1,2,6,7,3]
- print 'nums is:', nums
- insert_sort(nums)
- print 'insert sort:', nums
稳定, 时间复杂度 O(n^2)
交换两个元素的值 python 中你可以这么写: a, b = b, a, 其实这是因为赋值符号的左右两边都是元组
(这里需要强调的是, 在 python 中, 元组其实是由逗号, 来界定的, 而不是括号)
选择排序
选择排序 (Selection sort) 是一种简单直观的排序算法它的工作原理如下首先在未排序序列中找到最小 (大) 元素, 存放到
排序序列的起始位置, 然后, 再从剩余未排序元素中继续寻找最小 (大) 元素, 然后放到已排序序列的末尾以此类推, 直到所
有元素均排序完毕
- import sys
- def select_sort(a):
''''' 选择排序
每一趟从待排序的数据元素中选出最小 (或最大) 的一个元素,
顺序放在已排好序的数列的最后, 直到全部待排序的数据元素排完
选择排序是不稳定的排序方法
- '''
- a_len=len(a)
- for i in range(a_len):# 在 0-n-1 上依次选择相应大小的元素
- min_index = i# 记录最小元素的下标
- for j in range(i+1, a_len):# 查找最小值
- if(a[j]<a[min_index]):
- min_index=j
- if min_index != i:# 找到最小元素进行交换
- a[i],a[min_index] = a[min_index],a[i]
- if __name__ == '__main__':
- A = [10, -3, 5, 7, 1, 3, 7]
- print 'Before sort:',A
- select_sort(A)
- print 'After sort:',A
不稳定, 时间复杂度 O(n^2)
希尔排序
希尔排序, 也称递减增量排序算法, 希尔排序是非稳定排序算法该方法又称缩小增量排序, 因 DL.Shell 于 1959 年提出而得名
先取一个小于 n 的整数 d1 作为第一个增量, 把文件的全部记录分成 d1 个组所有距离为 d1 的倍数的记录放在同一个组中先在各组内进行排序;
然后, 取第二个增量 d2<d1 重复上述的分组和排序, 直至所取的增量 dt=1(dt<dt-l<<d2<d1), 即所有记录放在同一组中进行直接插入排序为止
- import sys
- def shell_sort(a):
- '''''shell 排序'''
- a_len=len(a)
- gap=a_len/2# 增量
- while gap>0:
- for i in range(a_len):# 对同一个组进行选择排序
- m=i
- j=i+1
- while j<a_len:
- if a[j]<a[m]:
- m=j
- j+=gap#j 增加 gap
- if m!=i:
- a[m],a[i]=a[i],a[m]
- gap/=2
- if __name__ == '__main__':
- A = [10, -3, 5, 7, 1, 3, 7]
- print 'Before sort:',A
- shell_sort(A)
- print 'After sort:',A
不稳定, 时间复杂度 平均时间 O(nlogn) 最差时间 O(n^s)1<s<2
堆排序 ( Heap Sort )
" 堆的定义: 在起始索引为 0 的堆中:
节点 i 的右子节点在位置 2 * i + 24) 节点 i 的父节点在位置 floor( (i - 1) / 2 ) : 注 floor 表示取整操作
堆的特性:
每个节点的键值一定总是大于 (或小于) 它的父节点
最大堆:
堆的根节点保存的是键值最大的节点即堆中每个节点的键值都总是大于它的子节点
上移, 下移 :
当某节点的键值大于它的父节点时, 这时我们就要进行上移操作, 即我们把该节点移动到它的父节点的位置, 而让它的父节点到它的位置上, 然后我们继续判断该节点, 直到该节点不再大于它的父节点为止才停止上移
现在我们再来了解一下下移操作当我们把某节点的键值改小了之后, 我们就要对其进行下移操作
方法:
我们首先建立一个最大堆(时间复杂度 O(n)), 然后每次我们只需要把根节点与最后一个位置的节点交换, 然后把最后一个位置排除之外, 然后把交换后根节点的堆进行调整(时间复杂度 O(lgn) ), 即对根节点进行下移操作即可 堆排序的总的时间复杂度为 O(nlgn).
代码如下:
- #!/usr/bin env python
- # 数组编号从 0 开始
- def left(i):
- return 2*i +1
- def right(i):
- return 2*i+2
- # 保持最大堆性质 使以 i 为根的子树成为最大堆
- def max_heapify(A, i, heap_size):
- if heap_size <= 0:
- return
- l = left(i)
- r = right(i)
- largest = i # 选出子节点中较大的节点
- if l A[largest]:
- largest = l
- if r A[largest]:
- largest = r
- if i != largest :# 说明当前节点不是最大的, 下移
- A[i], A[largest] = A[largest], A[i] #交换
- max_heapify(A, largest, heap_size)# 继续追踪下移的点
- #print A
- # 建堆
- def bulid_max_heap(A):
- heap_size = len(A)
- if heap_size >1:
- node = heap_size/2 -1
- while node >= 0:
- max_heapify(A, node, heap_size)
- node -=1
- # 堆排序 下标从 0 开始
- def heap_sort(A):
- bulid_max_heap(A)
- heap_size = len(A)
- i = heap_size - 1
- while i > 0 :
- A[0],A[i] = A[i], A[0] # 堆中的最大值存入数组适当的位置, 并且进行交换
- heap_size -=1 # heap 大小 递减 1
- i -= 1 # 存放堆中最大值的下标递减 1
- max_heapify(A, 0, heap_size)
- if __name__ == '__main__' :
- A = [10, -3, 5, 7, 1, 3, 7]
- print 'Before sort:',A
- heap_sort(A)
- print 'After sort:',A
不稳定, 时间复杂度 O(nlog n)
快速排序
快速排序算法和合并排序算法一样, 也是基于分治模式对子数组 A[p...r]快速排序的分治过程的三个步骤为:
分解: 把数组 A[p...r]分为 A[p...q-1]与 A[q+1...r]两部分, 其中 A[p...q-1]中的每个元素都小于等于 A[q]而 A[q+1...r]中的每个元素都大于等于 A[q];
解决: 通过递归调用快速排序, 对子数组 A[p...q-1]和 A[q+1...r]进行排序;
合并: 因为两个子数组是就地排序的, 所以不需要额外的操作
对于划分 partition 每一轮迭代的开始, x=A[r], 对于任何数组下标 k, 有:
1) 如果 pki, 则 A[k]x
2) 如果 i+1kj-1, 则 A[k]>x
3) 如果 k=r, 则 A[k]=x
代码如下:
- #!/usr/bin/env python
- # 快速排序
- '''''
划分 使满足 以 A[r]为基准对数组进行一个划分, 比 A[r]小的放在左边,
比 A[r]大的放在右边
快速排序的分治 partition 过程有两种方法,
一种是上面所述的两个指针索引一前一后逐步向后扫描的方法,
另一种方法是两个指针从首位向中间扫描的方法
- '''
- #p,r 是数组 A 的下标
- def partition1(A, p ,r):
- '''''方法一,
- 两个指针索引一前一后逐步向后扫描的方法'''
- x = A[r]
- i = p-1
- j = p
- while j < r:
- if A[j] < x:
- i +=1
- A[i], A[j] = A[j], A[i]
- j += 1
- A[i+1], A[r] = A[r], A[i+1]
- return i+1
- def partition2(A, p, r):
- '''''两个指针从首尾向中间扫描的方法'''
- i = p
- j = r
- x = A[p]
- while i = x and i < j:
- j -=1
- A[i] = A[j]
- while A[i]<=x and i < j:
- i +=1
- A[j] = A[i]
- A[i] = x
- return i
- # quick sort
- def quick_sort(A, p, r):
- '''''快速排序的最差时间复杂度为O(n2),
- 平时时间复杂度为O(nlgn)'''
- if p < r:
- q = partition2(A, p, r)
- quick_sort(A, p, q-1)
- quick_sort(A, q+1, r)
- if __name__ == '__main__ ':
- A = [5,-4,6,3,7,11,1,2]
- print 'Before sort: ',A
- quick_sort(A, 0, 7)
- print 'After sort: ',A'
不稳定, 时间复杂度 最理想 O(nlogn)最差时间 O(n^2)
说下 python 中的序列:
列表元组和字符串都是序列, 但是序列是什么, 它们为什么如此特别呢? 序列的两个主要特点是索引操作符和切片操作符索引操作符让我们可以从序列中抓取一个特定项目切片操作符让我们能够获取序列的一个切片, 即一部分序列, 如: a = ['aa','bb','cc'], print a[0] 为索引操作, print a[0:2]为切片操作
来源: http://www.jqhtml.com/11492.html