内部排序算法总结(时间原因待完善)
2021-07-06 本文已影响0人
愿你我皆是黑马
冒泡
-
原理：当气泡从水底浮上来的时候，由于压强变小气泡就会越来越大。最终在水面是其最大的时候。
冒泡排序算法每次从左到右比较，并判断是否需要交换位置(将大的放在右边)。在一次遍历后最大的数将会在最右边。之后对最大的数之外的数重复该操作。直到所有数都排列好。
-
模版要点：
- 工作一般用不上，面试可能会用到
- for 第j个气泡 in range(0,气泡长度-第i次排序-1): 这里的-1是因为下面的判断会判断j+1，所以这里需要-1
def 冒泡排序(气泡列表): for 第i次排序 in range(0,气泡列表长度): #表示重复该操作第i次 for 第j个气泡 in range(0,气泡长度-第i次排序-1): #表示一次具体的遍历换位 if 气泡列表[第j个气泡] > 气泡列表[第j+1个气泡] : 气泡列表[第j个气泡] (交换) 气泡列表[第j+1个气泡]
选择
-
原理：想象一下，如果你把一堆不一样长度的筷子给一个小孩子让他排好，他会怎样做？ 大概会把最小的找出来放到一边，然后再找最小的放到后面，就这样一直找下去。
选择排序就是按照这种依据：通过一次遍历找到最小的值，将最小的值和第一个数据交换位置。然后重复该步骤。
-
模版要点：
- 最小筷子的下标 = 第i次找：是因为每次找的时候第一眼看到的会觉得最小的，之后再刷新这个认识
- in range(第i次找 + 1, 一堆筷子的个数): 是因为每次找的时候，前i个已经是找出来了的
- if 第i次找 != 最小筷子的下标: 表示实际上最小的不是最开始看到的那第一个
def 选择排序(一堆筷子): for 第i次找 in range(一堆筷子的个数 - 1): 最小筷子的下标 = 第i次找 for 比较的第j根筷子 in range(第i次找 + 1, 一堆筷子的个数): if 一堆筷子[比较的第j根筷子] < 一堆筷子[最小筷子的下标]: 最小筷子的下标 = 比较的第j根筷子 if 第i次找 != 最小筷子的下标: 一堆筷子[第i次找]（交换）一堆筷子[最小筷子的下标]
插入
- 原理：相当于一副扑克牌，将牌一张一张的放到左手。右手的牌插入到左手的时候，从左到右比较牌的大小，将牌插入到正确位置，使得左手的牌始终有序。
- 模版要点：
- 数组传入的是引用，直接赋值某个下标的改变，对所有时刻都生效
- if里面不能break：因为之后要不停的交换位置，才能做到后面的所有数字后移一位
def 插入排序(桌上的牌): for 桌上第i张牌 in range(1,len(桌上的牌)): for 左手第j张牌 in range(0,桌上第i张牌): if 桌上的牌[左手第j张牌]>桌上的牌[桌上第i张牌]: 桌上的牌[左手第j张牌](交换位置)arr[桌上第i张牌]
快排
-
原理：每次取列表中的一个数，将其他数与其比较。小于的放到左边列表、大于的放到右边列表，最后将取出的树放到中间。不停的对左边列表和右边列表做同样的操作。最终得到有序。
要点： -
模版要点：
- pass
递归法模版套路：数据量太大可能导致栈溢出
while循环法模版套路：
希尔排序
指针排序
这是一个特殊场景的排序:将一个有序数组插入到另一个有序数组中。
-
原理：这里使用相当于上面插入排序的。把被插入的数组当作左手的牌，插入的数组当作桌上的牌。
-
模版要点：
- 具体算法做了一个优化：将被插入的牌的容量扩大,每次从最右边插入
def 特殊插入排序之指针排序(左手的有序牌,左手牌的长度,桌上的倒序牌,桌上的倒序牌的长度): 手上最后一张牌的位置 = 左手牌的长度 - 1 手上最右边的位置 = 桌上的倒序牌的长度 + 左手牌的长度 - 1 for 桌上的第i张倒序牌 in range(桌上的倒序牌的长度-1): if 桌上的倒序牌[桌上的第i张倒序牌]>=左手的有序牌[手上最后一张牌的位置]: 左手的有序牌[手上最右边的位置]=桌上的倒序牌[桌上的第i张倒序牌] else: 左手的有序牌[手上最右边的位置]=左手的有序牌[手上最后一张牌的位置] 做插入排序：插入排序初始状态{{{ 左手牌=左手的有序牌[0-手上最后一张牌的位置-1]的范围 插入牌=桌上的倒序牌[桌上的第i张倒序牌] }}} 手上最右边的位置-- };
