排序算法

1、概述

排序算法可以说是数据结构与算法当中最为基础的部分，针对的是数组这一数据结构。将数组中的无序数据元素通过算法整理为有序的数据元素即为排序。

2、简单排序

2.1 冒泡排序

简介：

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地访问要排序的数列，将每次访问的最大值“浮”到数组尾部。

步骤如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个，直到把最大的元素放到数组尾部。
  2. 遍历长度减一，对剩下的元素从头重复以上的步骤。

  3. 直到没有任何一对数字需要比较时完成。

    实现代码：

    1. def bubbleSort(arr):
    2.  for i in range(len(arr))[::-1]:
    3.      for j in range(i):
    4.          if arr[j] > arr[j + 1]:
    5.              swap(arr[j], arr[j + 1])

    效果图：

    七种排序算法——冒泡，选择，插入，希尔，快速，归并，堆 - 图1

    2.2 选择排序

    简介：

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，重复上述过程，直到所有元素均排序完毕。

    步骤如下：

  4. 遍历数组，找到最小的元素，将其置于数组起始位置。

  5. 从上次最小元素存放的后一个元素开始遍历至数组尾，将最小的元素置于开始处。

  6. 重复上述过程，直到元素排序完毕。

    实现代码：

    1. def selectSort(arr):
    2.  for i in range(len(arr)):
    3.      min = i
    4.      for j in range(i, len(arr)):
    5.          if arr[j] < arr[min]:
    6.              min = j
    7.      swap(arr[i], arr[min])

    效果图：

    七种排序算法——冒泡，选择，插入，希尔，快速，归并，堆 - 图2

    2.3 插入排序

    简介：

    插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

    步骤如下：

  7. 从第一个元素开始，该元素可以认为已经被排序

  8. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  9. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  10. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  11. 将新元素插入到该位置中

  12. 重复步骤2

    实现代码：

    1. def insertSort(arr):
    2.  for i in range(len(arr)):
    3.      tmp = arr[i]
    4.      pre = i - 1
    5.      while pre >= 0 and arr[pre] > tmp:
    6.          arr[pre + 1] = arr[pre]
    7.          pre -= 1
    8.      arr[pre + 1] = tmp

    3、高级排序

    3.1 希尔排序

    简介：

    希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

    步骤如下：

  13. 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；

  14. 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

    实现代码：

    1. def insertSort(arr):
    2.  k = 1
    3.  while k < len(arr) / 3:
    4.      k = 3 * h + 1 //此处为Knuth算法
    5.  while k > 0:
    6.      for i in range(k, len(arr)):
    7.          tmp = arr[i]
    8.          pre = i - k
    9.          while pre >= 0 and arr[pre] > tmp:
    10.              arr[pre + k] = arr[pre]
    11.              pre -= k
    12.          arr[pre + k] = tmp
    13.      k = (k - 1) / 3

    效果图：

    七种排序算法——冒泡，选择，插入，希尔，快速，归并，堆 - 图3

    3.2 快速排序

    简介：

    快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

    步骤如下：

  15. 从数列中挑出一个元素，称为 “基准”（pivot），

  16. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

  17. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

    实现代码：

    1. def quickSort(arr, low, high):
    2.  if low < high:
    3.      pivot = partition(arr, low, high)
    4.      quickSort(arr, low, pivot - 1)
    5.      quickSort(arr, pivot + 1, high)
    6. def partition(arr, low, high):
    7.  pivot = arr[low]
    8.  while low < high:
    9.      while low < high and arr[high] >= pivot:
    10.          high -= 1
    11.      arr[low] = arr[high]
    12.      while low < high and arr[low] <= pivot:
    13.          low += 1
    14.      arr[high] = arr[low]
    15.  arr[low] = pivot
    16.  return low

    效果图：

    七种排序算法——冒泡，选择，插入，希尔，快速，归并，堆 - 图4

    3.3 归并排序

    简介：

    归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

    步骤如下：

  18. 申请空间，创建两个数组，长度分别为两个有序数组的长度

  19. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  20. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  21. 重复步骤3直到某一指针达到序列尾

  22. 将另一序列剩下的所有元素直接复制到合并序列尾

    实现代码：

    1. def mergeSort(arr, low, high):
    2.  if low < high:
    3.      mid = low + (high - low) / 2
    4.      mergeSort(arr, low, mid)
    5.      mergeSort(arr, mid + 1, high)
    6.      return merge(arr, low, mid, high)
    7. def merge(arr, low, mid, high):
    8.  leftArr = arr[low : mid + 1]
    9.  rightArr = arr[mid + 1 : high + 1]
    10.  i, j, m = 0, 0, low
    11.  while i < len(leftArr) and j < len(rightArr)：
    12.      if leftArr[i] < rightArr[j]:
    13.          arr[m] = leftArr[i]
    14.          i += 1
    15.      else:
    16.          arr[m] = rightArr[j]
    17.          j += 1
    18.      m += 1
    19.  while i < len(leftArr):
    20.      arr[m] = leftArr[i]
    21.      m += 1
    22.      i += 1
    23.  while j < len(rightArr):
    24.      arr[m] = rightArr[j]
    25.      m += 1
    26.      j += 1

    实现效果：

    七种排序算法——冒泡，选择，插入，希尔，快速，归并，堆 - 图5

    3.4 堆排序

    简介：

    堆积排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

    步骤如下：

  23. 按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；

  24. 将R[0..n-1]调整为堆，交换R[0]和R[n-1]；
  25. 重复上述过程，直到交换了R[0]和R[1]为止。

    实现代码：

    1. def heapSort(arr):
    2.  for i in range(len(arr) / 2)[::-1]:
    3.      heapAdjust(arr, i, len(arr) - 1)
    4.  for i in range(len(arr) - 1)[::-1]:
    5.      swap(arr[i], arr[0])
    6.      heapAdjust(arr, 0, i)
    7. def heapAdjust(arr, parent, length)：
    8.  tmp = arr[parent]
    9.  child = 2 * parent + 1
    10.  while child < length:
    11.      if child + 1 < length and arr[child + 1] > arr[child]:
    12.          child += 1
    13.      if arr[child] <= tmp:
    14.          break
    15.      arr[parent] = arr[child]
    16.      parent = child
    17.      child = 2 * parent + 1
    18.  arr[parent] = tmp

    效果图：

    七种排序算法——冒泡，选择，插入，希尔，快速，归并，堆 - 图6

    4、各排序算法时间空间复杂度

    七种排序算法——冒泡，选择，插入，希尔，快速，归并，堆 - 图7