排序

排序相关

排序算法

在计算机科学与数学中，一个排序算法（英语：Sorting algorithm）是一种能将一串资料依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法（例如搜索算法与合并算法）中是重要的，如此这些算法才能得到正确解答。排序算法也用在处理文字资料以及产生人类可读的输出结果。基本上，排序算法的输出必须遵守下列两个原则：

输出结果为递增序列（递增是针对所需的排序顺序而言）输出结果是原输入的一种排列、或是重组虽然排序算法是一个简单的问题，但是从计算机科学发展以来，在此问题上已经有大量的研究。举例而言，冒泡排序在1956年就已经被研究。虽然大部分人认为这是一个已经被解决的问题，有用的新算法仍在不断的被发明。

冒泡排序

从无序区透过交换找出最大元素放到有序区前端。

package main

func BubbleSort(nums []int) []int {
	num := len(nums)
	for i := 0; i < num; i++ {
		for j := i + 1; j < num; j++ {
			if nums[i] > nums[j] {
				nums[i], nums[j] = nums[j], nums[i]
			}
		}
	}
	return nums
}

快速排序

“茴“字的三种写法

在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。

递归原地快排

package main

func QuickSortDeep(nums []int) {
	quickSortDeep(nums, 0, len(nums)-1)
}
func quickSortDeep(nums []int, start, end int) {

	num := len(nums)
	if num <= 1 {
		return
	}

	if start >= end {
		return
	}

	value := nums[end]

	var j = start
	for i := start; i < end; i++ {
		if nums[i] < value {
			nums[i], nums[j] = nums[j], nums[i]
			j++
		}
	}
	nums[j], nums[end] = nums[end], nums[j]
	quickSortDeep(nums, start, j-1)
	quickSortDeep(nums, j+1, end)
}

循环原地快排

package main

//QuickSortLoop 原地快排非递归
func QuickSortLoop(nums []int) {
	length := len(nums) - 1
	if length == 0 {
		return
	}
	temp := make([][]int, 0, length)
	temp = append(temp, []int{0, length})
	for len(temp) > 0 {
		pool := temp
		temp = make([][]int, 0, length)
		for _, ints := range pool {
			start, end := ints[0], ints[1]
			if start >= end {
				continue
			}
			endValue := nums[end]
			var j = start
			for i := start; i < end; i++ {
				if nums[i] < endValue {
					nums[i], nums[j] = nums[j], nums[i]
					j++
				}
			}
			nums[j], nums[end] = nums[end], nums[j]

			temp = append(temp, []int{start, j - 1})
			temp = append(temp, []int{j + 1, end})
		}
	}
}

递归三切快排

package main

func QuickSortDeep3(nums []int) {
	quickSortDeep3(nums, 0, len(nums)-1)
}

func quickSortDeep3(nums []int, start, end int) {
	num := len(nums)
	if num <= 1 {
		return
	}

	if start >= end {
		return
	}

	value := nums[end]

	var j = start
	var m = start
	for i := start; i < end; i++ {
		if nums[i] > value {
			continue
		}
		if nums[i] < value {
			nums[i], nums[j] = nums[j], nums[i]
			j++
		}
		m++
	}
	nums[j], nums[end] = nums[end], nums[j]
	quickSortDeep3(nums, start, j-1)
	quickSortDeep3(nums, m+1, end)
}

循环三切快排

package main

func QuickSortLoop2(nums []int) {
	length := len(nums) - 1
	if length == 0 {
		return
	}
	temp := make([][]int, 0, length)
	temp = append(temp, []int{0, length})
	for len(temp) > 0 {
		pool := temp
		temp = make([][]int, 0, length)
		for _, ints := range pool {
			start, end := ints[0], ints[1]
			if start >= end {
				continue
			}
			endValue := nums[end]
			var j = start
			var m = start
			for i := start; i < end; i++ {
				if nums[i] > endValue {
					continue
				}
				if nums[i] < endValue {
					nums[i], nums[j] = nums[j], nums[i]
					j++
				}
				m++
			}
			nums[j], nums[end] = nums[end], nums[j]

			temp = append(temp, []int{start, j - 1})
			temp = append(temp, []int{m + 1, end})
		}
	}
}