排序 | Road to Final

Road to Final

排序算法就是将一组数据按照特定的规则进行排列。排序算法主要从时间复杂度，空间复杂度，稳定性等方面来考虑性能。稳定性：稳定性指的是相等的排序元素再经过排序之后相对顺序是否发生了改变。这个主要是防止破环原有的顺序，一般再多次使用不同的key来排序元素的时候防止破坏上次排序。

基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。选择排序、堆排序、快速排序不是稳定排序。

选择排序就是一次从未排序的数组中选择最小或者是最大的元素与当前元素进行交换。

由于选择排序存在swap操作，所以选择排序是一种不稳定排序算法。

时间复杂度和空间复杂度

时间复杂度为O(n2)，没有使用额外的空间。

func SelectSort(nums []int) {
	for i := 0; i < len(nums); i++ {
		min := i
		for j := i; j < len(nums); j++ {
			if nums[min] > nums[j] {
				min = j
			}
		}
		nums[i], nums[min] = nums[min], nums[i]
	}
}

冒泡排序相比较于选择排序同样是进行交换，不过冒泡排序是将较小的元素不断的进行上浮。工作原理就是每次比较相邻的两个元素，然后入喉第i个元素小于第i+1个元素，则将两个元素进行交换，知道某一次遍历过程中没有发生交换则证明排序完成。

冒泡排序虽然进行了交换，但是交换是相邻的两个元素进行交换，而相同的元素不会进行交换，所以没有破坏原有的顺序。冒泡排序是一个稳定的排序算法。

时间复杂度和空间复杂度

时间复杂度为O(n2)，完全有序的时候为O(n).没有使用额外的空间。

func BubbleSort(nums []int) {
	flag := true
	for flag {
		flag = false
		for i := 0; i < len(nums)-1; i++ {
			if nums[i] > nums[i+1] {
				flag = true
				nums[i], nums[i+1] = nums[i+1], nums[i]
			}
		}
	}
}

插入排序是将未排序范围内的元素，选择一个然后在插入到已经排序的元素中的正确位置。和选择排序不相同，选择排序是直接将选择的元素加在已经排序元素的最后面，而插入排序需要搜索之后才知道元素的合适位置。

插入排序是一种稳定的排序算法。

时间复杂度和空间复杂度

插入排序的最优时间复杂度为 O(n)，在数列几乎有序时效率很高。

插入排序的最坏时间复杂度和平均时间复杂度都为 O(n2)，没有使用额外的空间。

func InsertSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		key := nums[i]
		j := i - 1
		for j >= 0 && nums[j] > key {
			// 从后往前遍历，来查找插入位置
			nums[j+1] = nums[j]
			j--
		}
		nums[j+1] = key
	}
}

快排的工作原理就是将数组化作两个部分，然后对每个部分再次进行递归排序，因为在划分的过程已经进行了排序，所以不需要进行合并，此时的数列已经完全有序了。快排在选择哨兵的方法和遍历交换过程都有几种实现方法。

快排是一种不稳定的排序算法。

时间复杂度和空间复杂度

快速排序的最优时间复杂度和平均时间复杂度为 O(nlogn)，最坏时间复杂度为 O(n2)。

基础实现，哨兵选择第一个元素，然后分别使用两个指针从后和从前找到元素进行交换。

func quickSort(nums []int, l, h int) {
	// 第一种 使用双指针从两端进行遍历
	// 哨兵的话使用 nums[l]
	if l >= h {
		return
	}
	i, j := l, h
	watch := nums[l]
	for i < j {
		for i < j && nums[j] >= watch {
			j--
		}
		for i < j && nums[i] <= watch {
			i++
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[i], nums[l] = nums[l], nums[i]
	quickSort(nums, i+1, h)
	quickSort(nums, l, i-1)
}

• 通过 三数取中（即选取第一个、最后一个以及中间的元素中的中位数） 的方法来选择两个子序列的分界元素（即比较基准）。这样可以避免极端数据（如升序序列或降序序列）带来的退化；
• 当序列较短时，使用 插入排序 的效率更高；
• 每趟排序后，将与分界元素相等的元素聚集在分界元素周围，这样可以避免极端数据（如序列中大部分元素都相等）带来的退化。

三路快速排序是快速排序和 基数排序的混合。三路快排在选取分界点M之后，会将待排序数列划分为三个部分：小于M，等于M，以及大于M。从原理就可以看出三路快排在处理重复元素较多的数组中，效率远远高于原始的快速排序。其最佳时间复杂度为O(n)。

func ThreeQuikcSort(nums []int, l, h int) {
	if l >= h {
		return
	}
	random_index := rand.Intn(h-l) + l
	pivot := nums[random_index]
	nums[l], nums[random_index] = pivot, nums[l]
	i, j, k := l+1, l, h+1
    // i表示等于，j表示小于，k表示大于
	for i < k {
		if nums[i] < pivot {
			nums[i], nums[j+1] = nums[j+1], nums[i]
			i++
			j++
		} else if nums[i] > pivot {
			// 这个时候由于我们是从前往后进行遍历，所以不修改i
			nums[i], nums[k-1] = nums[k-1], nums[i]
			k--
		} else {
			// 相等的时候
			i++
		}
	}
	nums[l], nums[j] = nums[j], nums[l]
	ThreeQuikcSort(nums, l, j-1)
	ThreeQuikcSort(nums, k, h)
}

归并排序的主要步骤就是分割之后合并。最重要的部分就是将两个有序的数组合并为一个有序的数组。其主要的三个步骤为：

1. 将当前数组段划分为两个部分；
2. 递归地分别对两个子学列进行归并排序。
3. 将子序列进行合并

归并排序是一种稳定的排序算法。

时间复杂度和空间复杂度

快速排序的最优时间复杂度和平均时间复杂度为 O(nlogn)，空间复杂度为 O(n)。