一、冒泡排序（Bubble Sort）
基本思想
给定一个数组，我们把数组里的元素通通倒入到水池中，这些元素将通过相互之间的比较，按照大小顺序一个一个地像气泡一样浮出水面。
实现
每一轮，从杂乱无章的数组头部开始，每两个元素比较大小并进行交换，直到这一轮当中最大或最小的元素被放置在数组的尾部，然后不断地重复这个过程，直到所有元素都排好位置。其中，核心操作就是元素相互比较。
代码
class Solution:
def BubbleSort(self, s):
L = len(s)
if L < 2:
return s
else:
for i in range(L-1):
for j in range(1,L-i):
if s[j-1] > s[j]:
s[j-1],s[j] = s[j],s[j-1]
return s
算法分析
空间复杂度
假设数组的元素个数是 n，由于在整个排序的过程中，我们是直接在给定的数组里面进行元素的两两交换，所以空间复杂度是 O(1)。
时间复杂度
- 给定的数组按照顺序已经排好
在这种情况下，我们只需要进行 n−1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。
- 给定的数组按照逆序排列
在这种情况下，我们需要进行 n(n-1)/2 次比较，时间复杂度是 O(n2)。这是最坏的情况。
- 给定的数组杂乱无章
在这种情况下，平均时间复杂度是 O(n2)。
由此可见，冒泡排序的时间复杂度是 O(n2)。它是一种稳定的排序算法。（稳定是指如果数组里两个相等的数，那么排序前后这两个相等的数的相对位置保持不变。）
二、插入排序（Insertion Sort）
基本思想
不断地将尚未排好序的数插入到已经排好序的部分。
实现
在冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的；而对于插入排序来说，经过每一轮的排序处理后，数组前端的数都是排好序的。
代码
class Solution:
def InsertionSort(self, s):
L = len(s)
if L < 2:
return s
else:
for i in range(1,L):
for j in range(i,0,-1):
if s[j] < s[j-1]:
s[j],s[j-1] = s[j-1],s[j]
return s
算法分析
空间复杂度
假设数组的元素个数是 n，由于在整个排序的过程中，是直接在给定的数组里面进行元素的两两交换，空间复杂度是 O(1)。
时间复杂度
- 给定的数组按照顺序已经排好
只需要进行 n-1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。
- 给定的数组按照逆序排列
在这种情况下，我们需要进行 n(n-1)/2 次比较，时间复杂度是 O(n2)。这是最坏的情况。
- 给定的数组杂乱无章
在这种情况下，平均时间复杂度是 O(n2)。
由此可见，和冒泡排序一样，插入排序的时间复杂度是 O(n2)，并且它也是一种稳定的排序算法。
三、归并排序（Merge Sort）
基本思想
核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。
实现
一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。
排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
代码
class Solution:
def MergeSort(self, s):
L = len(s)
if L < 2:
return s
else:
left = self.MergeSort(s[:L // 2])
right = self.MergeSort(s[L // 2:])
res = []
while left or right:
if left and right:
if left[0] > right[0]:
res.append(right[0])
del right[0]
else:
res.append(left[0])
del left[0]
else:
if not left:
left,right = right,left
res.extend(left)
break
return res
if __name__ == "__main__":
a = [8,9,5,7,4,2,1,3,6]
s = Solution()
print(s.MergeSort(a))
算法分析
空间复杂度
由于合并 n 个元素需要分配一个大小为 n 的额外数组，合并完成之后，这个数组的空间就会被释放，所以算法的空间复杂度就是 O(n)。归并排序也是稳定的排序算法。
时间复杂度
归并算法是一个不断递归的过程。
举例：数组的元素个数是 n，时间复杂度是 T(n) 的函数。
解法：把这个规模为 n 的问题分成两个规模分别为 n/2 的子问题，每个子问题的时间复杂度就是 T(n/2)，那么两个子问题的复杂度就是 2×T(n/2)。当两个子问题都得到了解决，即两个子数组都排好了序，需要将它们合并，一共有 n 个元素，每次都要进行最多 n-1 次的比较，所以合并的复杂度是 O(n)。由此我们得到了递归复杂度公式：T(n) = 2×T(n/2) + O(n)。
对于公式求解，不断地把一个规模为 n 的问题分解成规模为 n/2 的问题，一直分解到规模大小为 1。如果 n 等于 2，只需要分一次；如果 n 等于 4，需要分 2 次。这里的次数是按照规模大小的变化分类的。
以此类推，对于规模为 n 的问题，一共要进行 log(n) 层的大小切分。在每一层里，我们都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是 O(n)，所以整体的复杂度就是 O(nlogn)。
四、快速排序
基本思想
快速排序也采用了分治的思想。
实现
把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
举例：把班里的所有同学按照高矮顺序排成一排。
解法：老师先随机地挑选了同学 A，让所有其他同学和 A 比高矮，比 A 矮的都站在 A 的左边，比 A 高的都站在 A 的右边。接下来，老师分别从左边和右边的同学里选择了同学 B 和 C，然后不断地筛选和排列下去。
class Solution:
def QuickSort(self, s):
if len(s) < 2:
return s
else:
mid = s[0]
small = []
large = []
for i in s[1:]:
if i >= mid:
large.append(i)
else:
small.append(i)
return self.QuickSort(small) + [mid] + self.QuickSort(large)
算法分析
空间复杂度
和归并排序不同，快速排序在每次递归的过程中，只需要开辟 O(1) 的存储空间来完成交换操作实现直接对数组的修改，又因为递归次数为 logn，所以它的整体空间复杂度完全取决于压堆栈的次数，因此它的空间复杂度是 O(logn)。
时间复杂度
- 最优情况：被选出来的基准值都是当前子数组的中间数。
这样的分割，能保证对于一个规模大小为 n 的问题，能被均匀分解成两个规模大小为 n/2 的子问题（归并排序也采用了相同的划分方法），时间复杂度就是：T(n) = 2×T(n/2) + O(n)。
把规模大小为 n 的问题分解成 n/2 的两个子问题时，和基准值进行了 n-1 次比较，复杂度就是 O(n)。很显然，在最优情况下，快速排序的复杂度也是 O(nlogn)。
- 最坏情况：基准值选择了子数组里的最大或者最小值
每次都把子数组分成了两个更小的子数组，其中一个的长度为 1，另外一个的长度只比原子数组少 1。
网友评论