1.1 插入排序

插入排序算法就是把给定的数组中的元素一次插入到一个新的数组中，最终得到一个完整的有序数组。
插入排序的平均时间复杂度是O(nn),最好的情况下的时间复杂度是O(n)，最坏的情况下时间复杂度是O(nn)。它的空间复杂度是O(1)。
插入排序算法是一个稳定的排序算法。排序算法可以分为稳定算法和不稳定算法两类。冒泡排序、插入排序、和归并排序都是稳定的排序算法。选择排序、希尔排序、和快速排序都是不稳定的排序算法。

代码实现：

list = [1,8,6,7,2,4,9,3]
for i in range(len(list)):
    for j in range(i):
        if list[j]>list[i]:
            ins = list[i]
            list.pop(i)
            list.insert(j,ins)
            print(list)
            break

运行结果：

[1, 6, 8, 7, 2, 4, 9, 3]

[1, 6, 7, 8, 2, 4, 9, 3]

[1, 2, 6, 7, 8, 4, 9, 3]

[1, 2, 4, 6, 7, 8, 9, 3]

[1, 2, 3, 4, 6, 7, 8, 9]

代码中第一个for循环遍历未排序的元素，因为第一个元素自己肯定是有序状态，所以我们可以直接从第二个元素开始进行插入排序。

第二个for循环遍历的是已经排序的元素，假如在未排序的元素中发现比已经排序元素小的元素，则将其进插入到已排序元素的前面。

比如说第一次for循环遍历未排序序列，下标从1开始此时的list[i]=8，有序序列中只有一个1，不满足交换条件，下标直接后移一位，第二次遍历未排序序列6，6小于有序序列的8 ，这时将6插入到8的前面，此时的有序列表为[1,6,8],无序列表为[7,2,4,9,3], 以此遍历结束就完成了插入排序。

1.2 选择排序

选择排序表示从无序的数组中，每次选择最小或者最大的数据，从无序数组中放到有序数组中的末尾，以达到排序的效果。
选择排序的平均时间复杂度是O(nn),最好的情况下和最坏的情况下时间复杂度都是O(nn)。它是一个不稳定的排序算法。

代码实现：

list = [1,8,6,7,2,4,9,3]
for i in range(0,len(list)-1):
    for j in range(i+1,len(list)):
        if list[i] > list[j]:
            temp = list[i]
            list[i] = list[j]
            list[j] = temp
print(list)

运行结果：

[1, 6, 8, 7, 2, 4, 9, 3]
[1, 2, 8, 7, 6, 4, 9, 3]
[1, 2, 7, 8, 6, 4, 9, 3]
[1, 2, 6, 8, 7, 4, 9, 3]
[1, 2, 4, 8, 7, 6, 9, 3]
[1, 2, 3, 8, 7, 6, 9, 4]
[1, 2, 3, 7, 8, 6, 9, 4]
[1, 2, 3, 6, 8, 7, 9, 4]
[1, 2, 3, 4, 8, 7, 9, 6]
[1, 2, 3, 4, 7, 8, 9, 6]
[1, 2, 3, 4, 6, 8, 9, 7]
[1, 2, 3, 4, 6, 7, 9, 8]
[1, 2, 3, 4, 6, 7, 8, 9]

首先我们固定第一个元素，然后我们遍历第一个元素之后的所有元素，如果存在元素比固定的元素小，则利用中间变量temp实现两值互换。
比如第一次固定元素1，1之后不存在比1小的元素，然后下标后移固定元素8，向后遍历6比8小，两值互换，此时8的位置变成了6，也就是此时固定的元素是6，然后继续向后遍历7比6大不做操作，然后继续向后遍历2比6小，两值互换，此时的固定元素变成了2，继续向后遍历直到第二层for循环完成。然后进行新的遍历。

1.3 冒泡排序

冒泡排序采用重复遍历数组并一次比较相邻元素的方法来排序。由于在冒泡算法进行排序的过程中，最大数/最小数会慢慢“浮”到数组的末尾，所以算法由此命名。
冒泡排序的平均时间复杂度是O(nn),最好情况下的时间复杂度是O(n)，最坏情况下的时间复杂度是O(nn)。它的空间复杂度是O(1)。冒泡排序算法是一个稳定的排序算法。

代码实现：

list = [1,8,6,7,2,4,9,3]
for i in range(len(list)-1):
    for j in range(len(list)-i-1):
        if list[j]>list[j+1]:
            temp = list[j]
            list[j] = list[j+1]
            list[j+1] = temp
            print(list)

