Python实现排序及时间空间复杂度分析

一、冒泡排序（Bubble Sort）

原理：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。（从头到尾，从尾到头都可以）
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动画：

冒泡排序.gif

图片说明第一次排序：

冒泡排序.png
图片说明所有排序：
冒泡排序.png

Python实现：

def BubbleSort(matrix):
    for i in range(len(matrix) - 1):
        for j in range(len(matrix)-i-1):#要用到j+1，防止溢出，减掉1
            if matrix[j] > matrix[j + 1]:
                matrix[j], matrix[j + 1] = matrix[j + 1], matrix[j]
    return matrixB

从左到右找到依次找到较大的元素，如果左边的元素比右边的元素大，交换这两个元素。一共循环了len（matrix）-1次。

优化:
如果一个已经排好的数组，用这个算法还是要比较很多次。
所以增加一个flag，赋值为True，在一次循环中，如果没有两个元素进行交换，说明数组是已经排好序的，在当前循环结束时，flag的值没有发生改变依旧为True，可直接break出循环。

def BubbleSort(matrix):
    flag = True
    for i in range(len(matrix) - 1):
        for j in range(len(matrix) - i - 1):
            if matrix[j] > matrix[j + 1]:
                matrix[j], matrix[j + 1] = matrix[j + 1], matrix[j]
                flag = False
        if (flag): break
    return matrix

时间复杂度分析：
外层的for时间复杂度为O（n）
里层的时间复杂度分析如下：
因为里层的起点是0，结束是len（matrix）-i-1，（以下用n代替len（matrix））当i == 0 时，里层循环是n-1次，i == 1时，循环为n-1次，当i == n-1时，需要0次。把i为（0，n-1）时所有的循环次数加起来就是从0加到n-1，值为首项加尾项乘以项数除以二，即（0+n-1）n/2，这个的时间复杂度我O（n）。所有里层的循环时间复杂度为O（n）。
所以时间复杂度为O（n^2）

最差情况是需要交换n^2次，最好情况是不需要交换。

空间复杂度：
不需要额外的空间。所以O（1）

稳定性：
冒泡排序是一个稳定的排序方式，比如matrix = [25, 25, 3, 9, 23, 44, 29]时，出现了两个25，在冒泡排序结束后，从左边数的第一个25，在排序结束时，依旧是从左数的第一个25，它不会出现在第二个25的右面。（因为在元素相等的时候没有进行交换）

二、选择排序（Selction Sort）

原理：
第一次循环找出最大值（最小值），记录其下标，把他与最末尾（首）的元素交换，第二次找到第二大的，与倒数第二末尾的元素进行交换。第一次循环的范围是（0，数组长度-1），第二次是（0，数组长度-2）
动画：

选择排序.gif
图片说明：
选择排序.jpg
Python实现：

def SelectionSort(matrix):
    n = len(matrix)
    for i in range(n):
        index = 0
        for j in range(n - i):
            if matrix[j] > matrix[index]:
                index = j
        matrix[n - i - 1], matrix[index] = matrix[index], matrix[n - i - 1]

    return matrix

时间复杂度分析：
两次for循环：O（n^2），进行了O（n）次交换。

空间复杂度：
不需要额外的空间。所以O（1）

稳定性：
不稳定。

三、插入排序（Insert Sort）

原理：
相当于打牌时候摸牌，如数组[25, 5, 3, 9, 23, 44, 29]，第一张摸到的牌是25，第二张摸到了5，与25比较大小，放在25前面，依次摸完所有的牌，也就排序结束了。
动画：

插入排序.gif
图片说明：
插入排序.jpg
Python实现：

def InsertSort(matrix):
    n = len(matrix)
    for i in range(1, n):
        cur = i
        pre = cur - 1
        while pre >= 0 and matrix[cur] < matrix[pre]:
            if matrix[cur] < matrix[pre]:
                matrix[pre], matrix[cur] = matrix[cur], matrix[pre]
                cur = pre
                pre = cur - 1

    return matrix

定义一个cur来存储当前的下标，因为pre是cir-1，所以循环从1开始。

def InsertSort(matrix):
    n = len(matrix)
    for i in range(1, n):
        cur = i
        while cur - 1 >= 0 and matrix[cur] < matrix[cur - 1]:
            if matrix[cur] < matrix[cur - 1]:
                matrix[cur - 1], matrix[cur] = matrix[cur], matrix[cur - 1]
                cur -= 1

    return matrix

把pre用cur-1代替了。

也可以：

def InsertSort(matrix):
    for i in range(1, len(matrix)):
        tmp = i
        while i > 0:
            if matrix[i] < matrix[i - 1]:
                matrix[i], matrix[i - 1] = matrix[i - 1], matrix[i]
                i -= 1
            else:
                break

    return matrix

