| by suyi | No comments

Go:排序

1、选择排序

在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾,直到所有元素均排序完毕

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

2、冒泡排序

一次比较两个元素,如果它们的顺序错误就把它们交换过来。重复地进行比较直到没有再需要交换

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

3、插入排序

通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入

func InsertSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		selected := arr[i]
		for j := i-1; j >= 0; j-- {
			if arr[j] > selected {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			} else {
				arr[j+1] = selected
				break
			}
		}
	}
}

4、归并排序

把长度为n的输入序列分成两个长度为n/2的子序列,然后分别对这两个子序列分别采用归并排序,最后将两个排序好的子序列合并成一个最终的排序序列

func MergeSort(arr []int) []int{
	if len(arr) <= 1 {
		return arr
	}
	var middle int = len(arr)/2
	left := MergeSort(arr[:middle])
	right := MergeSort(arr[middle:])
	return merge(left, right)
}

func merge(a, b []int) []int {
	alen, blen := len(a), len(b)
	var z []int = make([]int, alen + blen)
	k := 0
	i, j := 0, 0
	for i < alen && j < blen  {
		if a[i] < b[j] {
			z[k] = a[i]
			i++
		} else {
			z[k] = b[j]
			j++
		}
		k++
	}
	for i != alen {
		z[k] = a[i]
		k++
		i++
	}
	for j != blen {
		z[k] = b[j]
		k++
		j++
	}
	return z
}

5、快速排序

从数列中挑出一个元素,称为 “基准”;然后,重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面。在这个分区退出之后,该基准就处于数列的中间位置,递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

func QuickSort(arr []int) {
	sort(arr, 0, len(arr)-1)
}
func sort(arr []int, left int, right int) {
	if right <= left {
		return
	}
	p := partition(arr, left, right) //快速排序切分
	sort(arr, left, p-1)
	sort(arr, p+1, right)
}
func partition(arr []int, left int, right int) int {
	pivot := arr[left]
	i, j := left, right+1
	for true {
		for i++; arr[i] < pivot; i++ {
			if i == right {
				break
			}
		}
		for j--; pivot < arr[j]; j-- {
			if j == left {
				break
			}
		}
		if i >= j {
			break
		}
		arr[i], arr[j] = arr[j], arr[i]
	}
	arr[left], arr[j] = arr[j], arr[left]
	return j
}

6、希尔排序

选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;按增量序列个数k,对序列进行k 趟排序;每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度

func ShellSort(arr []int) {
	var gap int = len(arr) / 2
	for gap > 0 {
		for i := gap; i < len(arr); i++ {
			temp := arr[i]
			j := i
			for j >= gap && arr[j-gap] > temp {
				arr[j] = arr[j-gap]
				j = j - gap
			}
			arr[j] = temp
		}
		gap = gap / 2
	}
}

7、堆排序

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成

func HeapSort(arr []int) {
	var first int = len(arr) / 2                
	for start := first; start > -1; start-- {
		maxheapify(arr, start, len(arr)-1)
	}
	for end := len(arr) - 1; end > 0; end-- { 
		arr[end], arr[0] = arr[0], arr[end]
		maxheapify(arr, 0, end-1)
	}
}
func maxheapify(arr []int, start int, end int) {
	root := start
	for true {
		child := root*2 + 1
		if child > end {
			break
		}
		if child+1 <= end && arr[child] < arr[child+1] {
			child = child + 1
		}
		if arr[root] < arr[child] {
			arr[root], arr[child] = arr[child], arr[root]
			root = child
		} else {
			break
		}
	}
}

发表评论