各种排序方法,排序方法,最近找工作,很是郁闷,回
各种排序方法,排序方法,最近找工作,很是郁闷,回
最近找工作,很是郁闷,回回去面试,都先让我在角落里做一个小时题,不是排序,就是单链表,要么就是二叉树。平常不用这些,早都忘光了。现在把自己以前写的代码翻出来,开始慢慢背了。这是各种排序:
#author: Jiang Hongfei <jianghongfei@gmail.com>import randomimport timeimport loggingdef isSorted(ml): for i in range(len(ml) - 1): if ml[i] > ml[i + 1]: return False return Truedef swap(ml, m, n): t = ml[m] ml[m] = ml[n] ml[n] = tdef bubbleSort(ml): for m in range(len(ml) - 1): for n in range(len(ml) - m - 1): if ml[n] > ml[n + 1]: swap(ml, n, n + 1)def selectSort(ml): for m in range(len(ml) - 1): minIndex = m for n in range(m + 1, len(ml)): if ml[n] < ml[minIndex]: minIndex = n if minIndex != m: swap(ml, minIndex, m)def quickSort(ml, left = None, right = None): def partition(ml, left, right): counter = left for m in range(left, right): if ml[m] < ml[right]: swap(ml, counter, m) counter += 1 swap(ml, counter, right) return counter if left == None or right == None: quickSort(ml, 0, len(ml) - 1) elif left < right: p = partition(ml, left, right) quickSort(ml, left, p - 1) quickSort(ml, p + 1, right)def insertSort(ml): for n in range(1, len(ml)): temp = ml[n] index = n while index > 0 and ml[index - 1] > temp: ml[index] = ml[index - 1] index -= 1 ml[index] = tempdef ciuraShellSort(ml): '''It says this is fast, but it seems it's not as fast as it's supposed to be''' op, n = 0, len(ml) incs = [2331004, 1036002, 460445, 204643, 90952, 40423, 17965, 7985, 3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1] for t in range(18): h = incs[t] if h > n * 4 / 9: continue for i in range(h, n): temp = ml[i] j = i - h while j >= 0 and ml[j] > temp: ml[j + h] = ml[j] op += 1 j -= h ml[j + h] = temp op += 1def shellSort(seq): '''This shell sort use the nature of python''' inc = len(seq) // 2 while inc: for i, el in enumerate(seq): while i >= inc and seq[i - inc] > el: seq[i] = seq[i - inc] i -= inc seq[i] = el inc = round(inc / 2.2)def shell(data): '''This is tranlsated from java version from wiki, not using python feature, it's a little bit slower than previous one''' inc = len(data) // 2 while inc: for i in range(inc, len(data)): tmp = data[i] j = i while j >= inc and data[j - inc] > tmp: data[j] = data[j - inc] j -= inc data[j] = tmp inc = round(inc / 2.2)def mergesort(n): """Recursively merge sort a list. Returns the sorted list.""" def merge(front, back): """Merge two sorted lists together. Returns the merged list.""" result = [] while front and back: # pick the smaller one from the front and stick it on # note that list.pop(0) is a linear operation, so this gives quadratic running time... result.append(front.pop(0) if front[0]<=back[0] else back.pop(0)) # add the remaining end result.extend(front or back) return result mid = len(n) // 2 front = n[:mid] back = n[mid:] if len(front) > 1: front = mergesort(front) if len(back) > 1: back = mergesort(back)def HeapSort(A): def heapify(A): start = (len(A) - 2) // 2 while start >= 0: siftDown(A, start, len(A) - 1) start -= 1 def siftDown(A, start, end): root = start while root * 2 + 1 <= end: child = root * 2 + 1 if child + 1 <= end and A[child] < A[child + 1]: child += 1 if child <= end and A[root] < A[child]: A[root], A[child] = A[child], A[root] root = child else: return heapify(A) end = len(A) - 1 while end > 0: A[end], A[0] = A[0], A[end] siftDown(A, 0, end - 1) end -= 1if __name__ == '__main__': mt = [random.randint(1, 100) for i in range(9999)] #print(' '.join(map(str, mt))) print(isSorted(mt)) def out(visit): if visit != None: print(visit.__name__ + ':') l = mt[:] t1 = time.time() visit(l) t2 = time.time() #print(' '.join(map(str, l))) print(isSorted(l)) print((t2 - t1) * 1000.0) out(insertSort) out(bubbleSort) out(selectSort) out(quickSort) out(ciuraShellSort) out(shellSort) out(shell) out(mergesort) out(HeapSort)#该片段来自于http://byrx.net
相关内容
- python编写的一个通过多线程扫描端口的代码,python多线
- 用wxpython开发的批量在图片上生成水印文字的可视化小
- 打印日历,,python代码#-*-
- GAE/python中利用memcache代替Session实现用户登录验,gaeme
- 获得图片的Base64编码,,python代码#!/u
- python修改操作系统时间的代码,python操作系统,#-*- cod
- python 抓去指定网页以及该网页上所有链接,python指定
- Python 支持上传的SimpleHTTPServer,,SimpleHTTPSe
- Python 随机生成中文验证码,python中文验证码,python代码
- Python : appendInt, appendShort, appendStr,,python代码impo
评论关闭