01.low B三人组

1.1 冒泡

• **原理：**拿自己与上面一个比较，如果上面一个比自己小就将自己和上面一个调换位置，依次再与上面一个比较
• 第一轮结束后最上面那个一定是最大的数
• python

import random
def bubble_sort(li):
   for i in range(len(li) - 1):
      exchange = False
      for j in range(len(li) - i -1):  #内层for循环执行一次，选出一个最大值，将可以调换位置的数调整
         if li[j] > li[j + 1]:
            li[j],li[j+1] = li[j+1],li[j]
            exchange = True
      if not exchange:                # 如果上一趟没有发生交换就证明已经排序完成
         break
data = list(range(100))
random.shuffle(data)                  #将有序列表打乱
bubble_sort(data)
print(data)

• golang

package main
import "fmt"

func bubble_sort(li []int)  {
	for i := 0; i < len(li)-1; i++ {
		for j:=0;j<len(li)-i-1;j++{
			if li[j] > li[j + 1]{
				li[j],li[j+1] = li[j+1],li[j]
			}
		}
	}
}

func main() {
	arr := []int{2,7,1,5,9,3}
	bubble_sort(arr)
	fmt.Println(arr)  // [1 2 3 5 7 9]
}

1.2 选择

• 1、先假定第一个是最小的，依次与其他数比，如果其他数中有比第一个数小就假定这个更小的最小
• 2、再比，第一轮就可以找到最小的那个放到0号位置，然后在假定1号位置数最小与剩下比较，再找到第二小的数放到第1号位置

import random
def select_sort(li):
   for i in range(len(li) - 1):
      min_loc = i                        #开始先假设0号位置的值最小
      for j in range(i+1, len(li)):      #循环无序区，依次比较，小于min_loc就暂定他的下标最小
         if li[j] < li[min_loc]:         #所以内层for循环每执行一次就选出一个小值
            min_loc = j
      li[i], li[min_loc] = li[min_loc],li[i]
       
li = [1,5,2,6,3,7,4,8,9,0]
select_sort(li)
print(li)               # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

1.3 插入

• 1、列表被分为有序区和无序区两个部分，最初有序区只有一个元素
• 2、每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空

import random

def insert_sort(li):
   for i in range(1, len(li)):
      tmp = li[i]     #tmp是无序区取出的一个数
      j = i - 1       #li[j]是有序区最大的那个数
      while j >= 0 and li[j] > tmp:
         # li[j]是有序区最大的数，tmp是无序区取出的一个数，tmp从有序区最大的那个数开始比
         # 小就调换位置，直到找到有序区中值不大于tmp的结束
         li[j+1]=li[j]    #将有序区最右边的数向右移一个位置
         j = j - 1
      li[j + 1] = tmp       #将tmp放到以前有序区最大数的位置，再依次与前一个数比较
data = list(range(100))
random.shuffle(data)        #将有序列表打乱
insert_sort(data)
print(data)