运行结果：

[1, 6, 8, 7, 2, 4, 9, 3]
[1, 6, 7, 8, 2, 4, 9, 3]
[1, 6, 7, 2, 8, 4, 9, 3]
[1, 6, 7, 2, 4, 8, 9, 3]
[1, 6, 7, 2, 4, 8, 3, 9]
[1, 6, 2, 7, 4, 8, 3, 9]
[1, 6, 2, 4, 7, 8, 3, 9]
[1, 6, 2, 4, 7, 3, 8, 9]
[1, 2, 6, 4, 7, 3, 8, 9]
[1, 2, 4, 6, 7, 3, 8, 9]
[1, 2, 4, 6, 3, 7, 8, 9]
[1, 2, 4, 3, 6, 7, 8, 9]
[1, 2, 3, 4, 6, 7, 8, 9]

冒泡排序算法使用了两个for循环。外层for循环用于遍历整个数组，由于每走一次外层for循环，数组中的最大数都会被交换到末尾，对应的i就是已经排好的序列长度，len(list)-i就是没有排好的序列长度，因此我们在第二层for循环中只需要遍历len(list)-i就可以了。
比如第一次遍历是i为0对应排好的序列长度为0，未排序的序列长度就是len(list)，因此第二层for循环需要对整个数组进行遍历，整个过程将8和7交换，8和2交换，8和4交换，9和3交换，在进行外层第一次遍历之后我们发现，数组中的最大数已经浮到数组最后面，下一次遍历对应排好的序列长度i，不需要再对已经排好的最后i位进行遍历，未排序的序列长度就是len(list)-i,这样整个外层for循环结束后就对数组排好序了。

1.4 归并排序

归并排序就是将把一个数列拆分位子数列，对子数列进行排序后，再把有序的子数列合并为完整的有序序列的算法。它实际上采用了分治的思想。
归并排序的平均时间复杂度是O(nlgn)，最好和最坏的情况下时间复杂度都是O(nlgn)。它的空间复杂度是O(1)。归并排序是一个稳定的排序算法。

代码实现：

num = [1, 8, 6, 7, 2, 4, 9, 3]
def mergesort(lis):
    if len(lis) < 2:
        return lis
    mid = int(len(lis)/2)
    l_list = mergesort(lis[:mid])
    r_list = mergesort(lis[mid:])
    re = []
    i, j = 0, 0
    while i < len(l_list) and j < len(r_list):
        if l_list[i] < r_list[j]:
            re.append(l_list[i])
            i += 1
        else:
            re.append(r_list[j])
            j += 1
    re += l_list[i:] + r_list[j:]
    print(re)
    return re

mergesort(num) 

运行结果：

[1, 8]
[6, 7]
[1, 6, 7, 8]
[2, 4]
[3, 9]
[2, 3, 4, 9]
[1, 2, 3, 4, 6, 7, 8, 9]

我们首先再递归函数里面写了递归的终止条件，当传入递归函数的数组只有一个元素时，这个数组一定是有序的我们就将其返回给上一层递归函数，上一层递归函数将有序的l_list 和 r_list中的元素进行比较，分别遍历两个数组，把小的元素放到合并数组中去，这样循环下去，肯定会有一个数组中的元素被拿完，这时我们终止while循环，把没有拿完的数组中的元素在放到合并数组后面，这样就可以将两个有序序列合并为一个有序序列了。
比如在最后一次递归中数组被分成了[1] [8] [6] [7]···· 因为其满足终止条件，直接会将他们返回给上一层递归函数，l_list=[1] r_list=8。在while循环中因为l_list[0] < r_list[0]所以把1放入合并序列，再把数组中剩的元素放到合并数组后面，所以合并序列变成了[1,8] 同样同层的另一个函数合并序列变成了[6,7]。它们又都把合并好的有序序列返回给了上一层递归函数，l_list = [1,8] r_list=[6,7],在while循环中首先1放入合并序列然后6放入合并序列，然后7放入合并序列，此时因为j不小于len(r_lsit)，所以退出while循环，最后把数组中剩的元素8放到合并数组后面，把[1,6,7,8]再返回给上一层递归函数，这样逐步的就完成了归并排序。

归并排序.PNG

1.5 快速排序

