默认从小到大排序，以这样的既定规则去分析排序算法


冒泡排序

每次循环将次大的数选出来，排好
原理：

  1. 比较每对相邻的元素，如果顺序错误，交换它们；
  2. 每次循环将最大的元素放到末端合适位置；
  3. 重复列表直到不需要交换，表明已被排序

属性：

  • O(1)的额外空间
  • O(n^2)的比较和交换
  • 稳定（因为相邻两个元素如果相同，不需要进行交换位置，因此相同元素的相对位置不会改变）

代码:

  1. def _bubble_sort(nums:list, reverse=False):
  2.     length = len(nums)
  3.     for i in range(length):
  4.         is_sorted = True # 如果没有交换过，说明已经排序好
  5.         for j in range(length - i - 1):
  6.             if nums[j] > nums[j+1]:
  7.                 nums[j], nums[j+1] = nums[j+1], nums[j]
  8.                 is_sorted = False
  9.         if (is_sorted):break
  10.     if reverse:
  11.         nums.reverse()
  12.     return nums

选择排序

每次选择次小放在已排序的末端
原理：

  1. 在未排序的序列中找到最大的元素，存放到序列末端（已排序的序列起士位置）；
  2. 在未排序的序列中，找到最大的元素，放到已排序序列起始位置；
  3. 重复第2步，所有序列都已排序

image.gif
属性：

  • O(1)的额外空间
  • O(n^2)对比，O(n)的交换
  • 不稳定

（举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。）
代码：

  1. 找到最小的点，放在序列首端
  2. 在剩下未排序的元素中，找到次小的点，接在后面
  3. 继续这样做，直至所有元素排序完成
  1. class Solution:
  2.     def sortArray(self, nums: List[int]) -> List[int]:
  3.         # selection sort
  4.         length = len(nums)
  5.         for i in range(length):
  6.             pos_min = i
  7.             for j in range(i + 1, length):
  8.                 if nums[j] < nums[pos_min]:
  9.                     pos_min = j
  10.             nums[i], nums[pos_min] = nums[pos_min], nums[i]
  12.         return nums

插入排序

插入到已排序的序列中
原理：

  1. 从第一个元素开始，该元素认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一个位置
  4. 重复步骤3，找到新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

image.gif
属性：

  • 时间复杂度O(n^2)
  • 额外空间O(n)
  • 稳定的

代码:

  1. class Solution:
  2.     def sortArray(self, nums: List[int]) -> List[int]:
  3.         # insert sort
  4.         length = len(nums)
  5.         for i in range(1, length):
  6.             for j in range(i, 0, -1):
  7.                 if nums[j] < nums[j - 1]:
  8.                     nums[j], nums[j - 1] = nums[j - 1], nums[ j]
  9.                 else:
  10.                     break
  11.         return nums

希尔排序

  • 不熟悉

原理：
image.png

代码：
def shell_sort(list):
n = len(list)
# 初始步長
gap = n // 2
while gap > 0:
for i in range(gap, n):
# 每个步長進行插入排序
temp = list[i]
j = i
# 插入排序
while j >= 0 and list[j - gap] > temp:
list[j] = list[j - gap]
j -= gap
list[j] = temp
# 得到新的步長
gap = gap // 2
return list

⭐重要

计数排序（桶排序）

原理：

  1. 找出待排序数组nums中最大和最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数，存入数组counts的第i项
  3. 在nums上按照正确的索引填充值

属性：

  • 时间复杂度：O(n+k)，n个数据范围为k的数
  • 不稳定
  • 空间复杂度:O(k)，k表示最小值到最大值范围，需要开辟一个大小为k的counts数组用于计数
  • 适用情况：范围小、重复元素比较多的序列

代码:

  1. class Solution:
  2.     def sortArray(self, nums: List[int]) -> List[int]:
  3.         # count sort
  4.         mmax, mmin = max(nums), min(nums)
  5.         counts = [0] * (mmax - mmin + 1)
  6.         # 计算每个val出现的次数
  7.         for i, val in enumerate(nums):
  8.             counts[val - mmin] += 1 # 索引从0开始，右移mmin
  10.         pos = 0
  11.         for i in range(mmax - mmin + 1):
  12.             for j in range(counts[i]):
  13.                 nums[pos] = i + mmin # 左移mmin，恢复原本值
  14.                 pos += 1
  16.         return nums

归并排序（merge sort)

分而治之
image.png

  • 拆分
  • 排序
  • 合并

merge的时候时间复杂度是O(n),

属性：

  • 时间复杂度O(nlogn)
  • 空间复杂度O(n)
  • 稳定的

改进：

  • 对小型自阵列使用插入排序
  • 测试两个需要merge的序列是否不需要merge，可以直接相加

python3中的sort和sorted函数使用的是:归并排序+插入排序的算法

用递归来写 

  1. def mergeSort(arr):
  2.     import math
  3.     if(len(arr)<2):
  4.         return arr
  5.     middle = math.floor(len(arr)/2)
  6.     left, right = arr[0:middle], arr[middle:]
  7.     return merge(mergeSort(left), mergeSort(right))
  9. def merge(left,right):
  10.     result = []
  11.     while left and right:
  12.         if left[0] <= right[0]:
  13.             result.append(left.pop(0))
  14.         else:
  15.             result.append(right.pop(0));
  16.     while left:
  17.         result.append(left.pop(0))
  18.     while right:
  19.         result.append(right.pop(0));
  20.     return result

⭐⭐快速排序

属于分治法（三大算法：分治法、动态规划、贪婪算法）

待排序的数列中，我们首先要找一个数字作为基准数（pivot,直译是中心枢纽， 这只是个专用名词）。为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区（partition）找出基准数，然后移动，直到各个分区只有一个数时为止。

属性：

  • 时间复杂度：nlog(n)
  • 不稳定

代码：
跟思路有一些不一样，用递归实现（用到递归，就想到数学归纳法，n=1的时候成立，n=2成立，假设当n=k-1也成立，推导出n=k成立）
def _quick_sorted(nums:list) -> list:
pivot = nums[0]
left_nums = _quick_sorted([num for num in nums[1:] if num < pivot])
right_nums = _quick_sorted([num for num in nums[::-1] if num >= pivot])
return left_nums+ [pivot] + right_nums

改进：

时间复杂度分析，T(n）代表解决这个问题所需要的问题
image.png
选择pivot跟算法复杂度息息相关，选择pivot为中位数是最好的（涉及中位数算法）。

一般工作中，选择第0个、中间的、最后的，在3个数中选择中间数，称为三点中值算法。
使用中位数算法，能保证算法复杂度（不管如何选择pivot)都是nlogn。

最好的一个排序算法，时间复杂度O(nlgn)，空间复杂度O(n)，不需要额外的空间。