简单排序（选择排序、起泡排序和插入排序）使用详解

简单排序算法

简单排序算法是一类算法，指那些直观、易理解的排序算法的总和。

到现在为止，我们已经讲了的三种排序算法：选择排序、起泡排序和插入排序，都属于简单排序算法。

这三种算法有许多性能上的共性，本章就我们来类比看看。

时间复杂度

排序的时间复杂度

假设我们要排列的数值共有 n 个，那么排序算法的时间复杂度应该是大 O 符号下一个 n 的函数——Of(n)。

排序算法的时间复杂度不能一概而论，而是要区分最好情况，最坏情况和一般情况：

• 最好 情况是指待排数列原本就是有序的；

• 最坏 则是指待排数列是倒序的；

• 最好最坏和介于两者之间的各种情况的综合属于一般（ 平均 ）情况。

最坏时间复杂度

enter image description here

我们先来看看最坏情况。最坏情况对应到实际中，是给一个倒序的数列排序。

从代码的角度来看，就是将一个算法中所有的代码全都足额跑满，没有任何中途的 break/return/exit！

既然如此，就让我们先来对比一下三个排序算法的代码：

def selectionSort(arr):
    for i in range(0, len(arr)):
        minPosition = i
        for j in range(i+1, len(arr)): 
            if (arr[j] < arr[minPosition]):
                minPosition = j
        swap(arr, i, minPosition) 
    return

def bubbleSort(arr):
    for i in range(0, len(arr) - 1):
        swapped = False
        for j in range(len(arr) -1, i, -1):
            if (arr[j] < arr[j - 1]):
                swap(arr, j, j-1)
                swapped = True
        if (not swapped):
            return
    return

def insertionSort(arr):
    if (len(arr) == 1):
        return
    for i in range(1,len(arr)):
        for j in range(i, 0, -1): 
            if arr[j] < arr[j-1]:
                swap(arr, j, j - 1)
            else:
                break
    return            

大家发现没有，这三个算法的主体结构，都是两重嵌套的循环。

在这里再向大家透露一个窍门：一旦遇到这种两重循环的结构，当其无论内循环还是外循环都和数据量（n）直接相关时，我们基本上可以肯定，它的最差情况时间复杂度就是 O(n2).

如果不信，咱们可以一个个来看一下：

• 选择排序：

  • 第 1 次迭代，外圈走 1 步，内圈走 （n−1）步；
  • 第 2 次迭代，外圈走 1 步，内圈走 （n−2）步；
  • ……
  • 第 n−1 次迭代，外圈走 1 步，内圈走 1 步；
  • 第 n 次迭代，外圈走 1 步，内圈跳过；全部迭代结束。