# 基于python的七种经典排序算法的详细介绍

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: liu jiang
# python 3.5
# 冒泡排序算法
class sqlist:
def init(self, lis=none):
self.r = lis
def swap(self, i, j):
“””定义一个交换元素的方法，方便后面调用。”””
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def bubble_sort_simple(self):
“””

“””
lis = self.r
length = len(self.r)
for i in range(length):
for j in range(i+1, length):
if lis[i] > lis[j]:
self.swap(i, j)
def bubble_sort(self):
“””

“””
lis = self.r
length = len(self.r)
for i in range(length):
j = length-2
while j >= i:
if lis[j] > lis[j+1]:
self.swap(j, j+1)
j -= 1
“””

“””
lis = self.r
length = len(self.r)
flag = true
i = 0
while i < length and flag: flag = false j = length - 2 while j >= i:
if lis[j] > lis[j + 1]:
self.swap(j, j + 1)
flag = true
j -= 1
i += 1
def str(self):
ret = “”
for i in self.r:
ret += ” %s” % i
return ret
if name == ‘main’:
sqlist = sqlist([4,1,7,3,8,5,9,2,6])
# sqlist.bubble_sort_simple()
# sqlist.bubble_sort()
print(sqlist)

lis[j+1] = lis[j]
j -= 1
lis[j+1] = temp
def str(self):
ret = “”
for i in self.r:
ret += ” %s” % i
return ret
if name == ‘main’:
sqlist = sqlist([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
sqlist.insert_sort()
print(sqlist)

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: liu jiang
# python 3.5
# 希尔排序
class sqlist:
def init(self, lis=none):
self.r = lis
def shell_sort(self):
“””希尔排序”””
lis = self.r
length = len(lis)
increment = len(lis)
while increment > 1:
increment = int(increment/3)+1
for i in range(increment+1, length):
if lis[i] < lis[i - increment]: temp = lis[i] j = i - increment while j >= 0 and temp < lis[j]: lis[j+increment] = lis[j] j -= increment lis[j+increment] = temp def str(self): ret = "" for i in self.r: ret += " %s" % i return ret if name == 'main': sqlist = sqlist([4, 1, 7, 3, 8, 5, 9, 2, 6, 0,123,22]) sqlist.shell_sort() print(sqlist)

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: liu jiang
# python 3.5
# 堆排序
class sqlist:
def init(self, lis=none):
self.r = lis
def swap(self, i, j):
“””定义一个交换元素的方法，方便后面调用。”””
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def heap_sort(self):
length = len(self.r)
i = int(length/2)
# 将原始序列构造成一个大顶堆
# 遍历从中间开始，到0结束，其实这些是堆的分支节点。
while i >= 0:
i -= 1
# 逆序遍历整个序列，不断取出根节点的值，完成实际的排序。
j = length-1
while j > 0:
# 将当前根节点，也就是列表最开头，下标为0的值，交换到最后面j处
self.swap(0, j)
# 将发生变化的序列重新构造成大顶堆
j -= 1
def heap_adjust(self, s, m):
“””核心的大顶堆构造方法，维持序列的堆结构。”””
lis = self.r
temp = lis[s]
i = 2*s
while i = lis[i]:
break
lis[s] = lis[i]
s = i
i *= 2
lis[s] = temp
def str(self):
ret = “”
for i in self.r:
ret += ” %s” % i
return ret
if name == ‘main’:
sqlist = sqlist([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
sqlist.heap_sort()
print(sqlist)

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# author: liu jiang
# python 3.5
# 归并排序
class sqlist:
def init(self, lis=none):
self.r = lis
def swap(self, i, j):
“””定义一个交换元素的方法，方便后面调用。”””
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def merge_sort(self):
self.msort(self.r, self.r, 0, len(self.r)-1)
def msort(self, list_sr, list_tr, s, t):
temp = [none for i in range(0, len(list_sr))]
if s == t:
list_tr[s] = list_sr[s]
else:
m = int((s+t)/2)
self.msort(list_sr, temp, s, m)
self.msort(list_sr, temp, m+1, t)
self.merge(temp, list_tr, s, m, t)
def merge(self, list_sr, list_tr, i, m, n):
j = m+1
k = i
while i lis[high]:
self.swap(low, high)
if lis[m] > lis[high]:
self.swap(high, m)
if lis[m] > lis[low]:
self.swap(m, low)
pivot_key = lis[low]
# temp暂存pivot_key的值
temp = pivot_key
while low < high: while low < high and lis[high] >= pivot_key:
high -= 1
# 直接替换，而不交换了
lis[low] = lis[high]
while low < high and lis[low]

Posted in 未分类