目录
一. 泡沫排序（bubble sort）
二. 鸡尾酒排序（cocktail sort）
三. 选择排序（selection sort）
四. 插入排序（insertion sort）
五. 堆积树排序（heap sort）
六. 快速排序（quick sort）
七. 合并排序（merge sort）
一. 泡沫排序（bubble sort）
在排序中最著名的也是最简单的算法就是泡沫排序（bubble sort），也被称为冒泡排序或气泡排序，这个方法的基本工作原理是将相邻的数字做比较，如果前一个数字大于后一个数字，将彼此交换，这样经过一个循环后最大的数字会经由交换出现在最右边，数字移动过程中很像泡泡的移动，所以称为泡沫排序；
1.1 代码如下：
# 泡沫排序(bubble sort)-------------------------------------------------------------
def bubble_sort(nlist):
length = len(nlist)
for i in range(length-1):
print('第 '+str(i+1)+' 次循环')
for j in range(length-1-i):
if nlist[j] > nlist[j+1]:
nlist[j], nlist[j+1] = nlist[j+1], nlist[j]
print('第 '+str(i+1)+' 次循环'+'第 '+str(j+1)+' 次内层排序:', nlist)
print('\n')
return nlist
data = [42,62,4,26,98,6,1,27]
print('原始列表：', data)
print('排序后的列表：', bubble_sort(data))1.2 代码讲解
下面跟大家一起走一遍排序的过程（黑色代表比较不换位，红色代表比较后换位）：
原始列表： [42, 62, 4, 26, 98, 6, 1, 27]
- 第 1 次循环
第 1 次循环第 1 次内层排序: [42, 62, 4, 26, 98, 6, 1, 27]
第 1 次循环第 2 次内层排序: [42, 4, 62, 26, 98, 6, 1, 27]
第 1 次循环第 3 次内层排序: [42, 4, 26, 62, 98, 6, 1, 27]
第 1 次循环第 4 次内层排序: [42, 4, 26, 62, 98, 6, 1, 27]
第 1 次循环第 5 次内层排序: [42, 4, 26, 62, 6, 98, 1, 27]
第 1 次循环第 6 次内层排序: [42, 4, 26, 62, 6, 1, 98, 27]
第 1 次循环第 7 次内层排序: [42, 4, 26, 62, 6, 1, 27, 98]
- 第 2 次循环
第 2 次循环第 1 次内层排序: [4, 42, 26, 62, 6, 1, 27, 98]
第 2 次循环第 2 次内层排序: [4, 26, 42, 62, 6, 1, 27, 98]
第 2 次循环第 3 次内层排序: [4, 26, 42, 62, 6, 1, 27, 98]
第 2 次循环第 4 次内层排序: [4, 26, 42, 6, 62, 1, 27, 98]
第 2 次循环第 5 次内层排序: [4, 26, 42, 6, 1, 62, 27, 98]
第 2 次循环第 6 次内层排序: [4, 26, 42, 6, 1, 27, 62, 98]
- 第 3 次循环
第 3 次循环第 1 次内层排序: [4, 26, 42, 6, 1, 27, 62, 98]
第 3 次循环第 2 次内层排序: [4, 26, 42, 6, 1, 27, 62, 98]
第 3 次循环第 3 次内层排序: [4, 26, 6, 42, 1, 27, 62, 98]
第 3 次循环第 4 次内层排序: [4, 26, 6, 1, 42, 27, 62, 98]
第 3 次循环第 5 次内层排序: [4, 26, 6, 1, 27, 42, 62, 98]
- 第 4 次循环
第 4 次循环第 1 次内层排序: [4, 26, 6, 1, 27, 42, 62, 98]
第 4 次循环第 2 次内层排序: [4, 6, 26, 1, 27, 42, 62, 98]
第 4 次循环第 3 次内层排序: [4, 6, 1, 26, 27, 42, 62, 98]
第 4 次循环第 4 次内层排序: [4, 6, 1, 26, 27, 42, 62, 98]
- 第 5 次循环
第 5 次循环第 1 次内层排序: [4, 6, 1, 26, 27, 42, 62, 98]
第 5 次循环第 2 次内层排序: [4, 1, 6, 26, 27, 42, 62, 98]
第 5 次循环第 3 次内层排序: [4, 1, 6, 26, 27, 42, 62, 98]
- 第 6 次循环
第 6 次循环第 1 次内层排序: [1, 4, 6, 26, 27, 42, 62, 98]
第 6 次循环第 2 次内层排序: [1, 4, 6, 26, 27, 42, 62, 98]
- 第 7 次循环
第 7 次循环第 1 次内层排序: [1, 4, 6, 26, 27, 42, 62, 98]
1.3 算法分析
泡沫排序的第一次循环的比较次数是n-1次，第二次循环的比较次数是n-2次，到n-1次循环的时候是1次，所以比较总次数计算方式为：(n-1)+(n-2)+···+1
整体所需时间（时间复杂度）是O()。
二. 鸡尾酒排序（cocktail sort）
鸡尾酒排序（cocktail sort）又称双向冒泡排序，泡沫排序算法(冒泡排序)的概念是每次皆从左到右比较，每次循环比较n-1次，须执行n-1个循环。而鸡尾酒排序法是泡沫排序法的改良，会先从左到右比较，经过一个循环最右边可以得到最大值，同时此值将在最右边的索引位置，然后从次右边的索引从右到左比较，经过一个循环可以得到尚未排序的最小值，此值将在最左索引。然后接着再从下一个尚未排序的索引值往右比较，如此循环，当有一个循环没有更换任何值的位置是，就代表排序完成。
2.1 代码如下：
# 鸡尾酒排序(cocktail sort)-------------------------------------------------------------
def cocktail_sort(nlist):
n = len(nlist)
is_sorted = True
start = 0
end = n-1
time = 1
while is_sorted:
is_sorted = False
for i in range(start, end):
if nlist[i] > nlist[i+1]:
nlist[i], nlist[i+1] = nlist[i+1], nlist[i]
is_sorted = True
print('第 '+str(time)+' 次往右排序'+'第 '+str(i+1-start)+' 次内层排序:', nlist)
if not is_sorted:
break
print('\n')
end -= 1
for i in range(end-1, start-1, -1):
if nlist[i] > nlist[i+1]:
nlist[i], nlist[i+1] = nlist[i+1], nlist[i]
is_sorted = True
print('第 '+str(time)+' 次往左排序'+'第 '+str(end-i)+' 次内层排序:', nlist)
start += 1
time += 1
print('\n')
return nlist
data = [42,62,4,26,98,6,1,27]
print('原始列表：', data)
print('排序后的列表：', cocktail_sort(data))2.2 代码讲解
下面跟大家一起走一遍排序的过程（黑色代表比较不换位，红色代表比较后换位）：
原始列表： [42, 62, 4, 26, 98, 6, 1, 27]
- 第 1 次往右排序
第 1 次往右排序第 1 次内层排序: [42, 62, 4, 26, 98, 6, 1, 27]
第 1 次往右排序第 2 次内层排序: [42, 4, 62, 26, 98, 6, 1, 27]
第 1 次往右排序第 3 次内层排序: [42, 4, 26, 62, 98, 6, 1, 27]
第 1 次往右排序第 4 次内层排序: [42, 4, 26, 62, 98, 6, 1, 27]
第 1 次往右排序第 5 次内层排序: [42, 4, 26, 62, 6, 98, 1, 27]
第 1 次往右排序第 6 次内层排序: [42, 4, 26, 62, 6, 1, 98, 27]
第 1 次往右排序第 7 次内层排序: [42, 4, 26, 62, 6, 1, 27, 98]
- 第 1 次往左排序
第 1 次往左排序第 1 次内层排序: [42, 4, 26, 62, 6, 1, 27, 98]
第 1 次往左排序第 2 次内层排序: [42, 4, 26, 62, 1, 6, 27, 98]
第 1 次往左排序第 3 次内层排序: [42, 4, 26, 1, 62, 6, 27, 98]
第 1 次往左排序第 4 次内层排序: [42, 4, 1, 26, 62, 6, 27, 98]
第 1 次往左排序第 5 次内层排序: [42, 1, 4, 26, 62, 6, 27, 98]
第 1 次往左排序第 6 次内层排序: [1, 42, 4, 26, 62, 6, 27, 98]
- 第 2 次往右排序
第 2 次往右排序第 1 次内层排序: [1, 4, 42, 26, 62, 6, 27, 98]
第 2 次往右排序第 2 次内层排序: [1, 4, 26, 42, 62, 6, 27, 98]
第 2 次往右排序第 3 次内层排序: [1, 4, 26, 42, 62, 6, 27, 98]
第 2 次往右排序第 4 次内层排序: [1, 4, 26, 42, 6, 62, 27, 98]
第 2 次往右排序第 5 次内层排序: [1, 4, 26, 42, 6, 27, 62, 98]
- 第 2 次往左排序
第 2 次往左排序第 1 次内层排序: [1, 4, 26, 42, 6, 27, 62, 98]
第 2 次往左排序第 2 次内层排序: [1, 4, 26, 6, 42, 27, 62, 98]
第 2 次往左排序第 3 次内层排序: [1, 4, 6, 26, 42, 27, 62, 98]
第 2 次往左排序第 4 次内层排序: [1, 4, 6, 26, 42, 27, 62, 98]
- 第 3 次往右排序
第 3 次往右排序第 1 次内层排序: [1, 4, 6, 26, 42, 27, 62, 98]
第 3 次往右排序第 2 次内层排序: [1, 4, 6, 26, 42, 27, 62, 98]
第 3 次往右排序第 3 次内层排序: [1, 4, 6, 26, 27, 42, 62, 98]
- 第 3 次往左排序
第 3 次往左排序第 1 次内层排序: [1, 4, 6, 26, 27, 42, 62, 98]
第 3 次往左排序第 2 次内层排序: [1, 4, 6, 26, 27, 42, 62, 98]
- 第 4 次往右排序
第 4 次往右排序第 1 次内层排序: [1, 4, 6, 26, 27, 42, 62, 98]
2.3 算法分析
到最后的循环中如果没有数据需要更新，代表排序完成，相较于泡沫排序如果循环没有更改任何值，可以省略循环。如果序列数据大都排好，时间复杂度可以使O(n)，不过平均是O()。
三. 选择排序（selection sort）
所谓选择排序（selection sort）工作原理是从为排序的列表的序列中找最小数字，然后将此最小数字与最小索引位置的数字对调。然后从剩余的未排序数字汇总继续找寻最小数字，再将次最小数字与未排序的最小索引位置的数字对调。以此类推，直到所有数字完成从小到大排序。
这个排序法在找寻最小数字时，是使用线性搜索。由于是线性搜寻，第1次循环执行是需要比较n-1次，第2次循环是比较n-2ci，其他依次类推，整个完成需要执行n-1次循环。
3.1 代码如下：
# 选择排序(selection sort)-------------------------------------------------------------
def selection_sort(nlist):
for i in range(len(nlist)-1):
print('第', i+1, '次循环前列表：', nlist)
index = i
for j in range(i+1, len(nlist)):
if nlist[index] > nlist[j]:
index = j
if i == index:
pass
else:
nlist[index], nlist[i] = nlist[i], nlist[index]
print('第', i+1, '次循环后列表：', nlist)
print('\n')
return nlist
data = [42,62,4,26,98,6,1,27]
print('原始列表：', data)
print('排序后的列表：', selection_sort(data))3.2 代码讲解
下面跟大家一起走一遍排序的过程（黑色代表已经排列好的序列，红色代表本次循环对调的数）：
原始列表： [42, 62, 4, 26, 98, 6, 1, 27]
- 第 1 次循环
第 1 次循环前列表： [42, 62, 4, 26, 98, 6, 1, 27]
第 1 次循环后列表： [1, 62, 4, 26, 98, 6, 42, 27]
- 第 2 次循环
第 2 次循环前列表： [1, 62, 4, 26, 98, 6, 42, 27]
第 2 次循环后列表： [1, 4, 62, 26, 98, 6, 42, 27]
- 第 3 次循环
第 3 次循环前列表： [1, 4, 62, 26, 98, 6, 42, 27]
第 3 次循环后列表： [1, 4, 6, 26, 98, 62, 42, 27]
- 第 4 次循环
第 4 次循环前列表： [1, 4, 6, 26, 98, 62, 42, 27]
第 4 次循环后列表： [1, 4, 6, 26, 98, 62, 42, 27]
- 第 5 次循环
第 5 次循环前列表： [1, 4, 6, 26, 98, 62, 42, 27]
第 5 次循环后列表： [1, 4, 6, 26, 27, 62, 42, 98]
- 第 6 次循环
第 6 次循环前列表： [1, 4, 6, 26, 27, 62, 42, 98]
第 6 次循环后列表： [1, 4, 6, 26, 27, 42, 62, 98]
- 第 7 次循环
第 7 次循环前列表： [1, 4, 6, 26, 27, 42, 62, 98]
第 7 次循环后列表： [1, 4, 6, 26, 27, 42, 62, 98]
3.3 算法分析
选择排序第一次循环的线性搜寻最小值是比较n-1次，第二次循环是n-2次，到第n-1次循环的时候是1次，所以比较总次数与泡沫排序相同，计算方式为：(n-1)+(n-2)+···+1
上述执行是每个循环将最小值与未排序的最小索引最多对调一次，整体所需时间（时间复杂度）是 O()。
四. 插入排序（insertion sort）
这是一个直观的算法，从序列左边往右边排序，先讲左边的数字排序完成，再取右边未排序的数字，在已排序的序列中由右向左找对应的位置插入。
4.1 代码如下：
def insertion_sort(nlist):
n = len(nlist)
if n == 1:
print('第', n, '次循环排序：', nlist)
return nlist
print('第1次循环排序：', nlist)
for i in range(1,n):
for j in range(i,0,-1):
if nlist[j] < nlist[j-1]:
nlist[j], nlist[j-1] = nlist[j-1], nlist[j]
else:
break
print('第', i+1, '次循环排序：', nlist)
return nlist
data = [42,62,4,26,98,6,1,27]
print('原始列表：', data)
print('排序后的列表：', insertion_sort(data))4.2 代码讲解
下面跟大家一起走一遍排序的过程（黑色代表已经排列好的序列，红色代表本次循环插入的数）：
原始列表： [42, 62, 4, 26, 98, 6, 1, 27]
- 第1次循环
第1次循环排序： [42, 62, 4, 26, 98, 6, 1, 27]
- 第 2 次循环
第 2 次循环排序： [42, 62, 4, 26, 98, 6, 1, 27]
- 第 3 次循环
第 3 次循环排序： [4, 42, 62, 26, 98, 6, 1, 27]
- 第 4 次循环
第 4 次循环排序： [4, 26, 42, 62, 98, 6, 1, 27]
- 第 5 次循环
第 5 次循环排序： [4, 26, 42, 62, 98, 6, 1, 27]
- 第 6 次循环
第 6 次循环排序： [4, 6, 26, 42, 62, 98, 1, 27]
- 第 7 次循环
第 7 次循环排序： [1, 4, 6, 26, 42, 62, 98, 27]
- 第 8 次循环
第 8 次循环排序： [1, 4, 6, 26, 27, 42, 62, 98]
4.3 算法分析
插入排序的原则是将去取出的值与索引左边的值作比较，如果左边的值比较小就不必对调，此循环就算结束。
这种循环最不好的情况是第2次循环比较1次、第三次循环比较2次、······、第n次循环比较n-1次，所需运行时间（时间复杂度）与泡沫排序及选择排序相同，为 O()。
五. 堆积树排序（heap sort）
堆排序(Heap sort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。
5.1 代码如下：
class Heaptree():
def __init__(self):
self.heap = []
self.size = 0
def data_down(self, i):
while (i*2+2) <= self.size:
mi = self.get_min_index(i)
if self.heap[i] > self.heap[mi]:
self.heap[i], self.heap[mi] = self.heap[mi], self.heap[i]
i = mi
def get_min_index(self, i):
if i*2+2 >=self.size:
return i*2+1
else:
if self.heap[i*2+1] < self.heap[i*2+2]:
return i*2+1
else:
return i*2+2
def build_heap(self, mylist):
i = (len(mylist)//2)-1
self.size = len(mylist)
self.heap = mylist
while(i>=0):
self.data_down(i)
i = i-1
def get_min(self):
min_ret = self.heap[0]
self.size -= 1
self.heap[0] = self.heap[self.size]
self.heap.pop()
self.data_down(0)
return min_ret
data = [42,62,4,26,98,6,1,27]
print('原始列表：', data)
obj = Heaptree()
obj.build_heap(data)
print('形成堆积树后的列表：',obj.heap)
sort_h = []
for i in range(len(data)):
sort_h.append(obj.get_min())
print('第', i+1, '次取出堆积树最小值后的列表：', sort_h)5.2 代码讲解
原始列表： [42, 62, 4, 26, 98, 6, 1, 27]
形成堆积树后的列表： [1, 26, 4, 27, 98, 6, 42, 62]
- 第 1 次取出堆积树最小值后的列表： [1]
- 第 2 次取出堆积树最小值后的列表： [1, 4]
- 第 3 次取出堆积树最小值后的列表： [1, 4, 6]
- 第 4 次取出堆积树最小值后的列表： [1, 4, 6, 26]
- 第 5 次取出堆积树最小值后的列表： [1, 4, 6, 26, 27]
- 第 6 次取出堆积树最小值后的列表： [1, 4, 6, 26, 27, 42]
- 第 7 次取出堆积树最小值后的列表： [1, 4, 6, 26, 27, 42, 62]
- 第 8 次取出堆积树最小值后的列表： [1, 4, 6, 26, 27, 42, 62, 98]
5.3 算法分析
插入数据到堆积树和去除最小堆积树的值，时间复杂度都是O()。其实我们可以使用不断取出最小堆积树的最小值的方式，达到排序的目的，时间复杂度是O()。
六. 快速排序（quick sort）
快速排序法的步骤为：
- 从数列中挑选基准值（pivot）；
- 重新排列数据，将所有比基准值小的排在基准值左边，所有比基准值大的牌在基准值的右边，如果与基准值相同可以排到任意一边；
- 递归式针对两边子序列做相同排序；
（注：当步骤2当一边的序列数量是0或1，则表示改编的序列已经完成排序）
6.1 代码如下：
import random
def quick_sort(nlist):
if len(nlist) <= 1:
return nlist
left = []
right = []
piv = []
pivot = random.choice(nlist)
for val in nlist:
if val == pivot:
piv.append(val)
elif val < pivot:
left.append(val)
else:
right.append(val)
return quick_sort(left)+piv+quick_sort(right)
data = [42,62,4,26,98,6,1,27]
print('原始列表：', data)
print('排序后的列表：', quick_sort(data))七. 合并排序（merge sort）
合并排序算法的精神是分治法（devide and conquer），主要是先将欲排列的序列分割（divide）成几乎等长的两个序列，这个动作重复chulzhidao序列只剩下一个数字无法再分割。接着合并（conquer）被分割的数列，主要将已排序最小单位的数列开始合并，重复处理，知道合并为与原数列相同大小的一个数列。
7.1 代码如下：
def merge(left, right):
output = []
while left and right:
if left[0] <= right[0]:
output.append(left.pop(0))
else:
output.append(right.pop(0))
if left:
output += left
if right:
output += right
return output
def merge_sort(nlist):
if len(nlist) <= 1:
return nlist
mid = len(nlist)//2
left = nlist[:mid]
right = nlist[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
data = [42,62,4,26,98,6,1,27]
print('原始列表：', data)
print('排序后的列表：', merge_sort(data))欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）