1. 简单插入排序

1)算法原理

2)可视化

3)代码实现

2. 希尔排序

1)算法原理

希尔排序是插入排序的高效实现，对简单插入排序减少移动次数优化而来。

简单插入排序每次插入都要移动大量数据，前后插入时的许多移动都是重复操作，若一步到位移动效率会高很多。

若序列基本有序，简单插入排序不必做很多移动操作，效率很高。

希尔排序将序列按固定间隔划分为多个子序列，在子序列中简单插入排序，先做远距离移动使序列基本有序；逐渐缩小间隔重复操作，最后间隔为1时即简单插入排序。

希尔排序对序列划分O(n)次，每次简单插入排序O(logn)，时间复杂度O(nlogn)

额外空间开销出在插入过程数据移动需要的一个暂存，空间复杂度O(1)

2)可视化

https://www.icode9.com/i/ll/?i=20200204161632429.gif

3)代码实现

def ShellSort(ls):
    def shellinsert(arr,d):
        n=len(arr)
        for i in range(d,n):
            j=i-d
            temp=arr[i]             #记录要出入的数
            while(j>=0 and arr[j]>temp):    #从后向前，找打比其小的数的位置
                arr[j+d]=arr[j]                 #向后挪动
                j-=d
            if j!=i-d:
                arr[j+d]=temp
    n=len(ls)
    if n<=1:
        return ls
    d=n//2
    while d>=1:
        shellinsert(ls,d)
        d=d//2
    return ls
 
 
x=input("请输入待排序数列：\n")
y=x.split()
arr=[]
for i in  y:
    arr.append(int(i))
arr=ShellSort(arr)
#print(arr)
print("数列按序排列如下：")
for i in arr:
    print(i,end=' ') 

3. 简单选择排序

1)原理

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

2)可视化

3)代码实现

###方法一：
arr=[23,41,25,54,18,14]
pos=0
for i in range(len(arr)):
    ls=arr[pos::]
    Max=max(ls)
    tmp=arr.index(Max)
    arr[pos],arr[tmp]=arr[tmp],arr[pos]
    pos+=1
print(arr)

4. 快速排序

1)算法原理

• 选定Pivot中心轴
• 将大于Pivot的数字放到Pivot的右边
• 将小于Pivot的数字放到Pivot的右边
• 分别对左右子序列重复以上三部，直到序列长度为一的时候完成快排

2)可视化

https://www.bilibili.com/video/BV1at411T75o/?spm_id_from=autoNext

3)代码实现

#######方法一
def QuikSort(arr,L,R):
    l=L
    r=R
    tmp = arr[l]
    if l>=r:
        return arr
    while l<r:
        while l<r and arr[r]>= tmp:
            r-=1
        while arr[r]< tmp:
            arr[l], arr[r] = arr[r], arr[l]
            l+=1
            while arr[l]< tmp:
                l+=1
            while arr[l]> tmp:
                arr[l], arr[r] = arr[r], arr[l]
                r-=1
    QuikSort(arr,L,l-1)
    QuikSort(arr,l+1,len(arr)-1)
    return arr
arr=[6,1,2,7,9,3,4,5,10,8]
res=QuikSort(arr,0,len(arr)-1)
print(res)    
#####方法二
def quick_sort(alist, start, end):
    """快速排序算法的实现"""
 
    # 递归的退出条件
    if start >= end:
        return
    # 设定起始元素为要寻找位置的基准元素
    mid = alist[start]
    # low为序列左边的由左向右移动的游标
    low = start
    # high为序列右边的由右向左移动的游标
    high = end
 
    while low < high:
        # 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
        while low < high and alist[high] >= mid:
            high -= 1
        # 将high指向的元素放到low的位置上
        alist[low] = alist[high]
 
        # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
        while low < high and alist[low] < mid:
            low += 1
        # 将low指向的元素放到high的位置上
        alist[high] = alist[low]
 
    # 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
    # 将基准元素放到该位置
    alist[low] = mid
    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low-1)  # 递归调用！
    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low+1, end)  # 递归调用！
 
 
if __name__ == "__main__":
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20, 100, 77]
    print(alist)
    quick_sort(alist, 0, len(alist)-1)
    print(alist)

5. 冒泡排序

1)算法原理

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

2)可视化

