1.冒泡

思路：每一轮排序，每次循环从头开始比较，但尾部根据i变化，length-i-1或者length-i，相当于每次当前尾部位置固定，每次循环选出当前轮最大的放后面，大的往数组尾部移动，小的往前挪
时空分析： 时间/空间 O(n^2)
稳定性：稳定
内排排序： 内排序

python

# 1.冒泡排序-稳定-内排序-时间复杂度O(n^2), 空间复杂度O(n^2)
def bubbleSort(nums: [int]) -> [int]:
    
    for i in range(len(nums)):
        for j in range(1, len(nums)-i):
            if nums[j-1] > nums[j]:
                nums[j-1], nums[j] = nums[j], nums[j-1]
    return nums

golang

// 1.bubble
func bubbleSort(nums []int) []int {
	
	for i := range nums {
		for j:=1;j<len(nums)-i;j++ {
			if nums[j-1] > nums[j] {
				nums[j-1], nums[j] = nums[j], nums[j-1]
			}
		}
	}
	return nums
}

2.选择

思路：每一轮排序，每次循环从头开始比较，不断把小的往前面推，大的被选择交换到后面，每一轮选出当轮最小的，相当于i固定位置，但交换后的值肯定是当轮最小的
时空分析： 时间/空间 O(n^2)
稳定性：数组实现不稳定，链表稳定
内排排序： 内排序

python

# 2.选择排序-不稳定-内排序-时空O(n^2)
def selectSort(nums: [int]) -> [int]:
    length = len(nums)
    for i in range(length):
        for j in range(i, length):
            if nums[i] > nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
    return nums

golang

// 2.select
func selectSort(nums []int) []int {
	length := len(nums)
	for i := range nums {
		for j:=i;j<length;j++ {
			if nums[i] > nums[j] {
				nums[i], nums[j] = nums[j], nums[i]
			}
		}
	}
	return nums
}

3.插入

思路：每一轮排序，会把当前遍历的元素之前的那些元素排序，使得每一轮循环结束，当前元素及其前面元素都排好序，后面再循环，相当于把某元素插入到合适位置
e.g. nums = [1,2,3,2,6,4,7], 当前遍历的元素为下标3的元素2，后面的6/4/7不动，该元素2不断与其前面排好序的元素比较，直到找到下标2合适的插入位置，
即下标1/2的元素2/3之间，所以此轮循环比较后，nums=[1,2,2,3,6,4,7]，后面遍历重复此过程。
时空分析： 时间/空间 O(n^2)
稳定性：数组稳定
内排排序： 内排序

python

# 3.插入排序-稳定-内排序-时空O(n^2)
def insertSort(nums: [int]) -> [int]:
    length = len(nums)
    for i in range(1, length):
        while i > 0 and nums[i-1] > nums[i]:
            nums[i-1], nums[i] = nums[i], nums[i-1]
            i -= 1
    return nums

golang

// 3.insert
func insertSort(nums []int) []int {
	length := len(nums)
	for i:=0;i<length;i++ {
		for j:=i;j>0;j-- {
			if nums[j-1] > nums[j] {
				nums[j-1], nums[j] = nums[j], nums[j-1]
			}
		}
	}
	return nums
}

4.希尔-插入排序升级版

思路：定义增量序列gap，通常取[1,2,4,...2^(k-1)], 循环增量序列，从大的增量开始递减，每个增量序列使用时，遍历从gap到length的元素，每次比较交换i-gap与i位置的元素, 比较后i = i-gap，直到gap=0为止
时空分析： 时间/空间 O(n^2)， 与增量序列有关，[1,2,4,8...]最坏O(n^2), [1,3,5,7,9...]最坏O(n^1.5), [1,5,19,41,109,...] -> O(n^1.3)，详情查阅《数据结构与算法分析》
稳定性：不稳定
内排排序： 内排序

python

# 4.希尔排序-不稳定-内排序-时空O(n^2)
def shellSort(nums: [int]) -> [int]:
    length = len(nums)
    gap = length >> 1
    while gap:
        for i in range(gap, length):
            while i-gap >= 0 and nums[i-gap] > nums[i]:
                nums[i-gap], nums[i] = nums[i], nums[i-gap]
                i -= gap
        gap >>= 1
    return nums

golang

// 4.shell
func shellSort(nums []int) []int {
	length := len(nums)
	gap := length >> 1
	for gap > 0 {
		for i:=gap;i<length;i++ {
			j := i
			for j-gap >= 0 && nums[j-gap] > nums[j] {
				nums[j-gap], nums[j] = nums[j], nums[j-gap]
				j -= gap
			}
		}
		gap >>= 1
	}
	return nums
}