抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

题目描述

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序

注意不基于比较哦

思路

思路：桶排序
  1. 假设数组长度为n，准备n+1个桶
  2. 遍历该数组，将最小值放入到第1个位置，将最大值放入到最后一个位置
  3. 将剩下的数等分成等分成n-1份依次放入剩下对应范围的桶中，
  4. 最后这n+1个桶中至少有一个空桶，说明桶内的数值差不是最大差值，我们去桶间找最大差值
  5. 对于每个桶，我们都保存了每个桶的最小值和最大值，从第2个桶开始，每次计算当前桶的最小值与前一个桶(要有元素)的最大值的差，过程中我们动态更新最大差值

堆排序基本知识

基本介绍

堆是一个完全二叉树，因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树：

  1. 下标为i的节点的左子节点的下标为i*2+1, 右子节点的下标为i*2+2
  2. 下标为i的节点的父节点的下标为(i-1)/2

建立堆的时间复杂度：O(log1) + O(log2) + … + O(logN) 近似于 O(N)，因此建立堆的时间复杂度为O(N)

堆有大根堆以及小根堆，没有规定堆中左子树的根必须大于(或小于)右子树的根。

堆排序的两个基本步骤：(具体说明看代码注释)
  1. 建堆，循环将数组中的每个数加入堆中（每次都需要heapInsert）
  2. 不断从堆的最后一个元素交换到堆的头部，然后将堆的长度减小1，再调整堆，每次都需要heapify

冒泡排序

思路：从左向右每次两两比较相邻元素，如果前一个元素大于后一个元素，那么就交换这两个元素，一趟下来肯定有一个元素放到了最后的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func BubbleSort(nums []int) []int {
	bubbleSort(nums)
	return nums
}

func bubbleSort(nums []int) {
	//从前往后进行交换，每次都会固定好后面的元素
	for i := 0; i < len(nums)-1; 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]
			}
		}
	}
}

直接插入排序

直接插入排序是简单排序中性能最好的

平均时间复杂度：O(n^n / 4)
最好时间复杂度：O(n)
最坏时间复杂度：O(n^n)

直接插入排序版本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
41
42
43
44
45
46
47
48
49
50
51
52
package main

import (
	"log"
	"math/rand"
	"time"
)

/**
 * @Author: yirufeng
 * @Email: yirufeng@foxmail.com
 * @Date: 2020/9/10 9:12 上午
 * @Desc: 直接插入排序
 */

func InsertSort(nums []int) []int {
	insertSort(nums)
	return nums
}

//思路：如果当前元素比前一个元素小就交换，一直到当前元素大于等于前一个元素
func insertSort(nums []int) {
	//默认下标为0的已经有序，因此从下标为1的开始插入
	for i := 1; i < len(nums); i++ {
		//插入条件：要排序的元素一定要小于前面的元素
		if nums[i] < nums[i-1] {
			//什么时候结束插入：当要插入的元素的值大于等于前面的那个元素就停止插入
			for j := i; j >= 1 && nums[j] < nums[j-1]; j-- {
				nums[j], nums[j-1] = nums[j-1], nums[j]
			}
		}
	}
}


//写一个随机数生成器
func RandArray(length int) []int {
	nums := []int{}
	for i := 0; i < length; i++ {
		r := rand.New(rand.NewSource(time.Now().UnixNano()))
		nums = append(nums, r.Intn(100))
	}
	return nums
}

func main() {
	rand.Seed(time.Now().UnixNano())
	nums := RandArray(30)
	log.Println(nums)
	log.Println(InsertSort(nums))
}