数据结构与算法专题汇总(四)排序,冒泡排序，插入排序，选择排序

一. 常见排序算法

排比较序算法	时间复杂度	是否基于比较
冒泡，插入，选择	O(n^2)	✅
快排，归并	O(nlogn)	✅
桶，计数，基数	O(n)	❌

分析排序算法

1. 执行效率：比较次数，交换次数
2. 内存消耗：原地排序？？
3. 稳定性

二. 常见算法原理及实现

1.冒泡排序

每一轮比较选出最大值放置在排序位置上
当一轮不出现交换的时候，表示数据已排序完毕，所以可设置一个哨兵，判读当前本轮是否有交换的情况。

def bubbleSort(numbers,length):
    if length <= 0:
        return 
    
    for i in range(length):
    #设置哨兵
        flag = False
        for j in range(length-i-1):
            if numbers[j] > numbers[j+1]:
                numbers[j],numbers[j+1] = numbers[j+1],numbers[j]
                flag = True
        
        if not flag:
            break

分析：

1. 原地排序
2. 稳定排序
3. 时间复杂度：
   最好：O(n)
   最坏：O(n^2)
   平均：O(n^2)

2.插入排序

从未排序区间中，一个个遍历，与已排序区间中的数据从后往前一个个比较，插入到已排序区间的对应位置中

def insertSort(numbers,length):
    if length <= 0:
        return 
    
    for i in range(1,length):
        j = i
        value = numbers[j]
        while j > 0:
            if numbers[j-1] > value:
                numbers[j] = numbers[j-1]
                j -= 1
        
        numbers[j] = value

算法分析

1. 原地排序
2. 不稳定排序
3. 最好 O(n)
   最坏O(n^2)
   平均O(n^2)

3.选择排序

从未排序区间中选择最小的，直接添加在已排序区间的末尾

def selectSort(numbers,length):
    if length <= 0:
        return 
    
    for i in range(0,length):
        min = i
        
        for j in range(i+1,length):
            if numbers[j] < numbers[min]:
                min = j
        
        temp = numbers[min]
        numbers[min] = numbers[i]
        numbers[i] = temp

分析

1. 原地排序
2. 稳定排序
3. 最好，最坏，平均：O(n^2)