快速排序的思想是取数组中的一个值作为基准值，把所有小于基准值的数都放在它的一侧，大于基准值的数都放在它的另一侧。然后对于基准值左右两侧的数组进行递归操作。
快速排序算法的平均时间复杂度是O(nlgn)，最好情况下的时间复杂度是O(nlgn)。最坏情况下可能退化成O(n*n)，但是这种情况很少见。它的空间复杂度是O(nlgn)。它是一个不稳定的排序算法。如果使用得当，它的速度可以达到归并排序 和堆排序的数倍。

代码实现：

num = [6, 8, 1, 7, 2, 4, 9, 3]
def quciksort(lis):

    if len(lis)<2:
        print(lis)
        return lis
    base = lis[0]
    l_list, m_list, r_list = [], [base], []
    for i in range(1, len(lis)):
        if lis[i] < base:
            l_list.append(lis[i])
        elif lis[i] > base:
            r_list.append(lis[i])
        else:
            m_list.append(lis[i])
    re_llist = quciksort(l_list)
    re_rlist = quciksort(r_list)
    print(re_llist + m_list + re_rlist)
    return re_llist+m_list+re_rlist

quciksort(num)

运行结果：

[]
[]
[3]
[]
[3, 4]
[2, 3, 4]
[1, 2, 3, 4]
[7]
[9]
[7, 8, 9]
[1, 2, 3, 4, 6, 7, 8, 9]

我们还是定义一个递归终止条件，当数组中的元素小于2时，数组中的序列肯定是有序序列，我们直接将其返回给上一层递归函数，我们定义了三个数组,l_list 用于保存比基准值小的值，r_list 用于保存比基准值大的值，m_list 用于保存基准值和与基准值同样大的值，然后我们会别对l_list和r_list 做递归操作。
比如我呢首先把6作为了基准值，经过for循环遍历后l_list变成了[1,2,4,3],r_list变成了[8,7,9]，m_list变成了[6],然后我们拿r_list进行递归操作来说，l_list = [7]，r_list[9]，m_list[8],然后又会对l_list和r_list进行递归操作，因为其满足递归终止条件，所以它会返回给re_llist [7]给re_rlist[9]，拿到re_llist和re_rlist之后，它又会返回给上一层递归函数re_rlist[7,8,9]，同样左边的re_llist会拿到[1,2,3,4]，最终会输出[1,2,3,4,6,7,8]。

快速排序.PNG

1.6 希尔排序

希尔排序又叫“缩小增量排序”，是对插入排序进行优化后产生的一种排序算法。它的执行思路是：把数组中的元素按下标增量分组，对每一个数组进行插入排序后。缩小增量并重复之前的步骤，直到增量到达1。
希尔排序的时间复杂度是O(n^1.3) ~ O(n^2),视增量大小而定。希尔排序的空间复杂度是O(1)，它是一个不稳定的排序算法。

代码实现：

def main():
    nums= [6, 8, 1, 7, 5, 2, 4, 9, 3, 0, -1]

    step = len(nums)//2
    while step != 0:

        for i in range(0, len(nums)):
            for j in range(i, 0, -step):
                if nums[j] < nums[j-step]:
                    nums[j-step], nums[j] = nums[j], nums[j-step]
        step //=2
    print(nums)

运行结果：

[-1, 8, 3, 1, 0, 2, 9, 4, 7, 5, 6]
[-1, 2, 0, 4, 1, 5, 3, 6, 7, 8, 9]
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

我们了解了希尔排序的思想后就很容易明白代码的意思，因为数组的长度是11，我们首先选择以增量5来分组，因此分别对[6,2,-1] [8,4] [1,9] [7,3] [5,0] ,进行插入排序，第一次的排序结果就是运行结果的第一行数据，接下来我么们再将增量减半，以增量2来分组，分别对[-1,1,9,5] [8,0,4,6] [3,2,7] 进行插入排序得到运行结果的第二组数据，然后再将增量减半，以增量1来分组，这时就跟传统的插入排序一样了，希尔排序只不过是通过前面的增量缩减，来使原本无序的序列变得不那么无序，最后还是要通过传统的插入排序将整个序列进行排序。

1.7堆排序

堆排序就像它的名字一样，是在直接选择排序的基础上利用堆的特性进行排序。实现堆的思路是，把数组构建成一棵二叉树，并随着每次堆的变化更新堆顶的最大/最小值。
堆排序的时间复杂度再所有情况下都是O(nlgn)，它是一个不稳定的算法。

代码实现：

