脑图

排序算法

稳定性，简单解释就是两个相同的值经过算法后是否依旧能保持前面的在前面，后面的在后面

1.冒泡排序

1.1步骤

1.比较第一个与第二个，如果前者大则交换位置
2.推进，即比较第二个和第三个
3.重复上述步骤

这个数据就如同气泡一样，将大的往后移，小的往前推。用冒泡排序命名可以说是很形象了

1.2python代码实现冒泡：

# 冒泡排序
def bubbles_sort(arr):# 循环列表长度for i in range(1, len(arr)):# 对于每一个arr[j]与后一个arr[j+1]进行对比for j in range(0, len(arr)-i):# 比较if arr[j] > arr[j+1]:# 前者大则交换两者位置arr[j], arr[j + 1] = arr[j + 1], arr[j]return arrbubbles_sort([5,4,3,2,1])

1.3分析冒泡

时间复杂度：最坏情况：O(N**2)
      最好情况：O(N)
空间复杂度：O(1)
稳定

2.插入排序

2.1步骤

1.将数组分为两个部分已经排序和未排序（初始认为第一个已经排序，后面的为未排序）
2.取未排序的第一个，与已排序的进行对比，并加入进已经排序的数组
3.重复第二步，直至未排序的为空

这个方式就如同打牌时摸牌一样，将牌堆中抽上来的牌与手牌进行对比，再决定插入哪个地方,最后继续抽牌。

2.2python代码实现插入排序：

# 插入排序
def insertion_sort(arr):for i in range(1, len(arr)):# 取值（抽牌）key = arr[i]j = i-1# 选择插入位置while j >= 0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = keyreturn arr
insertion_sort([5,4,3,2,1])

2.3分析插入

时间复杂度：最坏情况下为O(N**2)，此时待排序列为逆序，或者说接近逆序
      最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)
稳定

3.选择排序

3.1步骤

1.将数组分为两个部分已经排序和未排序（初始全部为未排序），
2.寻找未排序中的最小的值，并且与未排序中的第一个交换位置
3.重复2，直到未排序全部有序

可以发现，其中就是寻找最小值，放入有序的过程

3.2python代码实现：

# 选择排序
def select_sort(arr):# 循环寻找最小值for i in range(len(arr)):min_index=0min=arr[i]for j in range (i+1,len(arr)):if arr[j]<min:min=arr[j]min_index=j# 如果位置不同则交换位置if min!=arr[i]:arr[i],arr[min_index]=arr[min_index],arr[i]return arrarr = [23, 25, 12, 22, 11]
sorted_arr = select_sort(arr)

3.3分析选择

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N^2)
空间复杂度：O(1)
不稳定
事实上我们也可以同时选出最大最小值放入两边

4.快速排序

这个有两种方法（其实都是一种思路，不同的实现方式）

4.1步骤

方法1
1.令第一个数据为基准，并且利用两个指针l和r指向队首和队尾（如果只有一个数据则返回自己）
2.将r的数据与基准进行对比，如果大于基准则指向上一个数据，如果小于则与l进行交换
3.将l的数据与基准进行对比，如何小于基准则指向下一个数据，如果大于则与r进行交换
4.重复2和3，知道rhel指向同一个位置，这个位置就是基准的位置（此时左边的数全部小于基准，右边的数全部大于基准）
5.将左右两边的数列重复上述和此步骤，直到结束。

对于python，我们还有另一种方法

方法2
1.令第一个数据为基准（如果只有一个数据则返回自己）
2.利用列表推导式，直接选出所有小于基准，等于基准，大于基准的数
3.将小于基准的，大于基准的重复上述和此步骤，直到全部返回

快速排序主要是选择基准，将左边全部为小的，右边全部为大的，从而进行对比，并且利用了递归的思想，将两边重复从而实现有序

4.2python代码实现：

方法1：

def quick(arr):# 如果只有一个则无需排序if len(arr) <= 1:return arr# 选择基准base=arr[0]l=0r=len(arr)-1# 比较，交换数据while l<r:while l<r and arr[l]<base:l+=1while l<r and arr[r]>base:r-=1arr[l],arr[r]=arr[r],arr[l]# 将l和r重复时候的位置填入基准值arr[l],arr[0]=arr[0],arr[l]# 将左右递归return quick(arr[:l])+[arr[l]]+quick(arr[l+1:])
quick_sort([5,4,3,2,1])

方法2：

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[0]  # 选择小于基准的left = [x for x in arr if x < pivot]# 选择等于基准的middle = [x for x in arr if x == pivot]# 选择大于基准的right = [x for x in arr if x > pivot]# 递归return quick_sort(left) + middle + quick_sort(right)
quick_sort([5,4,3,2,1])

其实都是一个逻辑，将小的放左边，大的放右边

4.3分析快排

时间复杂度在最坏情况下是O(n^2)
平均情况O(n log n)
空间复杂度最坏情况下为O(n)
在平均情况下，是O(log n)。

5.希尔排序

5.1步骤

1.按照步长分组，并且将这组通过插入变为有序
2. 减小步长，重复步骤1
3. 直到步长变为1，数组有序

5.2python代码实现：

def shell_sort(arr):n = len(arr)gap = n // 2# 减小间隔进行排序while gap > 0:for i in range(gap, n):temp = arr[i]j = i# 插入排序while j >= gap and arr[j - gap] > temp:arr[j] = arr[j - gap]j -= gaparr[j] = tempgap //= 2# 测试希尔排序
arr = [12, 34, 54, 2,6, 3,1]
shell_sort(arr)
print("排序后的数组:", arr)

5.3分析

时间复杂度平均：O(N^1.3)
空间复杂度：O(1)
不稳定

6.归并排序

6.1步骤

1.分而治之，将一个数组按两个为一组进行分组，并让其有序
2.将两个有序数组之间两两组合，直到和为原来长度的大组

6.3python代码实现：

def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2  # 找到中间位置L = arr[:mid]  # 分割数组为两部分R = arr[mid:]merge_sort(L)  # 对左半部分进行排序merge_sort(R)  # 对右半部分进行排序i = j = k = 0# 合并过程while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1# 检查是否有剩余元素while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print( arr)

6.4分析

平均时间复杂度：O(nlogn)
最佳时间复杂度：O(n)
最差时间复杂度：O(nlogn)
空间复杂度：O(n)
排序方式：In-place
稳定性：稳定