Fork me on GitHub

python实现八大排序

世界这么大,该往哪走?

python实现八大排序

直接插入排序

算法基本思想:

  • 直接插入排序(Straight Insertion Sort)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def insert_sort(iterable, reverse=False):
'''
对可迭代对象进行插入排序
args:
iterable: 可迭代对象
reversed: False默认从小到大排序。True从大到小
'''
for i, _ in enumerate(iterable):
for j in range(i, 0, -1):
if iterable[j] < iterable[j - 1]:
iterable[j], iterable[j - 1] = iterable[j - 1], iterable[j]
else:
break
if reverse:
iterable.reverse()


if __name__ == '__main__':
lst1 = [3, 10, 4, 8, 1, 20, 100]
lst2 = [1]
lst3 = []
lst4 = lst1[::]
insert_sort(lst1)
print(lst1)

insert_sort(lst2)
print(lst2)

insert_sort(lst3)
print(lst3)

insert_sort(lst4, reverse=True)
print(lst4)

希尔排序

算法基本思想:

  •  希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
ddef shell_insert(iterable, start, end, step):
for i in range(start, end, step):
for j in range(i, start, -step):
if iterable[j] < iterable[j - step]:
iterable[j], iterable[j -
step] = iterable[j - step], iterable[j]
else:
break


def shell_sort(iterable, reverse=False):
'''
对可迭代对象进行希尔排序
args:
iterable: 可迭代对象
reversed: False默认从小到大排序。True从大到小
'''
length = len(iterable)
gap = length // 2
while gap != 0:
for start in range(gap + 1):
shell_insert(iterable, start, length, gap)
gap = gap // 2

if reverse:
iterable.reverse()


if __name__ == '__main__':
lst1 = [3, 10, 4, 8, 1, 20, 100]
lst2 = [1]
lst3 = []
lst4 = lst1[::]
shell_sort(lst1)
print(lst1)

shell_sort(lst2)
print(lst2)

shell_sort(lst3)
print(lst3)

shell_sort(lst4, reverse=True)
print(lst4)

直接选择排序

算法基本思想:

  • 与直接插入排序一样,分为有序区和无序区,所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区,而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def select_sort(iterable, reverse=False):
'''
对可迭代对象进行直接选择排序
args:
iterable: 可迭代对象
reversed: False默认从小到大排序。True从大到小
'''
length = len(iterable)
for i in range(length):
min_x = iterable[i]
flag_x = i
for j in range(i + 1, length):
if iterable[j] < min_x:
min_x = iterable[j]
flag_x = j

iterable[i], iterable[flag_x] = iterable[flag_x], iterable[i]
print(iterable)

if reverse:
iterable.reverse()


if __name__ == '__main__':
lst1 = [3, 10, 4, 8, 1, 20, 100]
lst2 = [1]
lst3 = []
lst4 = lst1[::]
select_sort(lst1)
print(lst1)

select_sort(lst2)
print(lst2)

select_sort(lst3)
print(lst3)

select_sort(lst4, reverse=True)
print(lst4)

堆排序

算法基本思想(大顶堆为例):

  • 先将初始排列关键字序列(R1,R2…,Rn-1,Rn)构成大顶堆,此堆为初始的无序区.(这里是从最后一个非叶结点向前进行赛选)
  • 将堆顶元素R1与最后一个元素Rn交换,此时得到新的无序区(R1,R2…,Rn-1)和新的有序区(Rn),并且Rn大于无序区所有数,此后还有n-1个数;
  • 由于交换后新的堆顶R1可能违反堆的性质,因此需要对当前无序区(R1,R2…,Rn-1)调整为新堆(将堆顶元素向下调整使其保持大顶堆的性质,输出堆顶元素),此后还剩余n-2个数;
  • 重读以上算法,直到堆中仅剩一个元素为止.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class HeapSort(object):
'''
堆排序

set() 方法设置可迭代对象以及排列顺序
_sift_down() 进行向下调整堆
_create_heap() 创建初始堆
heap_sort() 进行堆排序
'''

def set(self, iterable, reverse=False):
self.iterable = iterable
self.reverse = reverse
self.length = len(iterable)

self.iterable.insert(0, None)

def _sift_down(self, index):
left_child, right_child = index * 2, index * 2 + 1

if left_child > self.cur_len:
return

max_child = left_child
if (right_child <= self.cur_len) and (self.iterable[left_child] < self.iterable[right_child]):
max_child = right_child

if self.iterable[index] < self.iterable[max_child]:
self.iterable[index], self.iterable[max_child] = self.iterable[max_child], self.iterable[index]
self._sift_down(max_child)

