菜鸟也来学python 笔记4 - python排序算法比较

刚学python，练练手

 

Python语言:

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

可以运行，哪里有不对的地方，请大家指出来，菜鸟好提高。