Task 03： 数组排序
数组排序第一天打卡，附上学习链接
1 学习内容
1.1 冒泡排序（Bubble Sort）
冒泡排序法通过相邻元素之间的比较与交换，使值越小的元素位置越往前，值越大的元素越往后，类比水底的气泡向上冒的形态。
算法步骤：
（1）将序列中第1和2个元素进行比较，若前者大于后者，则交换位置，否则不交换；
（2）依次类推，直到第n-1和n个元素比较交换为止。一趟排序下来，最大的元素就会位于序列的第n个位置上；
（3）此后，对前n-1个元素同样操作，将n-1个元素中值最大的放置在n-1的位置上；
（4）重复，直至某一趟排序过程中不出现元素交换位置的动作，排序结束。
算法分析：
最好的情况是，初始时序列呈升序状态，只需要n-1次元素之间的比较，并且无移动，可结束排序。此时，算法时间复杂度为O(n)；
最差的情况是，初始时序列是逆序状态/最小值在尾，则需要n-1趟排序，总共进行n(n-1)/2次比较。因此，算法平均时间复杂度为O(n2)；
冒泡排序，需要移动次数较多，时间效率最低。适合于数据量较小/初始状态基本有序的情况；
元素的比较交换是在相邻元素之间进行，不会该表值相同元素的相对位置，因此冒泡排序是一种稳定排序法。
代码实现：
def bubbleSort(arr):
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
1.2 选择排序（Selection Sort）
选择排序在每一趟排序中，从剩下未排序元素中选择一个最小的元素，与未排好序的元素最前面的那个元素交换位置。
算法步骤：
（1）设置整型变量i，作为排序次数的计算，也作为第i趟排序时，未排序的元素的第1个元素的位置；
（2）设置整型变量min_i，记录未排序的n-i+1个元素中值最小元素的位置；
（3）每一趟排序开始，先令min_i = i（即暂定第i个元素为最小值，之后比较交换）；
（4）第i趟排序比较结束时，其中真正的值最小元素为下标min_i对应的元素。此时，若min_i == i时，则不用进行交换。
算法分析：
n个元素的序列，选择排序需要n-1趟；
原始序列升序，移动次数最少，为0次；原始序列逆序，移动次数最多，为3(n-1)次【3是交换arr[i]和arr[min_i]的执行次数】；
无论序列中元素的初始排列状态如何，第i趟排序要找出值最小元素都需要进行n-i次元素之间的比较。因此，整个排序过程需要进行的元素之间的比较次数都相同，为n(n-1)/2次，算法的时间复杂度为O(n2)；
由于值最小元素与未排好序的元素中第1个元素的交换动作是在不相邻的元素之间进行的，因此很有可能会改变值相同元素的前后位置，因此选择排序法是一种不稳定的排序方法。
代码实现：
def selectionSort(arr):
for i in range(len(arr) - 1):
min_i = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_i]:
min_i = j
if i != min_i:
arr[i], arr[min_i] = arr[min_i], arr[i]
return arr
1.3 插入排序（Insertion Sort)
将整个序列切分为两部分：前i-1个元素是有序序列，后n-i+1个元素是无序序列。每一次排序，将无序序列的首元素，在有序序列中找到相应的位置并插入。
算法步骤：
（1）将第一个元素作为一个有序序列，将2~n-1个元素作为无序序列；
（2）从头至尾一次扫描无序序列，将扫描到的每个元素插入到有序序列的适当位置上。
算法分析：
有n个元素的序列，插入排序方法一共要进行n-1趟排序；
对于插入排序算法，整个排序过程只需要一个辅助空间tmp；
当原始序列升序，对应的每个i值只进行一次元素之间的比较，因而总的比较次数最少，为n-1，且不需要移动元素（记录）；
当原始序列逆序，则对应的每个i值都要进行i-1次元素之间的比较，总的比较次数最多，为n(n-1)/2；
当原始序列随机，且参加排列的序列中元素可能出现的各站排列的概率相同，则取平均值作为比较次数，约为n2/4，即算法的时间复杂度为O(n2)；
插入排序算法属于稳定性排序方法。
代码实现：
def insertionSort(arr):
for i in range(1, len(arr)):
tmp = arr[i]
j = i
while j > 0 and arr[j-1] > tmp:
arr[j] = arr[j-1]
j -= 1
arr[j] = tmp
return arr
2 练习题目
2.1 剑指Offer 45、把数组排成最小的数 **
题目描述：输入一个非负整数数组，将所有数字拼接起来排成一个数，打印出拼接出的所有数字中最小的一个。 样例1：输入为[10, 2]，输出为"102"； 样例2：输入为[3, 30, 34, 5, 9]，输出为“3033459”。
解题思路：排序判断规则为，如果x+y > y+x，则x应该在y的左边，反之亦然。
class Solution:
def minNumber(self, nums: List[int]) -> str:
def quick_sort(left, right):
if left >= right:
return
i, j = left, right
while i < j:
while strs[j] + strs[left] >= strs[left] + strs[j] and i < j:
j -= 1
while strs[i] + strs[left] <= strs[left] + strs[i] and i < j:
i += 1
strs[i], strs[left] = strs[left], strs[i]
quick_sort(left, i-1)
quick_sort(i+1, right)
strs = [str(num) for num in nums]
quick_sort(0, len(strs) - 1)
return ''.join(strs)
class Solution:
def minNumber(self, nums: List[int]) -> str:
def sort_rule(x, y):
a, b = x + y, y + x
if a > b: return 1
elif a < b: return -1
else: return 0
strs = [str(num) for num in nums]
strs.sort(key = functools.cmp_to_key(sort_rule)) # amazing
return ''.join(strs)
2.2 0283 移动零 *
题目描述：给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。 样例1：输入为[0, 1, 0, 3, 12]，输出为[1, 3, 12, 0, 0]。
解题思路：对0计数，删除0，并在末尾添加满足数量的0。
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = nums.count(0)
for i in range(n):
nums.remove(0)
nums.extend([0] * n)
神奇的思路之双指针，哈哈哈哈。
左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
left = right = 0
while right < n:
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
2.3 0912 排序数组 **
题目描述：将一个整数数组nums，实现升序排列。 样例1：输入为nums=[5, 2, 3, 1]，输出为[1, 2, 3, 5]； 样例2：输入为nums=[5, 1, 1, 2, 0, 0]，输出为[0, 0, 1, 1, 2, 5]。
解题思路：用上述三种方法排序。
hahahaha，都超时了，偷懒用个list内置函数吧~~
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
nums.sort()
return nums
