排序

各种常见的基于比较的排序

• 稳定性的划分标准: 排序前后相同的值的相对次序会不会被打乱

冒泡排序

代码

func bubbleSort(arr []int)  {
	if arr == nil || len(arr) < 2 {
		return
	}
	for end := len(arr); end > 0; end-- {
		for i := 0; i < end; i++ {
			if arr[i] > arr[i+1] {
				tmp := arr[i]
				arr[i] = arr[i + 1]
				arr[i + 1] = tmp
			}
		}
	}
}

复杂度

1. 时间复杂度:
   • 外层for循环执行n, 内层for循环执行(1+2+3+…+n-1), 所以时间复杂度为O(N^2)
2. 空间复杂度:
   • 只申请了一个用于交换的临时变量, 复杂度为O(1)

是稳定性的排序

选择排序

代码

func selectionSort(arr []int)  {
	if arr == nil || len(arr) < 1 {
		return
	}
	for i := 0; i < len(arr); i++ {
		minIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[minIndex] > arr[j] {
				minIndex = j
			}
		}
		tmp := arr[i]
		arr[i] = arr[minIndex]
		arr[minIndex] = tmp
	}
}

复杂度

1. 时间复杂度:
   • 外层for循环执行n次, 内层for循环执行(n-1+n-2+…+3+2+1), 所以时间复杂度为O(N^2)
2. 空间复杂度:
   • 只申请了一个用于交换的临时变量, 复杂度为O(1)

不是稳定性的排序

插入排序

代码

func insertSort(arr []int)  {
	if arr == nil || len(arr) < 2 {
		return
	}
	for i := 1; i < len(arr); i++ {
		for j := i; j > 0; j-- {
			if arr[j] < arr[j - 1] {
				tmp := arr[j]
				arr[j] = arr[j - 1]
				arr[j - 1] = tmp
			} else {
				break
			}
		}
	}
}

复杂度

1. 时间复杂度:
   • 当数据为有序时, 插入排序的复杂度为O(N), 外层for循环执行n次, 内层for循环不执行
   • 当数据为逆序时, 插入排序的复杂度为O(N^2), 外层for循环执行n次, 内层for循环执行(1+2+3+..+n-1)
2. 空间复杂度:
   • 只申请了一个用于交换的临时变量, 复杂度为O(1)

是稳定性排序

归并排序

代码

func mergeSort(arr []int)  {
	if arr == nil || len(arr) < 2 {
		return
	}
	sortProcess(arr, 0, len(arr) - 1)
}

func sortProcess(arr[] int, left, right int)  {
	if left == right {
		return
	}
	mid := (left + right) / 2
	sortProcess(arr, left, mid)
	sortProcess(arr, mid + 1, right)
	var tmp []int
	i, j :=left, mid + 1
	for i <= mid && j <= right {
		if arr[i] <= arr[j] {
			tmp = append(tmp, arr[i])
			i++
		} else {
			tmp = append(tmp, arr[j])
			j++
		}
	}
	for i <= mid {
		tmp = append(tmp, arr[i])
		i++
	}
	for j <= right {
		tmp = append(tmp, arr[j])
		j++
	}
	for i, j = 0, left; i < len(tmp) && j <= right; i,j = i + 1, j + 1 {
		arr[j] = tmp[i]
	}
}

复杂度

1. 时间复杂度:
   • 由代码分析可得公式: T(N) = 2 * T(N/2) + O(N), 所以时间复杂度为O(N * logN)
2. 空间复杂度:
   • O(N), 需要一个和原数组的相同的辅助数组

是稳定性排序

快速排续

代码

func quickSort(arr []int)  {
	if arr == nil || len(arr) < 2 {
		return
	}
	process(arr, 0, len(arr) - 1)
}

func process(arr []int, L, R int) {
	if L < R {
		left, right := partition(arr, L, R)
		process(arr, L, left)
		process(arr, right, R)
	}
}

func partition(arr []int, L, R int) (int, int) {
	less, more := L - 1, R + 1
	index := L
	value := arr[L + rand.Intn(R - L + 1)]
	for index < more {
		if arr[index] < value {
			arr[less + 1], arr[index] = arr[index], arr[less + 1]
			less++
			index++
		} else if arr[index] > value {
			arr[more - 1], arr[index] = arr[index], arr[more - 1]
			more--
		} else {
			index++
		}
	}
	return less, more
}

复杂度

1. 时间复杂度:
   • 复杂度为O(N*logN), 和归并排序的复杂度一致
2. 空间复杂度:
   • 复杂度为O(logN), 每次递归都需要记录划分点

不是稳定性排序

堆排序

代码

func heapSort(arr []int)  {
	if arr == nil || len(arr) < 2 {
		return
	}
	for i := 0; i < len(arr); i++ {
		heapInsert(arr, i)
	}
	for heapSize := len(arr) - 1; heapSize > 0; heapSize-- {
		arr[0], arr[heapSize] = arr[heapSize], arr[0]
		heapify(arr, 0, heapSize)
	}
}

func heapInsert(arr []int, index int)  {
	for arr[index] > arr[(index - 1) / 2] {
		arr[index], arr[(index - 1) / 2] = arr[(index - 1)/ 2], arr[index]
		index = (index - 1) / 2
	}
}

func heapify(arr []int, index, heapSize int)  {
	left := index * 2 + 1
	for left < heapSize {
		target := left
		if left + 1 < heapSize && arr[left + 1] > arr[left] {
			target = left + 1
		}
		if arr[index] >= arr[target] {
			break
		}
		arr[index], arr[target] = arr[target], arr[index]
		index = target
		left = index * 2 + 1
	}
}

复杂度

1. 时间复杂度:
   • 复杂度为O(N*logN)
2. 空间复杂度:
   • 复杂度为O(1)

不是稳定性排序