一、冒泡排序
冒泡排序（Bubble Sort）：从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续重复这个过程，直到所有数据元素都排好序。
菜鸟教程：https://www.runoob.com/w3cnote/bubble-sort.html
1. 算法步骤（假设从小到大排序）
整个过程可以分为2层循环，外循环表示从下标0开始遍历至下标len-2，内循环表示
1）比较相邻的2个元素。如果第1个比第2个大，就交换他们两个位置。 —— 这样较大的元素就往右移动
2）对每一对相邻元素重复步骤①，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3）排除最大的数，针对其他所有的元素重复以上的步骤①②，确定第二大的数……
4）持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。
外层循环：第0次、第1次、第n次循环
内层循环：a[0]和a[1]比较、a[1]和a[2]比较 ... a[n-i-2]和a[n-i-1]比较
示例：将数组 num=[3, 6, 4, 2, 11, 10, 5] 从小到大排序
def bubbleSort(num):
n = len(num)
# 外层循环：表示一共要比较n-1趟，每1趟将最大的数放在无序数组的队尾，即第i趟将第i大的元素放在num[-i]的位置
for i in range(0, n-1, 1):
# 内层循环：表示从第0个元素到第n-i-1个元素，每2个相邻元素比较大小
for j in range(0, n-1-i, 1):
if num[j] > num[j+1]:
num[j], num[j+1] = num[j+1], num[j]
return num
num = [3, 6, 4, 2, 11, 10, 5]
print(bubbleSort(num)) # [2, 3, 4, 5, 6, 10, 11]
2. 优化算法
设置一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序，无须再遍历比较。
n = len(num)
# 外层循环：表示一共要比较n-1趟，每1趟将最大的数放在无序数组的队尾，即第i趟将第i大的元素放在num[-i]的位置
for i in range(0, n-1, 1):
# 标志第i趟循环中，是否有元素交换位置
flag = False
# 内层循环：表示从第0个元素到第n-i-1个元素，每2个相邻元素比较大小
for j in range(0, n-1-i, 1):
if num[j] > num[j+1]:
num[j], num[j+1] = num[j+1], num[j]
# 如果有元素交换位置，则将flag置为true
flag = True
# 如果没有元素交换位置，说明数组已经有序，不用再比较
if not flag:
break
return num
num = [3, 6, 4, 2, 11, 10, 5]
print(bubbleSort(num)) # [2, 3, 4, 5, 6, 10, 11]
3. 时间复杂度
最坏情况O(n²)：当列表完全逆序时，则每次都要比较(n-1)+(n-2)+...+1 = n(n-1)/2
最好情况O(n)：当列表完全正序时，则只需冒泡比较1趟，即n-1次比较
平均时间复杂度O(n²)：外层循环*内层循环
二、计数排序
1. 计数排序的特征
1）计数排序要求输入的数据必须是有确定范围的整数。
2）当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。
3）计数排序不是比较排序，排序的速度快于任何比较排序算法。
4）用来计数的数组C的长度取决于待排序数组中数据的范围（等于数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
菜鸟教程：https://www.runoob.com/w3cnote/counting-sort.html
2. 算法步骤
（1）找出待排序的数组中最大和最小的元素，初始化数组C的长度为最大值与最小值的差加上1
（2）统计数组中每个值为 i 的元素出现的次数，存入数组C的第 i 项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素 i 放在新数组的第C(i)项，每放一个元素就将C(i)+1
示例：将数组 num=[3, 2, 4, 2, 3, 10, 4] 从小到大排序，数组中每个元素num[i]<=10
def countSort(num, maxValue):
# count[i]表示i出现的次数
count = [0]*(maxValue+1)
# 统计num中每个元素出现的次数
for i in num:
count[i] += 1
cnt = 0
# 遍历count数组，从而反向填充目标数组
for i in range(maxValue+1):
# 如果i出现的次数不为0，则将num[cnt, cnt+count[i]]设置为i
if count[i] != 0:
for k in range(cnt, cnt+count[i], 1):
num[k] = i
cnt += count[i]
return num
num = [3, 2, 4, 2, 3, 10, 4]
print(countSort(num, 10)) # [2, 2, 3, 3, 4, 4, 10]
3. 时间复杂度
计数排序是通过空间换时间，使得时间复杂度能够达到线性 O(n+k)，且是稳定的排序算法
练习： 力扣1051题
# 学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
# 排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
# 给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
# 返回满足 heights[i] != expected[i] 的 下标数量 。
#
# 示例：
# 输入：heights = [1,1,4,2,1,3]
# 输出：3
# 解释：高度：[1,1,4,2,1,3]
# 预期：[1,1,1,2,3,4]
# 下标 2 、4 、5 处的学生高度不匹配。
class Solution:
def heightChecker(self, heights) -> int:
# count[i]表示身高为i的人数为count[i]
count = [0] * 101
for x in heights:
count[x] += 1
ans = 0
# i指向count的下标，j指向heights的下标
i, j = 0, 0
# 比较heights每个位置的身高是否与计数顺序一致
while i < 101 and j < len(heights):
while count[i] > 0:
if heights[j] != i:
ans += 1
count[i] -= 1
j += 1
i += 1
return ans
heights = [1,1,4,2,1,3]
print(Solution().heightChecker(heights))
三、快速排序
1. 快排的基本思想
快速排序的核心思想是分治：选择数组中的某个数作为基数，将数组中比基数小的数字放到它的左边，比基数大的数字放到它的右边，此时数组被划分为左两个分区；再按照此方法对这两个分区执行快速排序，一直递归，直到整个数组变得有序
菜鸟教程：https://www.runoob.com/w3cnote/quick-sort-2.html
2. 快排的原理
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
1）从数组中选择一个元素作为基数（pivot）—— 一般选择第 1 个元素
2）遍历数组中的每个数并与基数pivot比较，所有比基数小的元素放在基数的左边，所有比基数大的元素摆在基数的右边。这时，左右两个分区的元素就相对有序了，而基数就处于数组的中间位置，这个称为分区（partition）操作
3）递归地（recursively）把这两个分区分别按照上面步骤继续对每个分区找出基数，然后移动，
递归直到各个分区只有一个数时为止，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
3. 示例
以 [47, 29, 71, 99, 78, 19, 24, 47] 的待排序的数列为例进行排序，为了方便区分两个 47，我们对后面的 47 增加一个下画线，即待排序的数列为[47, 29, 71, 99, 78, 19, 24, 47] 。
方法一：
1）取第一个数nums[left]=47 为基准值，初始下标记为pivot=left
2）index为最终基准值的位置下标，index左边的数均小于基准值47，即表示数组中小于基准值的个数为index
3）指针 i 从左往右遍历数组，如nums[i]小于基准值，则index+1，然后将nums[i]放在index位置，即与nums[index]交换位置
4）如果nums[i]大于基准值，则不动
5）遍历结束后，由于基准值一直在队首left位置没动，因此将nums[left]和nums[index]交换，使得index左边的数均小于基准值，右边的数均大于基准值
# 快排
# 递归调用分区函数
def quickSort(nums, left, right):
if left < right:
# 先分区，得到两个子分区
partitionIndex = partition(nums, left, right)
# 对两个子分区递归
quickSort(nums, left, partitionIndex-1)
quickSort(nums, partitionIndex+1, right)
return nums
# 分区函数
# 对数组nums[left:right]进行分区，返回下标index，使得nums[left:index]<nums[index]<=nums[index:right]
def partition(nums, left, right):
pivot = left # pivot记录当前基准值的位置，基准值在循环比较过程中不移动
index = left # index表示基准值最终的位置下标，每有一个数小于pivot时，下标index往右移动+1
i = left + 1 # 指针i从左往右遍历数组nums
while i <= right:
# 如果当前数nums[i]小于基准值，则基准值下标index+1，并将nums[i]放置左分区index的位置
if nums[i] < nums[pivot]:
index += 1
nums[i], nums[index] = nums[index], nums[i]
# i+1继续遍历下一个
i += 1
# 遍历结束后，将基准值放在index的位置
nums[pivot], nums[index] = nums[index], nums[pivot]
return index
nums = [47, 29, 71, 99, 78, 19, 24, 47]
print(quickSort(nums, 0, 7)) # 输出：[19, 24, 29, 47, 47, 71, 78, 99]
方法二
1）取数组第一个元素为基准值pivot，并定义两个指针i=len(nums)-1、j=0
2）指针 i 从右往左遍历，如果nums[i]>=pivot，不动，i--遍历下一个元素；
如果nums[i]<pivot，则与基准值num[j]交换，j++，交换后nums[i]则为基准值；
3）指针 j 从左往右遍历，如果nums[j]<pivot，不动，j++遍历下一个元素；
如果nums[j]>=pivot，则与基准值num[i]交换，交换后nums[j]则为基准值；
4）重复上述寻找，直到 i = j (表明所有数都和pivot比较过)，最后基准值所在的位置k，此时 k 左边的值均比基准值小， k 右边的值都比基准值大。
5）对第4步得到的两个分区分别再进行步骤1~4
进行第 1 趟第 1 个交换的排序情况如下，第 1 次的操作情况如图1 所示。
交换之后，i 移动到了下标为 6 的位置，对 i 继续扫描，如图 2 所示。
此时交换后的数列变为 24、29、47、99、78、19、71、47。接下来我们继续对 i、j 进行操作，如图 3 所示，继续进行 i-- 及 j++ 的比较操作。
进行了这两次 i、j 的移动、比较、交换之后，我们最终得到的数列是 24、29、19、47、78、99、71、47。接下来我们继续进行 i-- 的操作，发现在 i 为 4 时比 47 大不用交换，在 i 为 3 时与 j 相遇，这时就不需要继续移动、比较了，已经找到 k 了，并且 k 的值为 3。
47 这个值已经落到了它该在的位置，第 1 趟排序完成了。接下来就是以 k 为基准，分为两部分，然后在左右两部分分别执行上述排序操作，最后数据会分为 4 部分；接着对每部分进行操作，直到每部分都只有一个值为止。
# 快排
# 递归调用分区函数
def quickSort(nums, left, right):
if left < right:
# 先分区，得到两个子分区
partitionIndex = partition(nums, left, right)
# 对两个子分区递归
quickSort(nums, left, partitionIndex-1)
quickSort(nums, partitionIndex+1, right)
return nums
# 对数组nums[left:right]进行分区，返回下标index，使得下标index左边的数均小于index右边的数，即nums[left:index]<nums[index]<=nums[index:right]
def partition(nums, left, right):
pivot = nums[left] # pivot记录当前基准值
i, j = right, left # 指针i从右往左遍历数组，指针j从左往右遍历数组
while j < i:
# i从右往左遍历数组
# 1）如果nums[i]大于基准值，不动，i--继续遍历下一个元素
while i > j and nums[i] >= pivot:
i -= 1
# 2）如果nums[i]小于基准值，则将nums[i]与基准值交换
if i > j:
nums[i], nums[j] = nums[j], nums[i]
j += 1
# j从左往右遍历数组
# 1）如果nums[j]小于基准值，不动，j++继续遍历下一个元素
while i > j and nums[j] < pivot:
j += 1
# 2）如果nums[j]小于基准值，则将nums[j]与基准值交换
if i > j:
nums[i], nums[j] = nums[j], nums[i]
return i
nums = [47, 29, 71, 99, 78, 19, 24, 47]
print(quickSort(nums, 0, 7)) # 输出：[19, 24, 29, 47, 47, 71, 78, 99]
总结
快排核心就是递归。对于每一趟排序都是一样的思想，只不过需要进行排序的数组的范围越来越小了
时间复杂度：
快速排序在最坏情况下的时间复杂度是O(n^2)，实际上每次比较都需要交换，但是这种情况并不常见。平均时间复杂度是 O(nlogn)，快排算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来。
空间复杂度：
快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的空间复杂度为 O(logn)，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O(n)。所以我们一般认为快速排序的空间复杂度为 O(logn)。
稳定性：
快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变。
快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。
练习
四、选择排序
原理
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
算法步骤
1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3）重复步骤2，直至所有元素排序完成
示例
待排序数组 nums = [1, 8, 7, 3, 5, 4]
# 选择排序
def selectSort(nums):
n = len(nums)
# 进行n-1次循环，每次从从剩余待排序数组中选择最小的数
for i in range(1, n):
# 最小的数的下标记为minIndex
minIndex = i
for j in range(i+1, n):
# 如果比nums[minIndex]，则更新minIndex
if nums[j] < nums[minIndex]:
minIndex = j
# 将最小的数已排序数组的末尾
nums[i], nums[minIndex] = nums[minIndex], nums[i]
return nums
nums = [1, 8, 7, 3, 5, 4]
print(selectSort(nums)) # [1, 3, 4, 5, 7, 8]
五、插入排序
原理
1）将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
算法步骤
1）将第一个元素看做一个有序序列 sortedList 只包含nums[0]
2）从头到尾依次遍历未排序序列nums[i]，并将nums[i]插入有序序列的适当位置
i）如果nums[i] < 已排序元素，将此已排序元素右移一位，nums[i]继续与前面元素比较
ii）如果nums[i] >= 已排序元素，直接将nums[i]插入到该位置后
重复步骤上述2~4
时间复杂度
最坏情况O(n²)：当列表完全逆序时，则每次都要比较前面所有数1+2+...+(n-2)+(n-1)= n(n-1)/2
最好情况O(n)：当列表完全正序时，则每趟只需比较1次，即n-1趟*1次
# 插入排序
def insertSort(nums):
# nums[0]为单独有序数列，从nums[1]开始插入
for i in range(1, len(nums)):
# 有序数组的末尾下标
preIndex = i-1
current = nums[i]
# 在有序数组nums[:i]中插入nums[i]
while preIndex >= 0 and current < nums[preIndex]:
nums[preIndex+1] = nums[preIndex]
preIndex -= 1
nums[preIndex+1] = current
return nums
nums = [9, 8, 7, 6, 5, 4, 3]
print("插入排序后的数组:", insertSort(nums)) # [3, 4, 5, 6, 7, 8, 9]
nums = [1, 8, 7, 3, 5, 4]
print("插入排序后的数组:", insertSort(nums)) # [1, 3, 4, 5, 7, 8]
# 插入排序
def insertSort(nums):
n = len(nums)
# 遍历待排序数组=nums[1:n]，从arr[1]开始插入，arr[0]为单独有序数列
for i in range(1, n):
key = nums[i]
# 在有序数组nums[:i]中插入nums[i]即key
for j in range(i-1, -1, -1):
# 如果key < 已排序元素，将此已排序元素右移一位，nums[i]继续与前面元素比较
if key < nums[j]:
nums[j+1] = nums[j]
nums[j] = key
# 如果nums[i] >= 已排序元素，直接将nums[i]插入到该位置后
else:
break
return nums
nums = [9, 8, 7, 6, 5, 4, 3]
print("插入排序后的数组:", insertSort(nums)) # [3, 4, 5, 6, 7, 8, 9]
nums = [1, 8, 7, 3, 5, 4]
print("插入排序后的数组:", insertSort(nums)) # [1, 3, 4, 5, 7, 8]
六、二分查找
二分查找是在有序数组中查找某一特定元素的搜索算法。
原理
查找过程
1）从数组的中间元素开始，如果中间元素 = X，则搜索过程结束；
2）如果中间元素 > X，则在数组左半边查找；
3）如果中间元素 < X，则在数组右半边查找；
4）重复1～3步骤，如果在某一步骤数组为空，则代表找不到，返回-1
这种搜索算法每一次比较都使搜索范围缩小一半
时间复杂度：O(logn)
# 返回 x 在 nums[start,end] 中的索引，如果不存在返回 -1
# 方法一：循环
def binarySearch(nums, x):
start, end = 0, len(nums)-1
while start <= end:
mid = (start+end)//2
# 元素正好在中间位置
if x == nums[mid]:
return mid
# 元素小于中间位置的元素，只需要再比较左边的元素
elif x > nums[mid]:
start = mid + 1
# 元素大于中间位置的元素，只需要再比较右边的元素
else:
end = mid - 1
return -1
# 方法二：递归分治
def binarySearch(nums, start, end, x):
if end >= start:
mid = int(start + (end - start) / 2)
# 元素正好在中间位置
if nums[mid] == x: return mid
# 元素小于中间位置的元素，只需要再比较左边的元素
elif nums[mid] > x:
return binarySearch(nums, start, mid - 1, x)
# 元素大于中间位置的元素，只需要再比较右边的元素
else:
return binarySearch(nums, mid + 1, end, x)
else:
# 不存在
return -1
# 测试数组
nums = [2, 3, 4, 10, 40]
x = 10
print(binarySearch(nums, 0, 4, 10))
练习1
# 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
left, right = 0, n
while left <= right:
mid = (left+right)//2
if isBadVersion(mid):
left = mid + 1
else:
right = mid
return left
练习2
x=5，nums=[1, 2, 4, 5, 5, 5, 7, 9, 10]，查找x在nums中第一次出现的位置
# 先用二分法找到x在nums中的位置，然后再往数组左边遍历找到第一次出现x的位置
def binarySearch(nums, x):
left, right = 0, len(nums)
while left <= right:
mid = (left+right)//2
# 找到x，再往左遍历找到第一次出现x的位置
if x == nums[mid]:
while mid >= 0:
if nums[mid] == x:
mid -= 1
else:
break
return mid+1
elif x > nums[mid]:
left = mid + 1
else:
right = mid - 1
nums = [1, 2, 4, 5, 5, 5, 7, 9, 10]
x = 5
print(binarySearch(nums, x))
七、线性查找
原理
从数组开始每个元素依次比较
时间复杂度：O(n)
def search(nums, x):
for i in range(len(nums)-1):
if x == nums[i]:
return i
return -1
# 测试数组
nums = [2, 3, 10, 40]
x = 10
print(search(nums, x))
