排序算法Ⅰ之冒泡选择插入排序

0.1 算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 

0.2 算法复杂度

0.3 相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。 

冒泡排序

原理

俩俩比较相邻记录的排序码，若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。

性能

时间复杂度为O(N^2)，空间复杂度为O(1)。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。

代码

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

优化

1.假设我们现在排序ar[]={1,2,3,4,5,6,7,8,10,9}这组数据，按照上面的排序方式，第一趟排序后将10和9交换已经有序，接下来的8趟排序就是多余的，什么也没做。
所以我们可以设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。

def bubble_sort(arr):
    for i in range(1, len(arr)):
        flag = True
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = False
        if flag:
            break

2.优化一仅仅适用于连片有序而整体无序的数据(例如：1， 2，3 ，4 ，7，6，5)。但是对于前面大部分是无序而后边小半部分有序的数据(1，2，5，7，4，3，6，8，9，10)排序效率也不可观，对于种类型数据，我们可以继续优化。既我们可以记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可。

def bubble_sort(arr):
    k = len(arr) - 1
    for i in range(1, len(arr)):
        pos = 0
        for j in range(k):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                pos = j
        k = pos
        if pos == 0:
            break

3.优化二的效率有很大的提升，还有一种优化方法可以继续提高效率。大致思想就是一次排序可以确定两个值，正向扫描找到最大值交换到最后，反向扫描找到最小值交换到最前面。例如：排序数据1，2，3，4，5，6，0

def bubble_sort(arr):
    p = 0
    q = len(arr) - 1

    while True:
        pos = 0
        tmp = 0
        for j in range(p, q, 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                pos = j
        q = pos

        for m in range(q, p, -1):
            if arr[m] < arr[m-1]:
                arr[m], arr[m-1] = arr[m-1], arr[m]
                tmp = m
        p = tmp

        if pos == 0 or tmp == 0:
            break

第三种和第一种比较时间减少了3秒多。

import random
import time
import copy
li = list(range(10000))
random.shuffle(li)
print(li)
li1 = copy.deepcopy(li)
li2 = copy.deepcopy(li)

starttime=time.time()
bubbleSort(li1)
print(time.time()-starttime)
print(li1)

starttime=time.time()
bubble_sort(li2)
print(time.time()-starttime)

选择排序

原理

每次从未排序的序列中找到最小值，记录并最后存放到已排序序列的末尾

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕。

性能

时间复杂度为O(N^2)，空间复杂度为O(1)，排序是不稳定的（把最小值交换到已排序的末尾导致的），每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。

代码

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

优化

上面一趟只是找到一个最大值或者最小值，我们可以考虑每趟循环确定两个元素（当前趟的最大和最小记录）的位置，从而减少排序所需的循环次数。改进后对n个
数据进行排序，最多只需进行【n/2】趟排序即可

def selectionSort(arr):
    n = len(arr)
    for i in range(len(arr)//2):
        # 记录最小数的索引
        minIndex = i
        maxIndex = n-1

        for j in range(i, n):
            if arr[j] < arr[minIndex]:
                minIndex = j
            if arr[j] > arr[maxIndex]:
                maxIndex = j

        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
            # 如果最大值发生交换，更新最大值
            if i == maxIndex:
                maxIndex = minIndex

        # n 不是最大数时，将 n 和最大数进行交换
        if n-1 != maxIndex:
            arr[n-1], arr[maxIndex] = arr[maxIndex], arr[n-1]

        n -= 1

插入排序

原理

依次选择一个待排序的数据，插入到前边已排好序的序列中。

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
  

性能

时间复杂度为O(N^2)，空间复杂度为O(1)。算法是稳定的，比较次数和交换次数都与初始序列有关。

使用场景

当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。

代码

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current

优化

直接插入排序每次往前插入时，是按顺序依次往前找，可在这里进行优化，往前找合适的插入位置时采用二分查找的方式，即折半插入。
折半插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至O(NlogN)，排序是稳定的，但排序的比较次数与初始序列无关，总是需要foor(log(i))+1次排序比较。

def insert_sort_1(arr):
    n = len(arr)
    for i in range(1,n):#默认第一个是已经排好序的
        if arr[i] < arr[i-1]:#如果本次的值小于前一个(前面是排好序的)
            num = arr[i]  # 记录本次的值
            index = i  # 记录值的下标
            left = 0
            right = i-1
            # 待插入的值与已排序区域的中间值比较，不断缩小区域范围，直到left和right相遇。
            while left <= right:
                mid = (left + right) // 2
                if num < arr[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # 当left 和 right 相遇的时候,待插入的位置其实就是left的位置
            for j in range(i - 1, left - 1, -1):
                arr[j + 1] = arr[j]
            arr[left] = num