nums= [6, 8, 1, 7, 5, 2, 4, 9, 3, 0, 11]
def heapify(start, end):  # 传入的数据是堆顶的节点编号和堆末尾的界限值
    father = start
    son = father*2  # son存储较大的子节点的 编号，初始化为左子节点
    while son < end:  # 当目前所处的节点还有子节点时，继续循环调整
        if son + 1 <= end and nums[son+1] > nums[son]:  # 首先判断是否如果存在右子节点，并且右子节点比左子节点大，那么son的下标就变成右子节点的下标，之后去跟父节点比较
            son += 1
        if nums[father] < nums[son]:  # 如果父节点的值小于子节点
            nums[father], nums[son] = nums[son], nums[father]
            father = son
            son = father * 2
        else:
            return
def heapinit():  # 初始化最大顶堆的函数
    nums.insert(0, 0)  # 首先再下标为0的位置插入元素0，为了便于方便给堆进行标号
    for i in range((len(nums)-1)//2, 0, -1):  # 首先从最底层最右侧的非叶子节点来进行调整
        heapify(i, len(nums)-1)

def heapsort():
    for i in range(len(nums)-1, 0, -1):
        nums[1], nums[i] = nums[i], nums[1]  # 将堆顶元素与堆末尾元素交换
        heapify(1, i-1)  # 随着i的递减，长度也会缩减，达到从数组中将最后一个元素删除的效果，然后在对删除后的序列进行调整，直到遍历到根节点为止。
        print(nums)
if __name__ == "__main__":
    heapinit()
    heapsort()

运行结果：

[0, 9, 8, 4, 7, 5, 2, 1, 6, 3, 0, 11]
[0, 8, 7, 4, 6, 5, 2, 1, 0, 3, 9, 11]
[0, 7, 6, 4, 3, 5, 2, 1, 0, 8, 9, 11]
[0, 6, 5, 4, 3, 0, 2, 1, 7, 8, 9, 11]
[0, 5, 3, 4, 1, 0, 2, 6, 7, 8, 9, 11]
[0, 4, 3, 2, 1, 0, 5, 6, 7, 8, 9, 11]
[0, 3, 0, 2, 1, 4, 5, 6, 7, 8, 9, 11]
[0, 2, 0, 1, 3, 4, 5, 6, 7, 8, 9, 11]
[0, 1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 11]
[0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11]
[0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11]

程序代码首先调用heapinit()函数，将给出的无序数列转换成堆，为了方便给堆进行标号，我们给标号为0的位置插入一个0，这个堆的标号直接就可以 从1开始，首先我们从堆的最底层的最右侧的非叶子节点开始进行调整。在调整函数heapify中，我们把传入的节点定义为父节点，通过公式son = father*2计算出其相应的左子节点，如果存在我们就行下一步，然后我们判断是否存在右子节点，并且判断左右子节点谁大谁小，我们选择子节点中大的数跟父节点进行比较，如果大于父节点，则与父节点进行交换，并且继续向下遍历，直到遍历到叶子节点为止。如果没有则函数什么都不做，然后对下一个非叶子节点进行调整，直到调整到根节点。这样我们就可以把一个无序的序列转换成一个堆了，堆顶元素肯定为最大元素，在heapsort函数中我们把堆顶元素跟末尾元素交换，然后把它从数组末尾割掉，在对割掉之后的序列进行堆调整，调整成为新的堆，再做交换，再割掉，直到数组遍历完成。

1.8桶排序

桶排序的算法思想可以理解为，每个桶装不同范围的数，遍历数组把相应的数放到合适的桶内，然后在对每个桶进行排序，最后按顺序输出这些桶。由于比较简单我们在这就用简单的方式实现它

代码实现：

nums= [8,5,3,11,12,15,32,14,42,45,13,9,21,28,27,325,34,39,25]

list1 = []  #第一个桶，用于存储0-10的数据
list2 = []  #第二个桶，用于存储11-20的数据
list3 = []  #第三个桶，用于存储21-30的数据
list4 = []  #第四个桶，用于存储31-40的数据
list5 = []  #第五个桶，用于存储其他大小的数据

for i in range(len(nums)):
    if nums[i] >=0 and nums[i] <11:
        list1.append(nums[i])
    elif nums[i] >= 11 and nums[i] <21 :
        list2.append(nums[i])
    elif nums[i] >= 21 and nums[i] < 31:
        list3.append(nums[i])
    elif nums[i] >= 31 and nums[i] < 41:
        list4.append(nums[i])
    else:
        list5.append(nums[i])
list1.sort()
list2.sort()
list3.sort()
list4.sort()
list5.sort()
print(list1+list2+list3+list4+list5)

上述代码只是简单的模拟了桶排序的过程，非常明确，我们在这就不详细概述。