O(n^2)

1. 冒泡 (Bubble Sort)
   通过下面这张图我们可以清晰了解到冒泡的原理，通过比较两个相邻的元素，然后进行交换，每一次循环都会选择出一个最大值 / 最小值(取决于你的排序规则)

   
   图片来自于网络，侵删.gif
   

   来段代码提提神

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        index = i
        for j in range(index, n):
            #比较相邻两个元素的大小
            if arr[j] < arr[index]:
                #符合条件进行交换
                arr[j], arr[index] = arr[index], arr[j]

2. 选择 (Selection Sort)
   相较于冒泡，我更喜欢选择排序，每一次遍历数组，都会挑选出最大值 / 最小值并记录它的位置，然后与当前的位置的值进行交换。

   
   图片来自于网络维基百科.gif

一样来段代码提提神

def select_sort(arr):
    n = len(arr)
    for i in range(n):
        index = i
        for j in range(i + 1, n):
            if arr[index] > arr[j]:
                index = j
        arr[i], arr[index] = arr[index], arr[i]

冒泡排序与选择排序之间的区别:
冒泡排序比较相邻元素，然后进行交换
选择排序比较大小记录位置，确定下一个最小/最大者的位置，然后进行交换

3. 插入 (Insertion Sort)
   插入排序: 一个充满意外的O(n^2)算法，在我看来，这里有一跟前两个有很大区别的地方就是，前面说的两种排序，是从前往后遍历的，但是这个插入排序呢，是从后往前遍历的。
   其次插入排序要比前两种都重要的多，当数组内元素基本有序的时候插入排序可以达到O(n)的速度。
   来看一下实现原理，将当前位置的元素，跟之前元素的值进行比较(于是第一个元素，我们就不需要遍历了)，如果比之前的小/大，则将这个元素向后移动，直到找到了该元素的合适位置，将其放在那个位置(可以看一下下图中的7移动轨迹)。
   我们需要注意下图中一个细节，当前元素并不是与之前元素交换，而是取出，之前元素后移。当找到合适位置时，再将其赋值放入。
   图片来自于网络维基百科.gif

提神时间

def insert_sort(arr):
    n = len(arr)
    #这里只需要从1,n 而不是 0,n
    for i in range(1, n):
        temp = arr[i]
        j = i - 1  
       #由于可能会提前结束，我们使用while更加方便
        while temp < arr[j] and j >= 0:
            arr[j+1] = arr[j]
            j -= 1
        #因为多-1 所以 在赋值的时候需要 +1
        arr[j+1] = temp

4. 希尔 (Shell Sort)
   说到shell就厉害了，这是插入排序的进化版，厉害到了我没找到gif图片，只找到了一个关于他的视频，观看这个视频要注意右上角有个gap值得变化。
   首先要注意的是这个是插入排序的进化，所以他也是从后往前遍历。shell中有个很关键的值就是gap，每次都只遍历gap之后的值，然后在于这个元素位置相距gap的前面的值进行比较(这里是一个插入排序，只不过这里j-=1变成了j-=gap)，一次大的循环完成后在改变gap的值，gap一般变化为 gap = n // m(m 自定义 2，3，4都可以)
   直接代码了

def shell_sort(arr):
    n = len(arr)
    gap = n // 3
    while gap > 0:
        for i in range(gap, n):
            j = i
            temp = arr[i]
            while temp < arr[j - gap] and j >= gap:
                arr[j] = arr[j - gap]
                j -= gap
            #题外:这里的插入写法与上面的插入写法有一些区别
            arr[j] = temp
        gap = gap // 2

这些代码我都参考了维基，也可以直接去维基看。