算法学习-排序

简单排序

1.冒泡排序

原理： 对给定的数组进行多次遍历，每次比较相邻的两个数，如果前一个比后一个大，则交换

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

2.选择排序

原理： 对给定的数组多次遍历，每次找出最大值的索引

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

3.插入排序

原理： 从第二个数开始向右遍历，每次将该位置的元素向左移动，放置合适的位置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

高级排序

1.希尔排序

原理：

选定一个增量h，按照增长量h作为数据分组的依据
对分好组的每一组数据完成插入排序
减少增长量，最小减为1，重复第二步操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func shellSort(nums []int) []int {
	//1.根据数组长度确定增长量h
	var h int = 1
	for h < len(nums)/2 {
		h = 2*h + 1
	}
	//2.希尔排序
	for h >= 1 {
		for i := h; i < len(nums); i++ {
			for j := i; j >= h; j -= h {
				//2.1 找到待插入的元素
				if nums[j-h] > nums[j] {
					//2.2 把待插入的元素插入插入有序数列中
					nums[j-h], nums[j] = nums[j], nums[j-h]
				}
			}
		}
		//减小h的值
		h = h / 2
	}
	return nums
}

2.归并排序

原理： 给定一组数组，首先将每个相邻的长度为1的子序列进行归并，得到n/2个长度的为2或1的有序子序列；再将其两两归并，反复执行，直到得到一个有序序列为止。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


//mergeSort 归并排序
//l为最小索引，r为最大索引
func mergeSort(nums []int, l, r int) {
	if l < r {
		mid := (l + r) / 2
		//对每组数据进行排序
		mergeSort(nums, l, mid)
		mergeSort(nums, mid+1, r)
        //合并
		merge(nums, l, mid, r)
	}
}

func merge(nums []int, l, mid, r int) {
	//左右两个子数组
	n1, n2 := mid-l+1, r-mid
	left := make([]int, n1)
	right := make([]int, n2)
	copy(left, nums[l:mid+1])
	copy(right, nums[mid+1:r+1])
	//将左右子数组排序合并到原数组中
	i, k, j := 0, l, 0
	for ; i < n1 && j < n2; k++ {
		if left[i] > right[j] {
			nums[k] = right[j]
			j++
		} else {
			nums[k] = left[i]
			i++
		}
	}
	for ; i < n1; i++ {
		nums[k] = left[i]
		k++
	}
	for ; j < n2; j++ {
		nums[k] = right[j]
		k++
	}
}

3.快速排序