LowB三人组（时间复杂度O(n^2)）

关键点，找到需要交换的躺数和以及完成一趟操作后的无序区

1. 冒泡排序

• 思路：冒泡泡，按照列表顺序两两进行比较，从小到大

• 原列表 [3,2,1,7,4,6,8,5]

• 第一趟比较（i=1）：[2,3,1,7,4,6,8,5]-> [2,1,3,7,4,6,8,5]-> [2,1,3,7,4,6,8,5]–>[2,1,3,4,7,6,8,5]->[2,1,3,4,6,7,8,5]->[2,1,3,4,6,7,8,5]->[2,1,3,4,6,7,5,8]。此时最大数8已经排好序，冒泡泡到了最上面的位置，此时的无序区为[2,1,3,4,6,7,5]

• 第二趟比较（i=2）：[1,2,3,4,6,7,5]->[1,2,3,4,6,7,5]->[1,2,3,4,6,7,5]->[1,2,3,4,6,7,5]->[1,2,3,4,6,7,5]->[1,2,3,4,6,5,7]。此时第二大数7已经排好序，冒泡泡到了最上面的位置，此时的无序区为[1,2,3,4,6,5]

• 第三趟比较（i=3）:[1,2,3,4,6,5]->[1,2,3,4,6,5]->[1,2,3,4,6,5]->[1,2,3,4,6,5]->[1,2,3,4,5,6]

  def bubble(nums):
  	for i in range(len(nums)-1):
  		for j in range(len(nums)-i-1):
  			if nums[j] > nums[j+1]:
  				nums[j],nums[j+1] = nums[j+1],nums[j]
  	return nums
  print(bubble(nums= [3,2,1,7,4,6,8,5]))
  1
  2
  3
  4
  5
  6
  7

2. 选择排序

• 思路：每次选择出列表中最小（或最大的）数进行排列。一趟排序记录最小的数，放到第一个位置；再一趟排序记录无序区里最小数，放到第二个位置（即第i个位置）。
• 关键点在于找到无序区最小数（即找到它的下标），并将最小数放在有序区里
• 原列表 [3,2,1,7,4,6,8,5]
• 第一趟（i=1）:选出了最小数1，交换1和3的位置->[1,2,3,7,4,6,8,5]。此时无序区为[2,3,7,4,6,8,5]
• 第二趟（i=2）:选出了第二最小数2， ->[1,2,3,7,4,6,8,5]。此时无序区为[3,7,4,6,8,5]
• 第三趟（i=3）:选出了第三最小数3 ，->[1,2,3,7,4,6,8,5]。此时无序区为[7,4,6,8,5]
• 第四趟（i=4）:选出了第四最小数4 ，交换4和7的位置->[1,2,3,4,7,6,8,5]。此时无序区为[7,6,8,5]
• 第五趟（i=5）:选出了第五最小数5，交换7和5的位置->[1,2,3,4,5,6,8,7]。此时无序区为[6,8,7]
• 第六趟（i=6）:选出了第六最小数6，->[1,2,3,4,5,6,8,7]。此时无序区为[8,7]
• 第七趟（i=7）:选出了第七最小数7，交换8和7的位置->[1,2,3,4,5,6,7,8]。此时全部排好序。

def select(nums):
	for i in range(len(nums)-1):
		min_loc = i
		for j in range(i+1,len(nums)):
			if nums[j]<nums[min_loc]:
				min_loc = j
		nums[i],nums[min_loc] = nums[min_loc],nums[i]
	return nums
print(select(nums= [3,2,1,7,4,6,8,5]))	
1
2
3
4
5
6
7
8
9

3. 插入排序

• 思路：手里的牌是有序取，每次从无序区里摸一张牌，插入到手里已有牌中的正确位置。此时摸出的牌是通过从有序区的右边往左走来插入到合适的位置的。比如说 列表[1,3,4,2,7,4,6,8,5] ，此时手里的牌有[1,3,4]已经排好序了 ，这时摸到了2，那么2先比较有序区里的4，再比较有序区里的3，再比较有序区里的1(一直往右走，直到找到一个比自身小的数，或者走到了有序区的尽头才停止并进行插入)，此时找到了合适的位置进行插入[1,2,3,4].

def insert(nums):
		for i in range(1, len(nums)): # 无序区的范围
			t = nums[i]  # 摸到的牌
			j = i-1  # 有序区的最后一个数的下标 
			while j >= 0 and nums[j] > t:
				nums[j+1] = nums[j]
				j -= 1
			nums[j+1] = t
		return nums
print(insert(nums= [3,2,1,7,4,6,8,5]))					
1
2
3
4
5
6
7
8
9
10

Niubility三人组（时间复杂度O(nlogn)）

1. 快速排序

• 记住递归，归位，折半
• 思路：取一个元素p（通常取第一个元素）,使p归位（即p的左边都比p小，p的右边都比p大）；此时列表被p分为两部分，左边都比p小，右边都比p大；递归完成排序。具体实现是：定义左右两个指针，先把第一个元素的值赋给p，从右开始找比p小的数，该数的位置记为j, 把该数放在第一个位置，接着从左找比p大的数放到右边刚刚空出来的j位置。左右指针依次挪动，直到left >= right。结束第一次归位，紧接着采用递归进行第二次归位。

def rightLocal(nums, left, right):
	p = nums[left]
	while left < right:
		while left < right and nums[right] >= p:
			right -= 1
		nums[left] = nums[right]
		while left < right and nums[left] <= p:
			left += 1
		nums[right] = nums[left]
	nums[left] = p
	return left
def quick_sort(nums, left, right):
	if left < right:
		mid = rightLocal(nums, left, right)
		quick_sort(nums, left, mid-1)
		quick_sort(nums, mid+1, right)
	return nums
	
nums = [5,7,4,6,3,1,2,9,8]
print(quick_sort(nums, 0, len(nums)-1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. 归并排序

3. 希尔排序