面向研究生入学考试编程:排序算法 01 简单排序算法 木灵的炼金工作室

最近想要复习一下排序算法来应对考研。为了简洁地表示算法,我们使用python来描述(其实是因为懒得写CPP)。首先从比较直观(同时比较慢)的几个排序算法开始:

选择排序

每次选择数组中未处理部分的最小值交换到已处理部分的尾部,称为选择排序。

def selectionSort(arr):
    for i in range(len(arr)):
        minValue, minLoca = arr[i], i
        for j in range(i, len(arr)):
            if minValue > arr[j]:
                minValue, minLoca = arr[j], j
        arr[i], arr[minLoca] = arr[minLoca], arr[i]
    return arr

很直观地,对于长度为n的输入,这个排序算法的渐近时间复杂度是$O(n^2)$,额外空间是$O(1)$
当然,“选择最小值”这一操作明显可以变得更快:使用小堆优化,这个算法的时间复杂度可以下降至$O(n\log x)$,优化后的排序方式叫堆排序(这个今天不写)。

因为minValue > arr[j]条件中的大于号,这个排序算法的实现是稳定的。

插入排序

对于每一个未处理元素,在已处理部分中找到它应该在的位置并将其插入,称为插入排序。在插入之间需要预留出其位置,这个过程可以与寻找插入位置同时进行。

def insertSort(arr):
    for i in range(len(arr)):
        nowValue = arr[i]
        insertPoint = i - 1
        while insertPoint >= 0 and arr[insertPoint] > nowValue:
            arr[insertPoint + 1] = arr[insertPoint]
            insertPoint -= 1
        arr[insertPoint + 1] = nowValue
    return arr

对于长度为n的输入,这个排序算法的平均和最差渐近时间复杂度是$O(n^2)$,但最佳的时间复杂度是$O(n)$,额外空间是$O(1)$
由于arr[insertPoint] > nowValue,这个实现也是稳定的。

冒泡排序

冒泡排序也是几个最简单的算法之一。它的单元操作是:将数组中的一个逆序对调换为顺序对并将目前的操作位置右移1。每次遍历一遍数组,它都会将未处理区域中目前访问到的最大元素一直向后移动直到遇到更大的或者到达未处理区域的末端,所以它叫冒泡算法。

def bubbleSort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

对于长度为n的输入,这个排序算法的平均和最差渐近时间复杂度是$O(n^2)$,最佳的时间复杂度是$O(n)$,额外空间是$O(1)$
由于arr[j] > arr[j + 1],若两元素键值相等,在后边的元素不会被交换,所以这个实现是稳定的


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn