第 04 天学习内容：冒泡排序、选择排序、插入排序
第 05 天学习内容：归并排序、希尔排序
第 06 天学习内容：快速排序、堆排序
第 07 天学习内容：计数排序、桶排序、基数排序

冒泡，选择，插入都是复杂度为O(n^2)的算法，快排、归并排序和堆排序是O(nlogn)的排序算法。他们都是基于比较的排序算法。基于比较的排序每次比较可以排除1/2的错误排序，所以至少要比较logn次，最优的复杂度就是O(nlogn)。希尔排序，桶排序和基数排序比较少见，不依赖比较排序，所以可以实现更优的时间复杂度，空间换时间了。

排序是比较基础的内容，知识点比较简单。快排最常用所以板子要写熟练。其他排序思想都比较简单，就原地归并排序板子复杂一点。时间复杂度高的简单排序算法实际也不会用。知识点是不难，但是第一道题目就难到我了……
python没有do-while啊……
quick_sort模板：

  1. def qsort(arr, l, r):
  2.     if l >= r: return
  3.     pivot, i, j = arr[l], l, r
  4.     while (i <= j):
  5.         while(arr[i] < pivot): i += 1
  6.         while(arr[j] > pivot): j += 1
  7.         if(i <= j):
  8.             arr[i], arr[j] = arr[j], arr[i]
  9.             i += 1
  10.             j += 1
  11.         qsort(arr, l, j)
  12.         qsort(arr, i, r)

第 04 天课程题目

看到题第一感觉感觉是：这是排序吗？仔细想了想是排序，定义一种新的有序关系。a证明：根据离散数学有序关系必须具有
1.传递性。 (a2.反对对称性。(a<=b, b<=a则 a=c)

证明传递性：[ab] < [ba], [bc] < [cb] 则 [ac] < [ca]
假设：a, b, c分别有n, m, k位
int[ab] : a10^m + b, int[ba] : b10^n + a
由[ab] < [ba] 得 a/b < (10^n-1)/(10^m-1) [1]
同理，由[bc] < [cb] b/c < (10^m-1)/(10^k-1) [2]
[式1][式2]左右分别相乘，得a/c < (10^n-1)/(10^k-1) 即 [ac] < [ca]。

证明反对称性：[ab], [ba] 位数相同，字典序可以直接转化成数字比较，易证，过程省略。

  1. class Solution:
  2.     def minNumber(self, nums: List[int]) -> str:
  3.         def qsort(arr, l, r):
  4.             if l >= r: return
  5.             pivot, i, j = arr[l], l, r
  6.             while (i <= j):
  7.                 while(arr[i] + pivot < pivot + arr[i]): i += 1
  8.                 while(arr[j] + pivot > pivot + arr[j]): j -= 1
  9.                 if(i <= j):
  10.                     arr[i], arr[j] = arr[j], arr[i]
  11.                     i += 1
  12.                     j -= 1
  13.             qsort(arr, l, j)
  14.             qsort(arr, i, r)
  16.         strs = [str(num) for num in nums]
  17.         qsort(strs, 0, len(strs) - 1)
  18.         return "".join(strs)

遍历一遍把不是0的数按顺序排好，记下非零元素个数，之后位置补0。复杂度O(n)。题解里面在交换啥？没看懂。

  1. class Solution:
  2.     def moveZeroes(self, nums: List[int]) -> None:
  3.         """
  4.         Do not return anything, modify nums in-place instead.
  5.         """
  6.         i = 0
  7.         for num in nums:
  8.             if num != 0:
  9.                 nums[i] = num
  10.                 i += 1
  11.         for j in range(i, len(nums)):
  12.             nums[j] = 0

啊，标准排序……按快排模板做就行了。也可以调用语言自带的排序函数。就当学习python了……
python中有两个sort函数。直接 list.sort()会改变原list，没有返回值。内置函数sorted(list)，不会修改原list，返回的是排好序的list。因此sorted()方法可以对string，tuple排序。

  1. class Solution:
  2.     def sortArray(self, nums: List[int]) -> List[int]:
  3.         return sorted(nums)

第 05 天课程题目

排序的题真多啊……

更多排序相关题目