菜鸟学python - 排序

开始学习Python了，练手一下吧。一些很基本的东西，代码写得很幼稚，但也算是一点点的进步吧。

代码在python 2.7下测试通过，使用的编辑器为Spyder。

我感觉Spyder挺好的，本来想用NetBeans7.0.1，但安装好后总是在logo画面秒退。唉，悲剧了。

不说了，上代码 ~

顺便用Python的matplot把随机生成的2000个正整数给画出来了。

 

 这不是数学中严格意义上的随机分布。

001 # -*- coding: utf-8 -*-
002 """
003 Created on Wed Sep 28 16:58:29 2011
004 
005 @author: Guo
006 """
007 import time 
008 import random 
009 import numpy as np
010 import matplotlib
011 import matplotlib.pyplot as plt
012 
013 randomList = []
014 maxValue = 2000
015 numberRandom = 2000
016 
017 """
018 直接插入排序
019 """
020 def insert_Sort(data):
021     for i in range(1, len(data)):
022         temp = data[i]    #data[i] is to insert
023         j = i - 1
024         while j >= 0 and temp < data[j]:
025             data[j + 1] = data[j]
026             j = j - 1
027         if j <> i - 1:
028             data[j + 1] = temp     #insert temp
029     sortedData = data
030     return sortedData
031     
032 """
033 随机数构造函数
034 """
035 def createRandomList():
036     for i in range(numberRandom):
037         randomList.append(random.randint(1,maxValue));
038 
039 """
040 冒泡排序
041 """  
042 def bubblesort(data):
043     sortedData = []
044     for i in range(len(data) - 1, 1, -1):
045         for j in range(0, i):
046             if data[j] > data[j + 1]:
047                 data[j], data[j + 1] = data[j + 1], data[j]
048     sortedData = data
049     return sortedData    
050 
051 """
052 希尔排序
053 """   
054 def shell_Sort(data, n = None):
055     if n == None:
056         n = len(data) / 2
057         if n % 2 == 0:
058             n = n + 1
059     for i in range(0, n):
060         newdata = data[i:len(data):n]
061         insert_sort(newdata)
062         data[i:len(data):n] = newdata
063     if n <> 1:
064         d = n / 2
065         if d % 2 == 0:
066             d = d + 1
067         shell_Sort(data, d)
068         
069 """
070 快速排序
071 """
072 def quickSort(data, low = 0, high = None):
073     if high == None:
074         high = len(data) - 1
075     if low < high:
076         s, i, j = data[low], low, high
077         while i < j:
078             while i < j and data[j] >= s:
079                 j = j - 1
080             if i < j:
081                 data[i] = data[j]
082                 i = i + 1
083             while i < j and data[i] <= s:
084                 i = i + 1
085             if i < j:
086                 data[j] = data[i]
087                 j = j - 1
088         data[i] = s
089         quickSort(data, low, i - 1)
090         quickSort(data, i + 1, high)
091 
092 """
093 堆排序
094 """
095 def heap_Adjust(data, s, m):
096     if 2 * s > m:
097         return
098     temp = s - 1
099     if data[2*s - 1] > data[temp]:
100         temp = 2 * s - 1
101     if 2 * s <= m - 1 and data[2*s] > data[temp]:
102         temp = 2 * s
103     if temp <> s - 1:
104         data[s - 1], data[temp] = data[temp], data[s - 1]
105         heap_Adjust(data, temp + 1, m)
106 def heap_sort(data):
107     m = len(data) / 2
108     for i in range(m, 0, -1):
109         heap_Adjust(data, i, len(data))
110     data[0], data[-1] = data[-1], data[0]
111     for n in range(len(data) - 1, 1, -1):
112         heap_Adjust(data, 1, n)
113         data[0], data[n - 1] = data[n - 1], data[0]
114 
115 """---------------------------以上是函数定义-----------------------------------"""
116 
117 """     
118 显示随机数
119 """     
120 createRandomList()
121 print "The random numbers are:"
122 print randomList 
123   
124 """
125 显示冒泡排序所需时间
126 """ 
127 starttime = time.clock()    
128 createRandomList()
129 bubblesort(randomList)
130 print "After the bubblesot, the sequence numbers are:"
131 print bubblesort(randomList)
132 endtime = time.clock() 
133 print "The bubblesort time cost is:", (endtime-starttime)
134 
135 """  
136 显示直接插入排序所需时间
137 """
138 starttime = time.clock()  
139 createRandomList()
140 insert_Sort(randomList)
141 endtime = time.clock() 
142 print "The insert_Sort time cost is :", (endtime-starttime)
143 
144 """  
145 显示快速排序所需时间
146 """
147 starttime = time.clock()  
148 createRandomList()
149 quickSort(randomList)
150 endtime = time.clock() 
151 print "The quickSort time cost is :", (endtime-starttime)
152 
153 """  
154 显示堆排序所需时间
155 """
156 starttime = time.clock()  
157 createRandomList()
158 heap_Adjust(randomList)
159 endtime = time.clock() 
160 print "The heap_Adjust cost is :", (endtime-starttime)