常用排序算法Python实现

本文仅提供冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序的Python实现。

在最开始先列出上述排序算法的时间复杂度：

• 冒泡排序bubbleSort()复杂度O(n^2)

• 选择排序 selectionSort() 复杂度O(n^2)

• 插入排序 insertionSort() 复杂度O(n^2)

• 希尔排序 shellSort() 复杂度O(n)与O(n^2)之间

• 归并排序 mergeSort() 复杂度O(nlog n) 需要额外使用一倍的存储空间

• 快速排序 quickSort() 复杂度O(nlog n) 不需要额外使用存储空间

冒泡排序

冒泡排序的思路在于对无序表进行多趟比较交换。

每趟包括了多次两两相邻比较，并将逆序(顺序)的数据项互换位置，最终能将本趟的最大项(最小项)就位。

经过n-1次比较、交换，实现整表的排序。

def bubbleSort(list):
  # num就是还未完成排序的数据项的最后一项的下标
  for num in range(len(list)-1, 0, -1):
    # 将未排序的数据项两两比较进行排序
    for i in range(num):
      if list[i] > list[i+1]:
        list[i], list[i+1] = list[i+1], list[i]

选择排序

选择排序对冒泡排序进行了改进，保留了其基本的多趟比对思路，每趟都使当前最大项就位

但选择排序对交换进行了削减，相比起冒泡排序进行多次交换，每趟仅进行1次交换，记录最大项的所在位置，最后再跟本趟最后一项交换

def selectionSort(list):
  # 与冒泡排序思想一致
  for num in range(len(list)-1, 0, -1):
    # 最大项所在的位置
    posMax = 0
    # 需要下标，所以num+1保证可取到到最后一项的下标
    for i in range(num+1):
      # 存储本趟的最大数据的位置
      if list[i] > list[posMax]:
        posMax = i
    # 循环结束后将最大数据放到最后，即num的位置
    list[num],list[posMax] = list[posMax],list[num]

插入排序

插入排序维持一个已排好序的子列表，其位置始终在列表的前部，然后逐步扩大这个子列表直到全表

第1趟，子列表仅包含第1个数据项，将第 2个数据项作为“新项”插入到子列表的合适位置中，这样已排序的子列表就包含了2个数据项

第2趟，再继续将第3个数据项跟前2个数据项比对，并移动比自身大的数据项，空出位置来，以便加入到子列表中

经过n-1趟比对和插入，子列表扩展到全表，排序完成

def insertionSort(list):
  for i in range(1, len(list)):
    # 要插入的值
    currentVal = list[i]
    # 目前的位置
    pos = i
    # 如果 不在第一位且前一位的值大于要插入的值
    while pos > 0 and list[pos-1] > currentVal:
      # 将前一位的值放到当前pos位置
      list[pos] = list[pos-1]
      # 将pos前移
      pos -= 1
    # 在合适的位置将要插入的值插入
    list[pos] = currentVal

冒泡排序，选择排序，插入排序的时间复杂度都比较高，也比较容易理解，接下来的几个排序算法需要好好理解一下。

希尔排序

希尔排序是一种分组的插入排序算法

对无序表进行“间隔”划分子列表，每个子列表都执行插入排序

随着子列表的数量越来越少，无序表的整体越来越接近有序，从而减少整体排序的比对次数

最后一趟是标准的插入排序，但由于前面 几趟已经将列表处理到接近有序，这一趟仅需少数几次移动即可完成

上边的描述可能比较难以理解，给一个小示例作为思路就可以懂了：

''' 希尔排序思路
假定有一个列表list=[6,5,3,2,8,7,1,9,4],n为列表长度9
1.首先取一个整数d1=n//2，将元素分为d1个组，每组内相邻两元素之间距离为d1，在各组内直接进行插入排序：
	d1 = len(list) // 2 = 4
  	第一组    6        8       4
  	第二组      5        7
  	第三组        3        1
 	第四组          2        9
  	分为4组，每组内相邻两数据间隔为4，每组内进行排序
  	排序之后结果为：
    	第一组    4        6       8
    	第二组      5        7
    	第三组        1        3
    	第四组          2        9
  	然后将其恢复为列表：
    list = [4,5,1,2,6,7,3,9,8]
2.取第二个整数d2=d1//2，重复上述排序过程，直到d=1，也就是所有元素在一个组内排序
	d2 = d1 // 2 = 2
  	第一组      4   1   6   3   8
  	第二组        5   2   7   9
  	分为两组，间隔为2，每组内进行插入排序
    	第一组      1   3   4   6   8
    	第二组        2   5   7   9
  	恢复为列表：
    list = [1,2,3,5,4,7,6,9,8]
  	取第三个整数，d3 = d2 // 2 = 1，即只有这一组数据
  	此时列表已经接近有序，进行一次插入排序即可
  	list = [1,2,3,4,5,6,7,8,9]
'''

可以发现，希尔排序就是分为多个组，在每个组内进行插入排序，不同的是排序的间隔不再是1，而是同组内相邻两元素的距离gap

只是逻辑上分为多个组进行排序，并没有真的将列表拆分为多个列表

# 希尔排序算法
def shellSort(list):
  # 去gap
  gap = len(list) // 2
  # gap大于等于1就分组进行插入排序
  while gap >= 1:
    insertSortGap(list, gap)
    gap = gap // 2