时间复杂度分析：
两个嵌套的循环，时间复杂度是O(n^2)。
虽然时间复杂度也是O(n^2)，但是第二层循环不需要与所有元素进行比较，所以在性能上优于冒泡排序和选择排序。
空间复杂度：
没有额外的存储空间，是原地排序算法O（1）。
稳定性：
稳定

四、希尔排序（Shell Sort）

原理：
实际上是插入排序的扩展，把数组分成几组，比如数组[25, 5, 3, 9, 23, 44, 29]，数组长度n为7，取gap = n/2，把数组的[i]和[i+gap]作为一组，比较[i]和[i+gap]的大小，如果[i]>[i+gap]，交换[i]和[i+gap]，如果[i]<[i+gap]，则继续比较[i+1]和[i+gap+1]，把数组里的所有元素都比较完之后，再把gap的值减小，可以减1，也可以把gap/2，继续比较，直至最后一次把数组中的所有元素作为一个整体排序。
动画：

希尔排序.gif
图片说明：
希尔排序.png
Python实现：

def ShellSort(matrix):
    n = len(matrix)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            for tmp in range(i, gap - 1, -gap):
                if matrix[tmp] < matrix[tmp - gap]:
                    matrix[tmp], matrix[tmp - gap] = matrix[tmp - gap], matrix[tmp]

        if gap == 2:
            gap = 1
        else:
            gap //= 2
    return matrix

五、计数排序（Count Sort）

使用范围：
数组长度有限，较小。
出现的重复数字比较多，并且这些数值较为集中。
原理：
抽屉原理：遍历数组，把相同的值都放到同一个抽屉中，遍历结束后，按照值从小到大的顺序依次取出，即排列完成。
动画：

计数排序.gif

图片说明：

计数排序.png

Python实现：

def CountSort(matrix):
    max = matrix[0]
    min = matrix[0]
    for i in matrix:  #找到list中的最大元素和最小元素
        if i > max:
            max = i
        if i < min:
            min = i

    tmp = [0] * (max - min + 1) # 定义一个新的数组，长度为最大值减最小值加一
    for i in range(len(matrix)):  #把原来数组中每个数字出现了多少次存在新数组中
        tmp[matrix[i] - min] += 1
    index = 0

    for j in range(len(tmp)):    # 
        while tmp[j] > 0:
            matrix[index] = min + j
            index += 1
            tmp[j] -= 1
    return matrix

时间复杂度分析：
第一个循环：O（n）
第二个循
环：O（n）
第三个循环：O（n），虽然有两个for但是实际上是从头到尾把元素都拿出来，只走了一遍所以时间复杂度还是O（n）
所以时间复杂度为O（n）
稳定性：
不稳定

六、归并排序（Merge Sort）

原理：
把数组从中间分成前后两个数组，再把前后两个数组每个数组再分，分到最小，然后对前后两部分分别排序，再将排好序的两部分合并在一起。

图片说明：

归并排序.jpg
Python实现：

def MergeSort(matrix):
    matrix = devide(matrix)
    return matrix


def devide(matrix):
    if len(matrix) <= 1:
        return matrix

    m = len(matrix) // 2
    a = devide(matrix[:m])
    b = devide(matrix[m:])
    return merge(a, b)

def merge(num1,num2):
    num = []

    while len(num1) > 0 and len(num2) > 0:
        if num1[0] > num2[0]:
            num.append(num2[0])
            num2.remove(num2[0])
        else:
            num.append(num1[0])
            num1.remove(num1[0])
    if len(num1) == 0:
        num += num2
    else:
        num += num1
    return num

时间复杂度：
时间复杂度是 O(nlogn)，要优于 O(n^2)。
空间复杂度：
空间复杂度是 O(n)。
稳定性：
稳定

七、快速排序（Quick Sort）

原理：
数组的一个元素赋给下标赋给first，末尾下标赋给last，把数组从左到右第一个元素的值赋给pivot，从数组末尾往前找到第一个比pivot值小的数，赋给matrix[first]，再从first往后找到第一个比pivot大的值，当first与last相遇时，把pivot的值赋给matrix[first]或matrix[last]，然后递归。

Python实现：

def QuickSort(matrix, i, j):
    if i >= j or i < 0 or j > len(matrix)-1:
        return
    else:
        first = i
        last = j
        pivot = matrix[i]
        while first < last:
            while first < last and matrix[last] > pivot:
                last -= 1

            matrix[i] = matrix[last]
            while first < last and matrix[first] < pivot:
                first += 1
            matrix[last] = matrix[first]

        matrix[first]= pivot

        QuickSort(matrix, i, first - 1)
        QuickSort(matrix, first + 1, j)
    return matrix

快排参考链接：
https://blog.csdn.net/u010005281/article/details/80084994

文章参考：
硬核！C语言八大排序算法，附动图和详细代码解释！
这或许是东半球分析十大排序算法最好的一篇文章
十大经典排序算法（动图演示）
数据结构与算法系列（五）基于选择的排序算法