• o(n^2)级别排序算法

为什么要学习O(n^2)的排序方法？

● 基础 ● 编码简单，易于实现，是一些简单情景的首选 ● 在一些特殊情况下，简单的排序算法更有效 ● 简单的排序算法思想衍生出复杂的排序算法 ● 作为子过程，改进更复杂的排序算法

1.选择排序 Selection Sort

每次选择没有排序部分的最小值和第一位交换

def selection_sort(org_arr, length):    """    选择排序，每次选择未排序部分的最小值和未排序部分的第一位交换位置    :param org_arr: 待排序数组    :param length: 待数组长度    :return:    """    for i in range(0, length):        # 寻找[i,n)区间里的最小值        main_index = i        for j in range(i+1, length):            if org_arr[j] < org_arr[main_index]:                main_index = j        org_arr[i], org_arr[main_index] = org_arr[main_index], org_arr[i]复制代码

2.插入排序 Insertion Sort

从左到右遍历每一个元素，每次将这个元素和前面的元素一一比较，如果比某个元素小，则跟其交换

def insert_sort(arr, n):    """    选择排序，每次选择未排序部分的最小值和未排序部分的第一位交换位置    :param arr:    :param n:    """    for i in range(0, n):        # 寻找元素arr[i]合适的插入位置        e = arr[i]        j = i  # j保存元素e应该插入的位置        while arr[j-1] > e and j > 0:            arr[j] = arr[j-1]            j -= 1        arr[j] = e复制代码

* 选择排序一个特别重要的性质：当找到合适的位置以后（arr[j-1] > e），可以提前终止内层循环

这使得在一个近乎有序的数组在进行插入排序的时候，效率要高的多，设置比o(logn)的算法效率还要高 当排序一个完全排序的数组时，插入排序的算法复杂度为o(n)级别