https://www.bilibili.com/video/BV1oA411i7HC?from=search&seid=6654424292689255239

3)代码实现

def BubbleSort(ls):
    n=len(ls)
    if n<=1:
        return ls
    for j in range (n,0,-1):
        for i in range(j):
            if ls[i]>ls[i+1]:
                ls[i],ls[i+1] = ls[i+1],ls[i]
    return ls
x=input("请输入待排序数列：\n")
y=x.split()
arr=[]
for i in  y:
    arr.append(int(i))
arr=BubbleSort(arr)
#print(arr)
print("数列按序排列如下：")
for i in arr:
    print(i,end=' ')

6. 堆排序

1)定义

堆排序基于比较交换，是冒泡排序的优化。具体涉及大（小）顶堆的建立与调整。

大顶堆指任意一个父节点都不小于左右两个孩子节点的完全二叉树，根节点最大。

堆排序首先建立大顶堆（找出一个最大值），然后用最后一个叶子结点代替根节点后做大顶堆的调整（再找一个最大值），重复

以数组（列表）实现大顶堆时，从上到下，从左到右编号。父节点序号为n，则左右孩子节点序号分别为2n+1、2n+2

大顶堆的调整：将仅有根节点不满足条件的完全二叉树，调整为大顶堆的过程。

大顶堆调整方法：将根节点与较大一个儿子节点比较，不满足条件则交换。

                        若发生交换，将被交换儿子节点视作根节点重复上一步

大顶堆的建立：从最后一个非叶子节点开始到根节点结束的一系列大顶堆调整过程。

堆排序的初始建堆过程比价复杂，对O(n)级别个非叶子节点进行堆调整操作O(logn)，时间复杂度O(nlogn)；之后每一次堆调整操作确定一个数的次序，时间复杂度O(nlogn)。合起来时间复杂度O(nlogn)

2)动画演示视频

https://www.bilibili.com/video/av710200011/

3)代码实现

def  HeapSort(ls):
    def heapadjust(arr,start,end):  #将以start为根节点的堆调整为大顶堆
        temp=arr[start]
        son=2*start+1
        while son<=end:
            if son<end and arr[son]<arr[son+1]:  #找出左右孩子节点较大的
                son+=1
            if temp>=arr[son]:       #判断是否为大顶堆
                break
            arr[start]=arr[son]     #子节点上移
            start=son                     #继续向下比较
            son=2*son+1
        arr[start]=temp             #将原堆顶插入正确位置
#######
    n=len(ls)
    if n<=1:
        return ls
    #建立大顶堆
    root=n//2-1    #最后一个非叶节点（完全二叉树中）
    while(root>=0):
        heapadjust(ls,root,n-1)
        root-=1
    #掐掉堆顶后调整堆
    i=n-1
    while(i>=0):
        (ls[0],ls[i])=(ls[i],ls[0])  #将大顶堆堆顶数放到最后
        heapadjust(ls,0,i-1)    #调整剩余数组成的堆
        i-=1
    return ls
#########
x=input("请输入待排序数列：\n")
y=x.split()
arr=[]
for i in  y:
    arr.append(int(i))
arr=HeapSort(arr)
#print(arr)
print("数列按序排列如下：")
for i in arr:
    print(i,end=' ') 

7. 归并排序

1)定义

2)动画演示讲解

https://www.bilibili.com/video/BV1ZW411q7vG?from=search&seid=9791204927634317149

3)代码实现

def MergeSort(array):
    n = len(array)
    if n <= 1:
        return array
    m = n//2
    L = MergeSort(array[:m])
    R = MergeSort(array[m:])

    i,j =0,0
    res=[]
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            res.append(L[i])
            i += 1
        else:
            res.append(R[j])
            j += 1

    res += L[i:]
    res += R[j:]
    return res



arr=[23,41,25,54,18,14]
n=len(arr)
ans = MergeSort(arr)
print(ans)

8. 桶排序

1）算法原理

2)可视化

3)代码实现

参考文献：

• https://blog.csdn.net/aiya_aiya_/article/details/79846380
• https://blog.csdn.net/u013719780/article/details/49201143/

项目：数据集的大小
测试接口
图像处理方法
python用到的经常库函数
多线程，及用到的库函数
算法：归并排序
数据库查询语句
操作系统
linx 指令
计算机网络；三次握手