python之八大排序方法

一、插入排序

#-*- coding:utf-8 -*-
”’
描述
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为o(n^2)。
是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),
而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中
”’
def insert_sort(lists):
count = len(lists)
for i in range(1, count):
key = lists[i]
j = i – 1
while j >= 0:
if lists[j] > key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return lists
lst1 = raw_input().split()
lst = [int(i) for i in lst1]
#lst = input()
insert_sort(lst)
for i in range(len(lst)):
print lst[i],

二、希尔排序

#-*- coding:utf8 -*-
”’
描述
希尔排序(shell sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
该方法因dl.shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,
每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
”’
def shell_sort(lists):
count = len(lists)
step = 2
group = count / step
while group > 0:
for i in range(group):
j = i + group
while j < count: k = j - group key = lists[j] while k >= 0:
if lists[k] > key:
lists[k + group] = lists[k]
lists[k] = key
k -= group
j += group
group /= step
return lists
lst1 = raw_input().split()
lst = [int(i) for i in lst1]
#lst = input()
shell_sort(lst)
for i in range(len(lst)):
print lst[i],

三、冒泡排序

#-*- coding:utf8 -*-
”’
描述
它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
”’
def bubble_sort(lists):
count = len(lists)
for i in range(count):
for j in range(i + 1, count):
if lists[i] > lists[j]:
lists[i], lists[j] = lists[j], lists[i]
return lists
lst1 = raw_input().split()
lst = [int(i) for i in lst1]
#lst = input()
bubble_sort(lst)
for i in range(len(lst)):
print lst[i],

四、直接选择排序

#-*- coding:utf8 -*-
”’
描述
基本思想:第1趟,在待排序记录r1 ~ r[n]中选出最小的记录,将它与r1交换;第2趟,在待排序记录r2 ~ r[n]中选出最小的记录,将它与r2交换;
以此类推,第i趟在待排序记录r[i] ~ r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
”’
def select_sort(lists):
count = len(lists)
for i in range(count):
min = i
for j in range(i + 1, count):
if lists[min] > lists[j]:
min = j
lists[min], lists[i] = lists[i], lists[min]
return lists
lst1 = raw_input().split()
lst = [int(i) for i in lst1]
#lst = input()
select_sort(lst)
for i in range(len(lst)):
print lst[i],

五、快速排序

#-*- coding:utf8 -*-
”’
描述(利用递归,效率较低,较难理解)
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,
然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
”’
def quick_sort(lists, left, right):
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right: while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
while left < right and lists[left] lists[max]: max = lchild if rchild < size and lists[rchild] > lists[max]:
max = rchild
if max != i:
lists[max], lists[i] = lists[i], lists[max]
adjust_heap(lists, max, size)
# 创建堆
def build_heap(lists, size):
for i in range(0, (size/2))[::-1]:
adjust_heap(lists, i, size)
# 堆排序
def heap_sort(lists):
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists, 0, i)
lst1 = raw_input().split()
lst = [int(i) for i in lst1]
#lst = input()
heap_sort(lst)
for i in range(len(lst)):
print lst[i],

七、归并排序

#-*- coding:utf8 -*-
”’
描述(利用递归)
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(pide and conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;
即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,
并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,
先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
”’
def merge(left, right):
#合并过程
i, j = 0, 0
result = []
while i < len(left) and j < len(right): if left[i]

Posted in 未分类

发表评论