收藏到CSDN网摘
归并排序(Merge sort)是另外一个很有名的排序算法.其思想是: divide and conquer.将原序列分割为2个小序列,排序之后再merge到一起.分割部分可以递归完成,递归出口是序列长度为1,直接返回序列.
Bottom_Up归并排序是归并排序的非递归实现,从size=2开始,不断merge,直到所有元素排序完毕.
快速排序(Quick sort)是对随机打乱后的数组,用2个指针分别从左边和右边来扫描元素,在排序过程中保证:对某个元素j,a[j]已经被排好,其左边所有元素都不大于它,而右边所有元素都不小于它.j这个位置由分割函数partition()返回.具体实现(随机排序可以不用,用median-3来选择一个元素作为a[lo]即可):
(a) partition分割(设置j)
i, j = lo, hi, 当i<j时,repeat:
- i从左往右scan,只要a[i]<a[lo],扫描停止时,a[i]>=a[lo]
- j从右往左scan,只要a[j]>a[lo],扫描停止时,a[j]<=a[lo]
- 交换a[i]与a[j]
- 循环结束后交换a[lo]与a[j].
- 返回j
(b) 递归调用排序lo到j-1
(c) 递归调用排序j+1到hi
3-way快速排序是对快速排序的改进,因为快速排序算法的扫描方法在有多个与a[lo]相当的元素时,仍然需要交换元素(非必要交换),因此,可以引入lt和gt2个元素,来保证lt-gt之间的元素都等于v,lt左边不大于v,gt右边不小于v.具体实现:
(a): partition分割(同时设置lt与gt)
lt = lo, gt = hi, i = lo, v = a[lo]
选择v作为partitioning元素a[lo](可与快速排序选择方法相同)
i从左往右开始扫描:
- a[i]<v: 交换a[lt]与a[i], lt++, i++
- a[i]>v: 交换a[gt]与a[i], gt--
- a[i]==v: i++
(b) 递归调用排序lo到lt-1
(c) 递归调用gt+1到hi
python实现如下(包含上次写过的希尔排序,插入排序与选择排序):
#! /usr/bin/env python
# coding: utf-8
def SelectionSort(s):
'''
Selection sort: [] from left to right,
exchange [] with the min value on its right
'''
print 'Selection Sorting Algorithm:'
print 'Original\t', ' '.join([str(x) for x in s])
for i in range(len(s)):
if s[i+1:]:
m = min(s[i+1:])
if s[i]<m:
continue
ind = i+1+s[i+1:].index(m)
s[i], s[ind] = s[ind], s[i]
print 'exch[', i+1, ']\t', ' '.join([str(x) for x in s])
print 'Sorted\t\t', ' '.join([str(x) for x in s])
return s
def InsertionSort(s):
'''
Insertion sort: [] from left to right,
exchange [] with each bigger value on its left
'''
print 'Insertion Sorting Algorithm:'
print 'Original\t', ' '.join([str(x) for x in s])
cnt = 1
for i in range(1,len(s)):
for j in range(i,0,-1):
if s[j]<s[j-1]:
s[j], s[j-1] = s[j-1], s[j]
print 'exch[', cnt, ']\t', ' '.join([str(x) for x in s])
cnt += 1
else:
break
print 'Sorted\t\t', ' '.join([str(x) for x in s])
return s
def ShellSort(s):
'''
Shell sort: perform h-sorting over the sequence,
h is an increamental sequence, 3x+1 is good
but the best is Sedgewick one: 1 5 19 41 109 209 505 929 2161 3905
which can be produced by merging 9*4^i-9*2^i+1 and 4^i-3*2^i+1
'''
print 'Shell Sorting Algorithm:'
print 'Original\t', ' '.join([str(x) for x in s])
h = 1
while h<len(s)/3:
h = 3*h+1;
while h>=1:
print 'h =', h
cnt = 1
for i in range(h,len(s)):
for j in range(i,-1,-h):
if j>=h and s[j]<s[j-h]:
s[j], s[j-h] = s[j-h], s[j]
print 'exch[', cnt, ']\t', ' '.join([str(x) for x in s])
cnt += 1
h /= 3
print 'Sorted\t\t', ' '.join([str(x) for x in s])
return s
def Merge(s1, s2):
result = []
while s1 and s2:
if s1[0]<s2[0]:
result.append(s1.pop(0))
else:
result.append(s2.pop(0))
return result+s1+s2
def MergeSort(s):
'''
Merge sort: divide and conquer
split the list into two small lists and sort them recursively until
the lists have only 1 element. Then merge them together
'''
if len(s)==1:
return s
elif len(s)==2:
return [min(s), max(s)]
else:
first = MergeSort(s[:len(s)/2])
second = MergeSort(s[len(s)/2:])
return Merge(first, second)
def MergeSortBU(s):
step = 1
while step<len(s):
for i in range(0,len(s),2*step):
s[i:i+2*step] = Merge(s[i:i+step],s[i+step:i+2*step])
step *= 2
return s
import random
def Partition(s, lo, hi):
i, j = lo, hi
while True:
while s[i]<s[lo]: # find item on left to swap
i += 1
if i==hi:
break
while s[j]>s[lo]: # find item on right to swap
j -= 1
if j==lo:
break
if i>=j: # check pointer cross
break
s[i], s[j] = s[j], s[i] # swap
s[lo], s[j] = s[j], s[lo]
print ' '.join([str(x) for x in s])
return j
def Sort(s, lo, hi):
if hi<=lo:
return
ind = Partition(s, lo, hi)
Sort(s, lo, ind-1)
Sort(s, ind+1, hi)
def QuickSort(s):
'''
Quick sort:
shuffle
partition for some j,
a[j] in place
no larger item to the left of j
no smaller entry to the right of j
sort each piece recursively
implementation:
i, j = lo, hi, repeat
- scan i from left to right when a[i] < a[lo]
- scan j from right to left when a[j] >a[lo]
- exchange a[i] with a[j]
exchange a[lo] with a[j] if i and j corss
'''
## random.shuffle(s) # can be replaced by put the median of 3 as the first
Sort(s, 0, len(s)-1)
return s
def Quick3WaySort(s):
'''
3-way quick sort: can optimise sorting with duplicate keys
items between lt and gt equal to v
no larger item to left of lt
no smaller item to right of gt
implementation:
v be the partitioning items a[lo]
scan i from left to right:
- a[i]<v: exchange a[lt] with a[i]; increase both lt and i
- a[i]>v: exchange a[gt] with a[i]; decrease gt
- a[i]==v: increase i
'''
if not s: return []
lo, hi = 0, len(s)-1
lt, gt = lo, hi
i, v = lo, s[lo]
while i<=gt:
if s[i]<v:
s[lt], s[i] = s[i], s[lt]
lt += 1
i += 1
elif s[i]>v:
s[gt], s[i] = s[i], s[gt]
gt -= 1
else:
i += 1
s[:lt-1] = Quick3WaySort(s[:lt-1])
s[gt+1:] = Quick3WaySort(s[gt+1:])
return s
def main():
a = '52 50 99 47 59 96 45 72 58 40'
s = [int(x.strip()) for x in a.strip().split(' ')]
SelectionSort(s)
print '='*20
a = '43 46 53 77 87 51 65 25 21 18'
s = [int(x.strip()) for x in a.strip().split(' ')]
InsertionSort(s)
print '='*20
a = '83 87 36 53 16 14 97 51 52 44'
s = [int(x) for x in a.split(' ')]
ShellSort(s)
print '='*20
a = '96 67 80 54 30 59 14 91 87 99 61 37'
s = [int(x.strip()) for x in a.strip().split(' ')]
print 'Merge Sorting Algorithm:'
print 'Original\t', ' '.join([str(x) for x in s])
s = MergeSort(s)
print 'Sorted\t\t', ' '.join([str(x) for x in s])
print '='*20
a = '96 67 80 54 30 59 14 91 87 99 61 37'
s = [int(x.strip()) for x in a.strip().split(' ')]
print 'Bottom-up Merge Sorting Algorithm:'
print 'Original\t', ' '.join([str(x) for x in s])
s = MergeSortBU(s)
print 'Sorted\t\t', ' '.join([str(x) for x in s])
print '='*20
a = '73 34 24 59 12 87 30 77 51 82 35 43'
s = [int(x.strip()) for x in a.strip().split(' ')]
print 'Quick Sorting Algorithm:'
print 'Original\t', ' '.join([str(x) for x in s])
s = QuickSort(s)
print 'Sorted\t\t', ' '.join([str(x) for x in s])
print '='*20
a = '58 58 15 46 24 34 58 58 28 22 '
s = [int(x.strip()) for x in a.strip().split(' ')]
print 'Quick3Way Sorting Algorithm:'
print 'Original\t', ' '.join([str(x) for x in s])
s = Quick3WaySort(s)
print 'Sorted\t\t', ' '.join([str(x) for x in s])
if __name__=='__main__':
main()
No comments :
Post a Comment