排序算法
# 插入排序
# 直接插入排序
插入排序是最简单的,我们不断比较插入数据
// 插入排序
// 时间复杂度 n^2
// 因为我们这里是两层for循环,运气好的话,如果是有序的那么只需要执行一层,时间复杂度就是n
// 运气不好的话时间复杂度就是 n^2 平均的时间复杂度为 n^2
// 空间复杂度 1 ,因为我们只使用了一个临时变量,然后就没申请其他的了,所以空间复杂度为 1
func insertSort(arr []int){
// 使用j来表示当前排序的位置
var j = 0
for i:=1;i<len(arr);i++{
// 使用临时变量存储
tmp:=arr[i]
// 这个就是核心部分,首先我们让j处于i上
// 当j-1大于tmp也就是arr[i]的时候,我们就需要把数字向后移动
for j = i ; j>0 && arr[j-1] > tmp ; j--{
arr[j] = arr[j-1]
}
// for循环的顺序 就是先j=1,然后执行判断语句,成功的话我们就执行函数体,最后才执行j--
// 所以我们这里移动后,j实际上减了1,这样我们就可以直接替换了
arr[j] = tmp
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
插入排序的思想如下
时间复杂度为o(n^2) 空间复杂度为o(1)
# 折半插入排序
// 折半插入排序(这个不算10大排序算法)
// 时间复杂度为 n^2,为什么是n^2呢,外面这一层不必多说就是n
// 里面这层,虽然有两个for循环,但是实际情况下,这个执行的时间是随n线性变化的,所以也可以看成n
// 空间复杂度为 1 这里为什么不是3呢,因为我们这个空间复杂度反映的是一个趋势
// 无论我们的n是多大,我们始终只用了三个变量,所以空间复杂度为1
func bInsertSort(arr []int){
var j = 0
for i:=1;i<len(arr);i++{
// 存储临时变量
tmp := arr[i]
// 赋值low和high,这里high等于i-1
// 这里为什么i-1,因为我们最后计算的时候要确保low指针+1不会越界
low,high,mid:=0,i-1,0
// 我们使用指针来查找需要插入的位置
for low <= high {
mid = (low+high) /2
if arr[mid] > tmp {
high = mid - 1
} else {
low = mid + 1
}
}
// 这里说一下为什么最后这个low就是我们应该放入的位置
// low,high,mid的值是两个一组的,上一组是a[i]和a[mid]未经比较以前的,
// 下一组是比较后,经过调整的。调整结果要么是low=mid+1,要么是high=mid-1。
// 不知大家从上面的数据看出了什么。对!我们现在可以清楚的肯定:新元素的插入位置就是low。
// 并且还发现high比low要小一,即high+1才与low相等。这是显然的,否则while循环如何结束。
// 我想此刻大家的疑惑肯定是解开了。那么插入位置的写法就很随意了:low和high+1都行!
// fmt.Println(low,mid,high)
// 这里为什么要取low因为我们结束后j一定为是low,所以我们可以直接替换
// 我也尝试过high不减一,low<high 但是就是调不出来,我也不知道为什么
for j=i;j>low;j-- {
arr[j] = arr[j-1]
}
arr[low] = tmp
}
}
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
时间复杂度为o(n^2) 时间复杂度为O(1)
# 希尔排序
也叫缩小增量排序,通过把整个待排序记录序列分割成几组,从而减少需要排序的数据量
我们的代码如下:
// 希尔排序
// 时间复杂度 n^1.3 这个是别人试验验证的结果
// 空间复杂度 不随n变化就是1
func shellSort(arr []int) {
// 首先我们就是要确定增量大小,默认情况下,我们取n=len(arr)/2,后面我们的增量就会不断的缩小
for gap:=len(arr)/2;gap>0;gap/=2{
// 确定好增量后我们就从gap开始,这里为什么是i等于gap呢,因为我们后面是j-gap,所以我们需要从这个增量开始计算
for i:=gap;i<len(arr);i++{
// 用一个变量来暂存i的位置
j:=i
// 这里就开始比较了,我们是从gap开始的,j-gap 是我们比的第二个数字,然后我们进行交换
for j-gap>=0 && arr[j] < arr[j-gap] {
// 如果发现右边大于左边的,我们就交换一下
arr[j],arr[j-gap] = arr[j-gap],arr[j]
// 这一步其实是优化,要不要都一样,我们这里就是确保后面排序后再给前面排序,加快排序速度
j-=gap
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 交换排序
# 冒泡排序
// 冒泡排序
// 时间复杂度 n^2 因为我们用了两层循环,这种两层循环的一般都是n^2
// 空间复杂度 1 这个和上面一样,不解释
func bubbleSort(arr []int) {
flag:=true
// 首先我们直接设置i,i表示当前未排序的区间最大值,同时为了避免重复比较,设置一个flag来进行标记
for i:=len(arr)-1;i>0 && flag;i-- {
// 把flag置为false,如果没有排序那么我们就退出循环
flag = false
// 然后我们只需要按顺序排好i前面的就行了
for j:=0;j<i;j++ {
// 冒泡排序是比较相邻两个位置的元素
if arr[j] > arr[j+1] {
// flag置为true表示已经排过序了
flag = true
// 交换
arr[j+1],arr[j] = arr[j],arr[j+1]
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
算法思路如下
算法特点
(1)稳定排序。
(2)可用于链式存储结构。
(3)移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时此算法不宜采用。
# 快速排序
快速排序(QuickSort) 是由冒泡排序改进而得的。在冒泡排序过程中, 只对相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的一次交换,消除多个逆序,则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。
// 快速排序-返回枢纽位置并进行排序,传入一个low指针,一个high指针,然后给数组进行简单排序
// 这里我们的数组排序好后返回一个中间位置的指针
func partition(arr []int,low int,high int) int {
// 一般情况下我们直接取low点作为枢纽,然后我们就要进行排序,把比low小的排左边,比low大的排右边
tmp:=arr[low]
// 当low大于high时我们的排序就已经好了,这个时候其实low就是high同时这个值为我们的枢纽
for low < high {
// 首先我们从high哪里往左遍历,找出第一个比tmp小的点
for low < high && arr[high] >= tmp {
high --
}
// 找到这个比tmp小的点后我们就替换过去,这个时候我们的high其实留了一个空
arr[low] = arr[high]
// 因为上面high有一个空,所以这时候我们就可以从low指针开始出发,找到一个比tmp大的
for low < high && arr[low] <= tmp {
low ++
}
// 找到后我们就可以替换了,这个时候我们就把high给替换了,此时low就没用了
// 然后我们就可以进行下一轮比较了,然后我们可以继续把比tmp小的点放到low这里
arr[high] = arr[low]
}
// fmt.Println(low,high)
// 最后替换完后,low和high其实就指向同一个位置了,这时我们就可以把low换成tmp了
arr[low] = tmp
// 返回low指针
return low
}
// 快速排序
// 时间复杂度 nlogn 这东西推导比较复杂
// 具体参考 https://www.zhihu.com/question/22393997
// 空间复杂度 最好情况nlogn(注意这个log以2为底),最坏情况就是n
func quickSort(arr []int,low int,high int) {
// 这里也要判断,要不然会堆栈溢出
if low < high {
// 给数组进行简单排序,同时留下一个mid位置的指针
mid:=partition(arr,low,high)
// 这里我们使用递归来分别递归左右两部分
quickSort(arr,low,mid-1)
quickSort(arr,mid+1,high)
}
}
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
算法特点
(1)记录非顺次的移动导致排序方法是不稳定的。
(2)排序过程中需要定位表的下界和上界,所以适合用于顺序结构,很难用于链式结构。
(3)当n较大时,在平均情况下快速排序是所有内部排序方法中速度最快的一种,所以其适合初始记录无序、n较大时的情况。
# 选择排序
选择排序的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,按顺序放在已排序的记录序列的最后,直到全部排完为止。本节首先介绍一种简单选择排序方法,然后给出另一种改进的选择排序方法——堆排序。
# 简单选择排序
// 选择排序
// 时间复杂度 n^2 这个很简单,因为是for循环嵌套
// 空间复杂度为1
func selectSort(arr []int){
j:=0
for i := 0; i < len(arr); i++ {
// 记录最小值的位置
min:=i
// 找出最小的那个值,这里我们从i开始往后找,找到一个最小的
for j=i+1;j<len(arr);j++{
if arr[j] < arr[min]{
min = j
}
}
// 最小值进行替换一下
arr[i],arr[min] = arr[min],arr[i]
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(1)就选择排序方法本身来讲,它是一种稳定的排序方法,但图8.6所表现出来的现象是不稳定的,这是因为上述实现选择排序的算法采用“交换记录”的策略所造成的,改变这个策略,可以写出不产生“不稳定现象”的选择排序算法。
(2)可用于链式存储结构。
(3)移动记录次数较少,当每一记录占用的空间较多时,此方法比直接插入排序快。
# 堆排序
堆排序(HeapSort) 是一种树形选择排序, 在排序过程中, 将待排序的记录[.] 看成是一根完全二叉树的顺序存储结构、利用完全二叉树中双亲结点和孩子结点之间的内在关系、在当前无序的序列中选择关键字最大(或最小)的记录。
堆的定义
堆要满足下面这样的条件
堆可以看成完全二叉树
堆排序的步骤
首先需要建初堆,建初堆的目的是将无序序列调整为堆,然后我们不断交换堆顶和堆最后一个元素,然后重新调整堆
筛选法调整堆的算法步骤如下
建初堆的步骤如下
// 建初堆
func createHeap(arr []int) {
// 这里我们使用筛选法来建初堆,我们依次把、[n/2],[n/2]-1,....,1的节点都调整为堆即可
n := len(arr) - 1
// 根据堆的性质,在完全二叉树中所有序号大于 [n/2]的节点都是叶子,
// 所以我们只需要调整 1 - n/2 这个区间把这几个点调整为大根堆就行
// 这里调整堆传入了一个开始点和结束点
for i :=n/2;i>=0;i--{
adjustHeap(arr,i,n)
}
}
// 调整堆
func adjustHeap(arr []int,s int,m int) {
// 保存起始点的值作为临变量
rc:=arr[s]
// 我们使用筛选法来调整堆
// 这里使用了堆的性质
// 当 ki>=k2i 且 ki >= k2i+1 或 ki <=k2i 且 ki <= k2i+1
for j:=2*s;j<=m;j*=2{
if j<m && arr[j]<arr[j+1]{ j++ }
if rc >= arr[j] { break}
arr[s] = arr[j]
s=j
}
arr[s] = rc
}
// 堆排序
// 时间复杂度 nlogn
// 这里耗时操作在于筛选和调整 筛选需要n-1次 然后n个节点的二叉树深度为logn +1
// 空间复杂度 1 因为只需要一个临时空间
func heapSort(arr []int) {
// 先建堆,保证初始的时候是一个堆
createHeap(arr)
// 开始进行for循环,进行堆排序
for i:=len(arr)-1;i>0;i--{
// 这里我们把最大的那个最后一个(这个指的是当前堆的最大一个)互换
// 因为我们堆排序后0号是最大的
arr[0],arr[i] = arr[i],arr[0]
// 我们i号是最大的了,所以我们忽略i,从i-1开始进行调整
adjustHeap(arr,0,i-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
利用了堆里面首部元素最大的特点
# 归并排序
// 合并表
// 注意这里我们arr2是一个空数组,然后arr1的low和mid是一个排好序的数组,mid+1和high也是一个排好序的数组
// 这个函数的作用就是把两个数组合并为一个数组,放入arr2中
func Merge(arr1 []int,arr2 []int,low int,mid int,high int) {
// 这里我们使用i和j来表示arr1数组的两部分,然后k就表示arr2数组的位置
i,j,k:=low,mid+1,low
// 只要有一个数组到头了,我们就介绍排序
for i <= mid && j<=high {
// 因为我们要合并两个数组,所以我们需要判断一下数组的两部分到底谁大
if arr1[i] > arr1[j] {
// 注意,k表示arr2的位置,然后j表示的是 mid+1 到high这个数组
arr2[k] = arr1[j];k++;j++
} else {
// 注意,k表示arr2的位置,然后j表示的是 low 到mid 这个数组
arr2[k] = arr1[i];k++;i++
}
}
// 剩余部分因为已经是一个有序的数组了,所以我们直接按顺序加到arr2就行
for i<=mid {
arr2[k] = arr1[i];i++;k++
}
for j<=high {
arr2[k] = arr1[j];j++;k++
}
}
// 2-路归并排序
// 时间复杂度nlogn
// 空间复杂度 n 因为我们排序的时候需要申请n个空间来存储
func mSort(arr []int,arr2 []int,low int,high int) {
// 当low和high相等的时候,这个时候大小为1,我们直接放到arr2就行
if low == high{
arr2[low] = arr[low]
} else {
// 我们准备开始进行拆分,我们需要把我们的数组拆成两部分
arr3:=make([]int,high+1)
// 直接取mid作为数组的分界点
mid:= (low + high) / 2
// 首先我们把low和mid 进行排序并放入arr3中
mSort(arr,arr3,low,mid)
// 然后我们把mid+1和high 进行排序并放入arr3中
mSort(arr,arr3,mid+1,high)
// 最后我们得到的数组在arr3中已经排好序并分成了两部分
// 因为arr2是一个空数组,所以我们把arr3再进行排序,最后就是合并为一个有序的表并放入arr2中
Merge(arr3,arr2,low,mid,high)
}
}
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
# 其他排序
# 计数排序
参考:漫画:什么是计数排序?-五分钟学算法 (cxyxiaowu.com) (opens new window)
这个算法不是基于元素比较,而是利用数组下标来确定元素的正确位置
假定我的的20个随机整数值如下:
9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9 ,7,9
我们可以确定最大值为10最小值为0,这样我们就建立一个大小为11的数组
非常简单,让我们遍历这个无序的随机数列,每一个整数按照其值对号入座,对应数组下标的元素进行加1操作。比如第一个整数是9,那么数组下标为9的元素加1
最终,数列遍历完毕时,数组的状态如下:
有了这个“统计结果”,排序就很简单了。直接遍历数组,输出数组元素的下标值,元素的值是几,就输出几次:
0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10
通常,我们为了节省空间,需要确定一个最大值和最小值
实际代码如下:
// 计数排序,这里我们传入一个数组,一个最小值,一个最大值
func countingSort(arr []int, minvalue, maxValue int){
// 首先我们建立一个统计数组,为了节省空间我们直接取最大值和最小值的差+1的空间,这个时候最大值在最后一个,最小值在第一个
count:=make([]int,maxValue-minvalue+1)
// 遍历数组,统计出现的次数,注意我们计算的时候需要减minValue
for _,v:=range arr{
count[v-minvalue] ++
}
// 最后我们输出数组,这里我们使用i来标记arr数组
i:=0
// 遍历count
for k,v:=range count{
// 如果count数组为0那么就不管,如果不为0那么就为几,我们就输出几次
if v!=0 {
// 输出v次
for j:=0;j<v;j++{
arr[i] = minvalue + k
i ++
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 桶排序
1.9 桶排序 | 菜鸟教程 (runoob.com) (opens new window)
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:
- 在额外空间充足的情况下,尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
1. 什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
2. 什么时候最慢
当输入的数据被分配到了同一个桶中。
比如我们有下面这几个数组
[63,157,189,51,101,47,141,121,157,156,194,117,98,139,67,133,181,13,28,109]
我们分成5个桶,下面开始排序
- 找到数组中的最大值194和最小值13,然后根据桶数为5,计算出每个桶中的数据范围为
(194-13+1)/5=36.4
- 遍历原始数据,(以第一个数据63为例)先找到该数据对应的桶序列
Math.floor(63 - 13) / 36.4) =1
,然后将该数据放入序列为1的桶中(从0开始算) - 当向同一个序列的桶中第二次插入数据时,判断桶中已存在的数字与新插入的数字的大小,按从左到右,从小打大的顺序插入。如第一个桶已经有了63,再插入51,67后,桶中的排序为(51,63,67) 一般通过链表来存放桶中数据,但js中可以使用数组来模拟
- 全部数据装桶完毕后,按序列,从小到大合并所有非空的桶(如0,1,2,3,4桶)
- 合并完之后就是已经排完序的数据
// 桶排序,这里我们传入一个最大值,还有一为个桶的数量
// 时间复杂度 为n+k
// 空间复杂度为 n+k
func sortBucket(arr []int,max int,num int) {
// 创建桶,大小为我们传入桶的数量
buckets := make([][]int,num)
var index int
// 遍历数组
for _,v := range arr{
// 分配桶 index = value * (n-1)/k 这里我们使用公式来确放入的位置
index = v * (num-1) / max
// 把我们的数字放入桶内
buckets[index] = append(buckets[index],v)
}
// 桶内排序
tmpPos := 0
// 这里我们遍历每一个桶
for k:=0; k < num; k++ {
// 获取桶里面数据的长度
bucketLen := len(buckets[k])
// 如果我们这个桶大小为0,那么我们就对桶里面进行排序
if bucketLen>0{
// 使用插入排序对数组进行排序
insertSort(buckets[k])
// 我们把排序好的部分复制到数组中
copy(arr[tmpPos:],buckets[k])
// 数组位置加上桶的大小,开始保存下一个桶
tmpPos +=bucketLen
}
}
}
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
# 基数排序
基数排序与桶排序、计数排序都用到了桶的概念,但对桶的使用方法上有明显差异:
- 基数排序:根据键值的每位数字来分配桶;
- 计数排序:每个桶只存储单一键值;
- 桶排序:每个桶存储一定范围的数值;
基数排序按取数方向分为两种:从左取每个数列上的数,为最高位优先(Most Significant Digit first, MSD);从右取每个数列上的数,为最低位优先(Least Significant Digit first, LSD)。下列以LSD为例。
基数排序步骤:
- 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零
- 从最低位开始,依次进行一次排序
- 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
func radixSort(theArray []int,max int){
// 因为前面我们获取了最大值,这里我们获取一下最大值的位数
var count = 0
for max % 10>0{
max /= 10
count++
}
// 给桶中对应的位置放数据
for i:=0; i<count; i++ {
// 根据不同的位数,我们来获取10的n次方,用于后面获取每位的值
theData := int(math.Pow10(i))
// 建立空桶
bucket:=make([][]int,10)
// 遍历数组
for k:=0; k<len(theArray); k++{
// 这里我们进行取余操作,目的是为了获取这个数组在每位上的值
theResidue := (theArray[k]/theData) %10
// 获取到了位数后我们直接放入对应的桶中
bucket[theResidue] = append(bucket[theResidue],theArray[k])
}
// 一遍循环完之后需要把数组二维数据进行重新排序,比如数组开始是10 1 18 30 23 12 7 5 18 233 144 ,循环个位数
// 循环之后的结果为10 30 1 12 23 233 144 5 7 18 18 ,然后循环十位数,结果为1 5 7 10 12 18 18 23 30 233 144
// 最后循环百位数,结果为1 5 7 10 12 18 18 23 30 144 233
var x = 0
// 遍历我们的桶
for p:=0; p<len(bucket); p++ {
for q:=0; q<len(bucket[p]); q++ {
// 这里按照桶的结构,按桶的顺序把桶里面的数据放入数组中
if bucket[p][q]!=0 {
theArray[x] = bucket[p][q]
x++
}else {
break
}
}
}
}
}
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