常用的排序算法总结

李玮

主要介绍冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序的思想，实现代码全部采用 Python 实现。准备工作

所谓 “磨刀不误砍柴工”，在进行排序算法练习的时候，我们需要做一些准备的工作：

• 生成算法需要的数列：随机数列
• 对于一些极端情况，考虑算法的效率，需要生成基本有序的数列
• 测试算法性能的函数
• 判断数列是否有序
• 数列中元素相互交换
• 数列的拷贝
  
  

生成随机数列

1. #coding=utf-8
   
2. from random import randint
   
3. def generateRandomArray(n, min, max):
   
4.     arr = []
   
5.     arr = [randint(min, max) for x in range(n)]
   
6.     return arr

复制代码

生成基本有序的数列

1. def generateNearlyOrderedArray(n, swapTimes):
   
2.     arr = []
   
3.     for i in range(n):
   
4.         arr.append(i)
   
5.     for j in range(swapTimes):
   
6.         posx = randint(0, n-1)
   
7.         posy = randint(0, n-1)
   
8.         arr[posx], arr[posy] = arr[posy], arr[posx]
   
9.     return arr

复制代码

判断数列是否有序（算法是否正确）

1. def isSorted(alist):
   
2.     for i in range(0, len(alist)-1):
   
3.         if alist[i] > alist[i+1]:
   
4.             return False
   
5.     return True

复制代码

测试算法性能（耗费时间）

1. t1 = timeit.Timer('testSort("某种排序算法函数", alist)', 'from __main__ import testSort, 某种排序算法函数, alist')
   
2. print('某种排序算法：%s s' %t1.timeit(number=1))
   
3. 
   
4. # func表示要检测的算法函数，alist为传入的数列
   
5. def testSort(func, alist):
   
6.     alist =  func(alist)
   
7.     assert isSorted(alist), "排序算法错误\n"

复制代码

数列中元素相互交换

Python 语言对于交换两个数列的元素非常简单：

1. alist[i], alist[j] = alist[j], alist[i]

复制代码

数列的拷贝

对于数列的拷贝，在 Python 语言中可以直接使用数列的切片：

1. # 直接使用切片
   
2. # list = [8,6,2,3,1,5,7,4]
   
3. alist=list[:]

复制代码

---

冒泡排序

算法思想

冒泡排序要对一个列表多次重复遍历。它要比较相邻的两项，并且交换顺序排错的项。每对 列表实行一次遍历，就有一个最大项排在了正确的位置。大体上讲，列表的每一个数据项都会在 其相应的位置 “冒泡”。如果列表有 n 项，第一次遍历就要比较 n-1 对数据。需要注意，一旦列 表中最大(按照规定的原则定义大小)的数据是所比较的数据对中的一个，它就会沿着列表一直 后移，直到这次遍历结束。

动图演示

代码实现

1. # 冒泡排序
   
2. def bubbleSort(alist):
   
3.     n = len(alist)
   
4.     for i in range(n-1, 0, -1):
   
5.         for j in range(0, i):
   
6.             if alist[j] > alist[j+1]:
   
7.                 alist[j], alist[j+1] = alist[j+1], alist[j]
   
8.     return alist

复制代码

优化点

因为冒泡排序必须要在最终位置找到之前不断交换数据项，所以它经常被认为是最低效的排 序方法。这些 “浪费式” 的交换操作消耗了许多时间。但是，由于冒泡排序要遍历整个未排好的 部分，它可以做一些大多数排序方法做不到的事。尤其是如果在整个排序过程中没有交换，我们就可断定列表已经排好。因此可改良冒泡排序，使其在已知列表排好的情况下提前结束。这就是说，如果一个列表只需要几次遍历就可排好，冒泡排序就占有优势：它可以在发现列表已排好时立刻结束。

优化代码

1. # 冒泡排序
   
2. def bubbleSort(alist):
   
3.     n = len(alist)
   
4.     exchange = False
   
5.     for i in range(n-1, 0, -1):
   
6.         for j in range(0, i):
   
7.             if alist[j] > alist[j+1]:
   
8.                 alist[j], alist[j+1] = alist[j+1], alist[j]
   
9.                 exchange = True
   
10.         # 如果发现整个排序过程中没有交换，提前结束
    
11.         if not exchange:
    
12.             break
    
13.     return alist

复制代码

选择排序

算法思想

选择排序提高了冒泡排序的性能，它每遍历一次列表只交换一次数据，即进行一次遍历时找 到最大的项，完成遍历后，再把它换到正确的位置。和冒泡排序一样，第一次遍历后，最大的数 据项就已归位，第二次遍历使次大项归位。这个过程持续进行，一共需要 n-1 次遍历来排好 n 个数 据，因为最后一个数据必须在第 n-1 次遍历之后才能归位。

动图演示

代码实现

1. # 选择排序
   
2. def selectionSort(alist):
   
3.     n = len(alist)
   
4. 
   
5.     for i in range(n - 1):
   
6.         # 寻找[i,n]区间里的最小值
   
7.         min_index = i
   
8.         for j in range(i+1, n):
   
9.             if alist[j] < alist[min_index]:
   
10.                 min_index = j
    
11.         alist[i], alist[min_index] = alist[min_index], alist[i]
    
12.     return alist

复制代码

---

插入排序

算法思想

插入排序的算法复杂度仍然是 ，但其工作原理稍有不同。它总是保持一个位置靠前的 已排好的子表，然后每一个新的数据项被 “插入” 到前边的子表里，排好的子表增加一项。我们认为只含有一个数据项的列表是已经排好的。每排后面一个数据（从 1 开始到 n-1），这 个的数据会和已排好子表中的数据比较。比较时，我们把之前已经排好的列表中比这个数据大的移到它的右边。当子表数据小于当前数据，或者当前数据已经和子表的所有数据比较了时，就可 以在此处插入当前数据项。

动图演示

代码实现

1. # 插入排序
   
2. def insertionSort(alist):
   
3.     for i in range(1,len(alist)):
   
4.         currentvalue=alist[i]
   
5.         position=i
   
6.         while alist[position-1]>currentvalue and position>0:
   
7.             alist[position]=alist[position-1]
   
8.             position=position-1
   
9.         alist[position]=currentvalue
   
10.     return alist

复制代码

注意，这里在用 Python 实现的时候需要注意，第一次我采用的是下面的代码：

1. # 插入排序
   
2. def insertionSort(blist):
   
3.     n = len(blist)
   
4.     for i in range(1, n):
   
5.         # 寻找a[i]合适的插入位置
   
6.         temp = blist[i]
   
7.         for j in range(i, 0, -1):
   
8.             if (temp < blist[j-1]):
   
9.                 blist[j] = blist[j-1]
   
10.             else:
    
11.                 break
    
12.         blist[j-1] = temp
    
13.     return blist

复制代码

在测试性能的时候发现，当数列的逐渐变大的时候，运行时间并不是按照 的速度增长，后来分析发现：

1. for j in range(i, 0, -1):

复制代码

这行代码在数列很大的时候，会不听的新建列表，这回损害性能，这是非算法思想因素的影响，但是需要注意一下。