十大排序算法

Posted on Edited on In Word count in article: 5.9k Reading time ≈ 5 mins.
十大排序算法，以及golang版

快速排序

分成两个数组，对每个数组进行递归排序，不断递归，最后得到排好序的 数组

先处理排序，再递归

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
func quickSort(q []int, l, r int) {
	// 递归终止条件
	if l >= r {
		return
	}
	x := q[(l+r)>>1] // 确定分界点，从中间开始
	i, j := l-1, r+1 // 两个指针，因为do while要先自增/自减
	// ，大的放右边，小的放左边
	for i < j {
		for {
			i++
			// 碰到大于的就停止
			if q[i] >= x { break }
		}
		for {
			j--
			// 碰到小于的就停止
			if q[j] <= x { break}
		}
		if i < j { // swap 两个元素
			q[i], q[j] = q[j], q[i]
		}
	}
	// 递归处理左右两段
	quickSort(q, l, j) 
	quickSort(q, j+1, r)
}

时间：O(nlogn)
空间：O(n)
稳定

归并排序

分治思想与快排相反，先排，再合并，先递归在合并

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

func merge_sort(nums []int, left, right int) {
	if left >= right { return }
	// 找中间位置
	mid := (left + right) >> 1
	// 左右排序
	merge_sort1(nums, left, mid)
	merge_sort1(nums, mid+1, right)
	//合并
	tmp := []int{}
	// 左右的起始位置
	i, j := left, mid+1
	for i <= mid && j <= right {
		// 比较两个指针的位置，放入新数组
		if nums[i] <= nums[j] {
			tmp = append(tmp, nums[i])
			i++
		} else {
			tmp = append(tmp, nums[j])
			j++
		}
	}
	// 没排完的，放到后面
	if i <= mid {
		tmp = append(tmp, nums[i:mid+1]...)
	} else { //如果使用...运算符，可以将一个切片的所有元素追加到另一个切片里
		tmp = append(tmp, nums[j:right+1]...)
	}
	// 放到nums里
	copy(nums[left:right+1], tmp)
}

时间： O(nlogn)
空间：O(n) 临时数组加递归深度
稳定

堆排序

将数组生成大顶堆，或者小顶堆，再逐步取出堆顶元素

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
func heap_sort(nums []int) []int {
    lens := len(nums) - 1
    // 建堆 O(n) lens/2后面都是叶子节点，不需要向下调整
    for i := lens/2; i >= 0; i -- { 
        down(nums, i, lens)
    }
    for j := lens; j >= 1; j -- {
    	// 将最大值放到后面
        nums[0], nums[j] = nums[j], nums[0]
        // 最后一位已经是最大值，调整之前的值
        lens --
        down(nums, 0, lens)
    }
    return nums
}
//O(logn)大根堆，如果堆顶节点小于叶子，向下调整
func down(nums []int, i, lens int) { 
	// 当前值是最大值
    max := i 
    // 如果他的左节点大于最大值
    if i<<1+1 <= lens && nums[i<<1+1] > nums[max] {
    	// 则最大值等于子节点
        max = i<<1+1
    }  
    // 如果他的右节点大于最大值
    if i<<1+2 <= lens && nums[i<<1+2] > nums[max] {
        max = i<<1 + 2
    }
    // 如果最大值发生变化，则交换两个位置
    if max != i {
        nums[max], nums[i] = nums[i], nums[max]
        // 递归向下调整
        down(nums, max, lens)
    }
}