def _create_heap(self):
for i in range(self.length // 2, 0, -1):
self._sift_down(i)

def heap_sort(self):
# cur_len表示还没有顺序区域的长度
self.cur_len = self.length
self._create_heap()
while self.cur_len:
# print(self.iterable)
self.iterable[1], self.iterable[self.cur_len] = self.iterable[self.cur_len], self.iterable[1]
self.cur_len -= 1
self._sift_down(1)

self.iterable.pop(0)
if self.reverse:
self.iterable.reverse()


if __name__ == '__main__':
lst1 = [3, 10, 4, 8, 1, 20, 100]
lst2 = [1]
lst3 = []
lst4 = lst1[::]

heap_sort = HeapSort()

heap_sort.set(lst1)
heap_sort.heap_sort()
print(lst1)

heap_sort.set(lst2)
heap_sort.heap_sort()
print(lst2)

heap_sort.set(lst3)
heap_sort.heap_sort()
print(lst3)

heap_sort.set(lst4, reverse=True)
heap_sort.heap_sort()
print(lst4)

冒泡排序

算法基本思想:

  • 从无序序列头部开始,进行两两比较,根据大小交换位置,直到最后将最大(小)的数据元素交换到了无序队列的队尾,从而成为有序序列的一部分;下一次继续这个过程,直到所有数据元素都排好序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def bubble_sort(iterable, reverse=False):
'''
冒泡排序
args:
iterable: 可迭代对象
reversed: False默认从小到大排序。True从大到小
'''
length = len(iterable)
for i in range(length, 0, -1):
# flag标记本次是否交换了数据,如果没交换数据就不用继续排了
flag = 0
for j in range(i - 1):
if iterable[j] > iterable[j + 1]:
iterable[j], iterable[j + 1] = iterable[j + 1], iterable[j]
flag = 1

if not flag:
break

if reverse:
iterable.reverse()


if __name__ == '__main__':
lst1 = [3, 10, 4, 8, 1, 20, 100]
lst2 = [1]
lst3 = []
lst4 = lst1[::]
bubble_sort(lst1)
print(lst1)

bubble_sort(lst2)
print(lst2)

bubble_sort(lst3)
print(lst3)

bubble_sort(lst4, reverse=True)
print(lst4)

快速排序

算法基本思想(分治思想):

  • 在数据集之中,找一个基准点(以下代码以最left为基准点)
  • 以基准点为中心将数据分为左边比基准点小,右边大于等于基准点
  • 在递归左右两边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class QuickSort(object):
'''
快速排序

set() 设置可迭代对象及排序方式(大->小 or 小->大)
place_it() 每次选择最左边的作为参考,这个方法调用后左边的元素都小于它,右边的元素大于等于它,返回参考元素最终的位置
sort() 递归左右两边
'''

def set(self, iterable, reverse=False):
self.iterable = iterable
self.reverse = reverse

def place_it(self, left, right):
chose_it = left
while left < right:
while left < right:
if self.iterable[right] < self.iterable[chose_it]:
break
right -= 1
while left < right:
if self.iterable[left] > self.iterable[chose_it]:
break
left += 1
self.iterable[left], self.iterable[right] = self.iterable[right], self.iterable[left]
self.iterable[left], self.iterable[chose_it] = self.iterable[chose_it], self.iterable[left]
return left

def sort(self, left, right):
if left >= right:
return
index = self.place_it(left, right)
# print(self.iterable)
self.sort(left, index - 1)
self.sort(index + 1, right)

def quick_sort(self):
self.sort(0, len(self.iterable) - 1)
if self.reverse:
self.iterable.reverse()


if __name__ == '__main__':
lst1 = [3, 10, 4, 8, 1, 20, 100, 8, 101, 0, 35, 9, 10, 100, 20, 2, 3]
lst2 = [1]
lst3 = []
lst4 = lst1[::]
quick_sort = QuickSort()

quick_sort.set(lst1)
quick_sort.quick_sort()
print(lst1)

quick_sort.set(lst2)
quick_sort.quick_sort()
print(lst2)

quick_sort.set(lst3)
quick_sort.quick_sort()
print(lst3)

quick_sort.set(lst4, reverse=True)
quick_sort.quick_sort()
print(lst4)

归并排序

算法基本思想(分治思想):

  • 归并排序首先将待排序数组或线性表分为两个有序数组或线性表
  • 将两个有序数组或线性表合并成一个有序数组或线性表.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class MergeSort(object):
'''
归并排序

set() 设置可迭代对象及排序方式(大->小 or 小->大)
merge() 将有序的两边进行合并
sort() 递归左右两边
'''

def set(self, iterable, reverse=False):
self.iterable = iterable
self.reverse = reverse

def merge(self, left, mid, right):
'''
合并左右两边
'''
left_index = left
right_index = mid + 1
left_end = mid
right_end = right

tmp = []
while left_index <= left_end and right_index <= right_end:
if self.iterable[left_index] <= self.iterable[right_index]:
tmp.append(self.iterable[left_index])
left_index += 1
else:
tmp.append(self.iterable[right_index])
right_index += 1
while left_index <= left_end:
tmp.append(self.iterable[left_index])
left_index += 1

while right_index <= right_end:
tmp.append(self.iterable[right_index])
right_index += 1

tmp_index = 0
for i in range(left, right + 1):
self.iterable[i] = tmp[tmp_index]
tmp_index += 1

def sort(self, left, right):
if left >= right:
return
mid = (left + right) // 2
self.sort(left, mid)
self.sort(mid + 1, right)

self.merge(left, mid, right)

def merge_sort(self):
self.sort(0, len(self.iterable) - 1)
if self.reverse:
self.iterable.reverse()


if __name__ == '__main__':
lst1 = [3, 10, 4, 8, 1, 20, 100, 8, 101, 0, 35, 9, 10, 100, 20, 2, 3]
lst2 = [1]
lst3 = []
lst4 = lst1[::]
merge_sort = MergeSort()

merge_sort.set(lst1)
merge_sort.merge_sort()
print(lst1)

merge_sort.set(lst2)
merge_sort.merge_sort()
print(lst2)

merge_sort.set(lst3)
merge_sort.merge_sort()
print(lst3)

merge_sort.set(lst4, reverse=True)
merge_sort.merge_sort()
print(lst4)

基数排序

后面再补…

-------------本文结束感谢您的阅读-------------

本文标题:python实现八大排序

文章作者:Longofo

发布时间:2018年07月09日 - 19:07

最后更新:2018年07月11日 - 11:07

原始链接:http://longofo.cc/python实现八大排序.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我吃包辣条也好啊!!!
分享到: