首页 > 编程语言 > 详细

排序(选择排序)

时间:2017-09-24 14:12:57      阅读:56      评论:0      收藏:0      [点我收藏+]

标签:range   两种   then   pen   直接   heapsort   main   dom   左右   

选择排序是每次从序列中挑出一个最小的数字放在开始位置,依次往后即可,如何找到最小的元素可以有两种方法。

1、简单选择排序,就是直接找了,每次找到最小那个放在起始位置。

2、堆排序,在二叉树中执行,要求每个节点都比左右节点大,整个树的根节点就是最大的,然后将根节点与最后一个节点调换位置,并重新排列,这样最大值依次往后放置。

给代码。

#coding:utf-8

import random

def simpleChooseSort(numList):
lengthen = len(numList)#记录数组大小
i = 0
index = 0 #记录查询过程中的当前最大值索引
while i < lengthen - 1:
index = i
j = i + 1
while j < lengthen:
if numList[j] < numList[index]:
index = j
j += 1
if index != i:
numList[i],numList[index] = numList[index],numList[i]
i += 1

#堆排序
def heapSort(numList):
lengthen = len(numList)
start = lengthen / 2
while start >= 0:
maxHeap(numList,start,lengthen)
start -= 1
start = lengthen - 1
while start >= 2:
numList[0],numList[start] = numList[start],numList[0]
maxHeap(numList,0,start - 1)
start -= 1
if numList[0] > numList[1]: #这里比较奇怪,不知道为什么如果去掉这几句,每次排序下来总是发现根节点处发生问题。
numList[0],numList[1] = numList[1],numList[0]
if numList[0] > numList[2]:
numList[0],numList[2] = numList[2],numList[0]
if numList[1] > numList[2]:
numList[1],numList[2] = numList[2],numList[1]



#整理数组得到二叉堆
def maxHeap(numList,startIndex,lengthen):
l = 2 * startIndex + 1
r = 2 * startIndex + 2
if l < lengthen and numList[startIndex] < numList[l]:
minIndex = l
else:
minIndex = startIndex
if r < lengthen and numList[minIndex] < numList[r]:
minIndex = r
if minIndex != startIndex:
numList[startIndex],numList[minIndex] = numList[minIndex],numList[startIndex]
maxHeap(numList,minIndex,lengthen)

#测试简单选择排序
def test1():
import random
a = []
for i in range(100):
temp = random.randint(0, 100)
while True:
for x in range(len(a)):
if a[x] == temp:
temp = random.randint(0, 100)
break
else:
a.append(temp)
break
# print ‘\n‘,len(a),‘\n‘
for x in a:
print x,
simpleChooseSort(a)
print ‘\n‘
for x in a:
print x,

#测试堆排序
def test2():
import random
a = []
for i in range(100):
temp = random.randint(0, 100)
while True:
for x in range(len(a)):
if a[x] == temp:
temp = random.randint(0, 100)
break
else:
a.append(temp)
break
# print ‘\n‘,len(a), ‘\n‘
print ‘\n‘
for x in a:
print x,
heapSort(a)
print ‘\n‘
for x in a:
print x,

if __name__ == ‘__main__‘:
test1()
test2()

排序(选择排序)

标签:range   两种   then   pen   直接   heapsort   main   dom   左右   

原文:http://www.cnblogs.com/world-for-gold/p/7587047.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号