时间: O(nlogn)
空间：O(1）
不稳定

选择排序

当前循环的值为最小值，内层循环遍历后面的，后面的小于最小值，找到一个最小的，最后交换位置

1
2
3
4
5
6
7
8
9
10
11
func select_sort(q []int) {
    for i := 0; i < len(q) - 1; i++ {
        minIndex := i
        for j := i;j < len(q); j++ {
            if q[j] < q[minIndex] {
                minIndex = j
            }
        }
        q[i], q[minIndex] = q[minIndex], q[i]
    }
}

时间复杂度：O(n ^2)
空间复杂度:O(1)
不稳定

冒泡排序

两两交换，保证最后一个是最大值，然后第二次遍历就到最后一个的前面截止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func bubbleSort(q []int) {
    n := len(q)
    for i := 0; i < n - 1; i++ {
        exchange := false
        for j := 0; j < n-1-i; j++ {
            if q[j] > q[j+1] {
                q[j], q[j+1] = q[j+1], q[j]
                exchange = true
            }
        }
        if !exchange {
            break
        }
    }

}

时间复杂度：O(n ^2)
空间复杂度:O(1)
稳定

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func insertSort(nums []int) []int {
	n := len(nums)
	for i := 1; i < n; i++ {
		tmp := nums[i]
		j := i - 1
		//左边比右边大
		for j >= 0 && nums[j] > tmp { 
			//右边的数就等于前一个数，最后大于tmp的都被j+1赋值，相当于右移
			nums[j+1] = nums[j] 
			j--                 //到前一个数
		}
		// 上一步比tmp大的 都右移过去之后，小于tmp的右边
		nums[j+1] = tmp
	}
	return nums
}

时间复杂度：O(n ^2)
空间复杂度:O(1)
稳定

希尔排序

插入排序的优化，长度/2，再次/4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func shell_sort(q []int) {
	// 先排n/2，后面的排好，再排n/4
    for k := len(q) / 2; k > 0; k /= 2 {
    	// 从k开始往后，插入排序
        for i := k; i < len(q); i++ {
            tmp := q[i]
            j := i - k
            for j >= 0 && tmp < q[j] {
                q[j+k] = q[j]
                j -= k
            }
           q[j+k] = tmp
        }
    }
}

时间复杂度: O(nlogn)
空间复杂度: O(1)
不稳定

计数排序

找出最大值即可，然后从1到最大值生成map，有值记为1，没有的记为0

然后继续0到最大值，遍历，从字典取值，就是按顺序取的，按顺序放到数组里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func qSort(q []int) {
    v := [10001]int{}
    for i := 0; i < len(q); i++{
        v[5000+q[i]]++
    }
    idx := 0
    for i := 0; i < 10001; i++ {
        for v[i] > 0 {
            q[idx] = i - 5000
            idx++
            v[i]--
        }
    }
}

时间复杂度:O(n+k)
空间复杂度:O(k)
稳定排序

桶排序

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
func bin_sort(li []int, bin_num int) {
	// 找最大值，找最小值
    min_num, max_num := li[0], li[0]
    for i := 0; i < len(li); i++ {
        if min_num > li[i] {
            min_num = li[i]
        }
        if max_num < li[i] {
            max_num = li[i]
        }
    }
    // 捅数，生成捅
    bin := make([][]int, bin_num)
    for j := 0; j < len(li); j++ {
    	// 计算捅的位置，减去最小值，除以 （最大值-最小值+1）/桶数
        n := (li[j] - min_num) / ((max_num - min_num + 1) / bin_num)
        // 加入捅
        bin[n] = append(bin[n], li[j])
        // ，每个捅排序，插入排序
        k := len(bin[n]) - 2
        for k >= 0 && li[j] < bin[n][k] {
            bin[n][k+1] = bin[n][k]
            k--
        }
        bin[n][k+1] = li[j]
    }
    // 排好序后给到结果
    o := 0
    for p, q := range bin {
        for t := 0; t < len(q); t++ {
            li[o] = bin[p][t]
            o++
        }
    }
}

时间复杂度: O(n+k)
空间复杂度: O(n+k)
稳定

基数排序

个位，十位，百位排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func radix_sort(li []int) {
    max_num := li[0]
    for i := 0; i < len(li); i++ {
        if max_num < li[i] {
            max_num = li[i]
        }
    }
    for j := 0; j < len(strconv.Itoa(max_num)); j++ {
        bin := make([][]int, 10)
        for k := 0; k < len(li); k++ {
            n := li[k] / int(math.Pow(10, float64(j))) % 10
            bin[n] = append(bin[n], li[k])
        }
        m := 0
        for p := 0; p < len(bin); p++ {
            for q := 0; q < len(bin[p]); q++ {
                li[m] = bin[p][q]
                m++
            }
        }
    }
}

时间复杂度: O(kn)
空间复杂度: O(n+k)
稳定

翻转对

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
func reversePairs(nums []int) int {
    if len(nums) == 0 { // 没有元素，没有翻转对
        return 0
    }
    count := 0 // 翻转对个数
    mergeSort(nums, &count, 0, len(nums)-1) // 归并的范围：0到末尾
    return count
}

// 对当前的序列（start到end）进行归并排序
func mergeSort(nums []int, count *int, start, end int) {
    if start == end { // 递归的出口：不能再二分了，返回
        return
    }
    mid := start + (end-start)>>1 // 当前序列的中点索引

    mergeSort(nums, count, start, mid) // 递归左序列
    mergeSort(nums, count, mid+1, end) // 递归右序列

    // 此时左右序列已升序，现在做：合并前的统计、以及合并
    i := start                 // 左序列的开头
    j := mid + 1               // 右序列的开头
    for i <= mid && j <= end { // i j 都不越界
        if nums[i] > 2*nums[j] {
            *count += mid - i + 1 // i 到 mid，都ok
            j++                   // 考察下一个j，继续找 i
        } else {                  // 当前i不满足，考察下一个i
            i++
        }
    }
    i = start  
    j = mid + 1 // 复原 i j 指针，因为现在要合并左右序列

    temp := make([]int, end-start+1) // 辅助数组，存放合并排序的数
    index := 0                       // 从0开始
    for i <= mid && j <= end {       // 如果 i j 都没越界
        if nums[i] < nums[j] {    // nums[i]更小
            temp[index] = nums[i] // 取nums[i]，确定了temp[index]
            index++               // 确定下一个
            i++                   // 考察下一个i，j不动
        } else {
            temp[index] = nums[j]
            index++
            j++
        }
    }
    for i <= mid {            // 如果 i 没越界，j越界了
        temp[index] = nums[i] // i 和 i右边的都取过来
        index++               // 确定下一个数
        i++
    }
    for j <= end {            // j 没越界，i越界了
        temp[index] = nums[j] // j 和 j右边的都取过来
        index++               // 确定下一个数
        j++
    }
    k := 0
    for i := start; i <= end; i++ { // 根据合并后的情况，更新nums
        nums[i] = temp[k]
        k++
    }
}