# 改造后可接收gap的插入排序
def insertSortGap(list, gap):
  # 由于是分组进行，所以是从第一组的第二个元素的下标开始进行插入排序
  for i in range(gap, len(list)):
    current = list[i]
    pos = i
    # 分组就在此处表现，每次pos与pos-gap两个位置去比较，而不是与其前1位进行比较
    # 也就从逻辑上分为了多个组
    while pos > 0 and list[pos-gap] >current:
      list[pos] = list[pos-gap]
      pos -= gap
    list[pos] = current

归并排序

归并排序是递归算法，思路是将数据表持续分裂为两半，对两半分别进行归并排序，即先分解后合并。

也简单说一下思路好了：

'''
假定有一个列表list=[6,5,3,2,8,7,1,9]
分解过程：一层一层分解
             [6,5,3,2,8,7,1,9]
        [6,5,3,2]          [8,7,1,9]
    [6,5]     [3,2]     [8,7]     [1,9]
  [6]   [5]  [3]  [2]  [8]  [7]  [1]  [9]
合并过程：一层一层合并
第一次：
             [6,5,3,2,8,7,1,9]
        [6,5,3,2]          [8,7,1,9]
    [5,6]     [2,3]     [7,8]     [1,9]
第二次：
             [6,5,3,2,8,7,1,9]
        [3,2,5,6]          [1,7,8,9]
第三次：
             [1,2,3,5,6,7,8,9]
'''

看一下代码，应该很容易理解，就是一个递归。

def mergeSort(list):
  # 如果只有一个数据，就不需要再分解了，这是递归的结束条件
  if len(list) <= 1:
    return list
  # 取中间值
  mid = len(list) // 2
  # 左右两侧继续分解
  left = mergeSort(list[:mid])
  right = mergeSort(list[mid:])
  # 准备一个空列表用于存放排好序的数据,这也就是所需的额外一倍内存空间
  merged = []
  # 合并
  while left and right:
    if left[0] < right[0]:
      # 注意这里不能直接放left[0]，要把left[0]从left中删除并放入merged
      merged.append(left.pop(0))
    else:
      merged.append(right.pop(0))
  # while循环结束，left或者right肯定有一个是空的，另一个是有数据的
  # 将剩余的数据直接放入merged中
  merged.extend(right if right else left)
  '''
  extend函数用于在列表末尾一次性追加另一个列表中的多个值，如果不懂也可以写：
  while left:
    merged.append(left[0])
  while right:
    merged.append(right[0])
  '''
  # 将排序好的列表返回
  return merged

快速排序

快速排序的思路是依据一个“中值”数据 项来把数据表分为两半

小于中值的一半 和大于中值的一半，然后每部分分别进行快速排序(递归)

快速排序的递归算法“递归三要素”如下

​ 基本结束条件:数据表仅有1个数据项，自然是排好序的

​ 缩小规模:根据“中值”，将数据表分为两半，最好情况是相等规模的两半

​ 调用自身:将两半分别调用自身进行排序

注意：排序基本操作在分裂过程中完成！

快速排序的思路：

1. 选定中值，将表分为两半，最好是想等规模的两半

2. 将两半分别调用自身进行排序(排序操作在分裂过程中)

3. 设置左右标：

   • 左标向右移动，右标向左移动

   • 左标一直向右移动，碰到比中值大的就停止

   • 右标一直向左移动，碰到比中值小的就停止

   • 然后把左右标所指的数据项交换

   • 直到左标移动到右标的右侧，即交错，停止移动

   • 此时右标所指的位置就是中值应处的位置

   • 将中值和这个位置的值进行交换

   • 此时分裂完成，左半部比中值小，右半部比中值大

# 主程序
def quickSort(list):
  # 调用辅助程序，执行分裂操作
  quickSortHelper(list, 0, len(list)-1)
# 辅助程序
def quickSortHelper(list, first, last):
  # 如果最左侧下标 ＜ 最右侧下标，说明至少还有两个值
  if first < last:
    # 调用partition函数返回中值点
    splitPoint = partition(list, first, last)
    # 拿到中值点的位置，分别将左右两侧递归调用进行排序
    # 中值点在分裂过程中是已经排好序的，所以不需要对其进行排序
    quickSortHelper(list, first, splitPoint-1)
    quickSortHelper(list, splitPoint+1, last)
# 分裂程序
def partition(list, first, last):
  # 将第一个值作为中值
  pivotValue = list[first]
  # 设置左右标
  leftMark = first + 1
  rightMark = last
  # 左右标是否停止移动的标记
  done = False
  while not done:
    # 如果左标不大于右标且左标数据小于中值，左标向右移动
    while leftMark <= rightMark and list[leftMark] <= pivotValue:
      leftMark += 1
    # 如果左标不大于右标且右标数据大于中值，右标向左移动
    while leftMark <= rightMark and list[rightMark] >= pivotValue:
      rightMark -= 1
    # 程序运行到这里肯定是上述两个循环程序都因为某个条件不满足
    # 如果是因为右标小于左标了，那就停止移动
    if rightMark < leftMark:
      done = True
    else:
      # 不然就是因为左标的数据大于中值，右标的数据小于中值了
      # 此时交换左右标的数据
      list[leftMark], list[rightMark] = list[rightMark], list[leftMark]
  # 跳出循环了则满足rightMark < leftMark
  # 由于是从小到大排列的，所以此时左标的位置数据大于中值，右标的位置的数据小于中值
  # 我们将中值和右标所处位置的数据交换，即可保证中值左侧的比他小，右侧的比他大
  list[first], list[rightMark] = list[rightMark], list[first]
  # 我们将应该存放中值的位置返回出去，用于程序对中值两侧分别进行快排
  return rightMark

快速排序的算法比较绕，理解了中值应该放到什么位置，就能比较好的理解这个排序算法了。