不基于比较的排序找到数组排序后的最大差值

题目描述

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度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. 求逆序对的个数

几个注意点：

mid := l + (r-l)>>1 避免数组越界

for i <= mid { help[index] = nums[i] index++ i++ }，这里是一个for循环，不是if，因为是要将后面剩下的数拷贝进来

for i <= mid { help[index] = nums[i] index++ i++ }，这里是一个for循环，不是if，因为是要将后面剩下的数拷贝进来

算法排序

冒泡排序以及优化

冒泡排序

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

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]
			}
		}
	}
}
算法排序

选择排序

选择排序

思路：每次选择一个当前未排序的最小元素放到当前未排序的第一个位置上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func SelectSort(nums []int) []int {
	selectSort(nums)
	return nums
}

func selectSort(nums []int) {
	//存储最小元素对应的下标
	var min int
	//进行多少趟
	for i := 0; i < len(nums)-1; i++ {
		min = i
		//每趟从哪里开始
		j := i + 1
		for ; j < len(nums)-1; j++ {
			if nums[min] > nums[j] {
				min = j
			}
		}
		if min != i {
			nums[i], nums[min] = nums[min], nums[i]
		}
	}
}
算法排序

直接插入排序以及优化

直接插入排序

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

平均时间复杂度：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))
}

算法排序

快速排序以及优化

经典快速排序

思路：选取数组中的第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
53
54
55
56
57
58
59
60
61
package quickSortV1

import (
	"InterviewQuestions/Algo/sort"
	"fmt"
)

/**
 * @Author: yirufeng
 * @Email: yirufeng@foxmail.com
 * @Date: 2020/9/10 7:45 上午
 * @Desc:
 */

/*
快速排序第1个版本：选择第1个元素作为划分枢轴
注意：切片作为参数传递的时候是一个引用
*/
func QuickSort(nums []int) []int {
	quickSort(nums, 0, len(nums)-1)
	return nums
}

func quickSort(nums []int, low int, high int) {
	var pivotkey int
	if low < high {
		//pivotkey 为枢轴防止的最终下标
		pivotkey = partition(nums, low, high)
		quickSort(nums, low, pivotkey-1)
		quickSort(nums, pivotkey+1, high)
	}
}

func partition(nums []int, low int, high int) int {
	//选择划分元素
	dummy := nums[low]
	for low < high {
		for low < high && dummy <= nums[high] {
			high--
		}
		swap(nums, low, high)
		for low < high && dummy > nums[low] {
			low++
		}
		swap(nums, low, high)
	}
	//最后low == high
	return low
}

func swap(nums []int, i int, j int) {
	nums[i], nums[j] = nums[j], nums[i]
}


//------------------------------for test------------------------------
func main() {

	fmt.Println(QuickSort(sort.RandArray(100)))
}

经典快速排序的不足

虽然经典快速排序性能相对其他排序性能较高，但仍然有一定的瓶颈，例如如果是一个有序的数组。

此外快速排序可以从以下几点进行改进：

  1. 优化选取枢轴的策略
    1. 随机从low到high中选择一个下标对应的元素作为枢轴
    2. (三数取中)从left, high 以及mid对应的下标的元素中的三个选择一个大小居中的元素
    3. (九数取中)
  2. 优化不必要的交换：采用置换而不是交换。我们可以提前存储nums[low],之后每次在右边找到小的元素就将其赋值给nums[low]，每次在左边找到大的元素可以直接赋值给nums[high]
  3. 优化小数组的排序方案：虽然快速排序可以有很好的性能，但是在数组较小时，直接插入排序效率比快速排序效率高(直接插入排序是简单排序中性能最好的)
  4. 对快排进行尾递归优化：如果传入一个大量数据且有序的数组，快排会不断的递归，栈的深度也会越来越深，因此很容易在数据量大且数据有序的时候造成栈溢出(申请不到更多的栈空间)

9QFpxr

算法排序