1. 首页
  2. 文章中心
  3. 学习

排序算法-插入排序 #算法学习题目引入设计题目开始学习

121 阅读 0 评论
我是靠谱客的博主 幸福小虾米，这篇文章主要介绍排序算法-插入排序 #算法学习题目引入设计题目开始学习，现在分享给大家，希望可以做个参考。

每日一题
Day1 兔子试毒 #每日一题
Day2 排序算法-插入排序 #每日一题
Day3 排序算法 #每日一题

Day2

  • 题目引入
  • 设计题目
  • 开始学习
    • 潦草的自编程序
    • 学习十大经典算法
    • 默写
      • 插入排序
      • Day3见

题目引入

排序算法

最经典的算法之一
菜鸟教程这里罗列了十大经典排序算法，讲解的挺详细的，还有每种算法的单独讲解并配备了动图更好理解
以下就是教程中的冒泡算法图解
在这里插入图片描述

设计题目

排序算法是编程学习中接触最久的一种经典算法题，网上很多经典的算法和各种花式解法
所以我想分成几个步骤来慢慢的复习一下这个经典算法题

  1. 先用自己思路简单的实现排序
  2. 详细学习一下十大经典算法
  3. 重写(默写)十大算法
  4. 充分理解算法

开始学习

潦草的自编程序

第一次排序

复制代码
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
package main
import (
    "fmt"
    "math/rand"
    "time"
)
func main() {
    start := time.Now().UnixNano()
    fmt.Printf("start: %vn", start)
    defer func() {
        // 记录耗时
        end := time.Now().UnixNano()
        fmt.Printf("end: %vnduration: %vn", end, end-start)
    }()
    // 1 随机生成固定数组
    var arr []int
    // numsCount := 10
    numsCount := 100000
    for i := 0; i < numsCount; i++ {
        rand.Seed(int64(i))
        // rand.Seed(int64(time.Now().UnixNano()) + int64(i)) // 非固定
        arr = append(arr, rand.Intn(numsCount*10))
    }
    // 生成数组的时间为794828300 0.79秒
    fmt.Printf("排序前: %v ... %vn", arr[:10], arr[len(arr)-10:])
    // 2 从小到大排序
    arr = arrSort(arr)
    fmt.Printf("排序后: %v ... %vn", arr[:10], arr[len(arr)-10:])
}
// 2.1 用自己第一个思路做排序算法
func arrSort(arr []int) []int {
    for i, num := range arr {
        min := num
        minI := i
        for _i := i + 1; _i < len(arr); _i++ {
            if min > arr[_i] {
                min = arr[_i]
                minI = _i
            }
        }
        // 把最小的数放到第一位
        arr[minI] = arr[i]
        arr[i] = min
        // fmt.Printf("%v: %vn", i, arr)
    }
    return arr
}

输出

复制代码
1
2
3
4
5
6
start: 1629689102646758900
排序前: [793274 498081 266786 151008 636829 243626 651548 305886 697888 831901] ... [715529 760583 152069 297222 979203 168585 95815 653064 187794 350723]
排序后: [8 20 31 33 34 40 44 49 61 69] ... [999912 999938 999939 999947 999955 999957 999964 999984 999986 999994]
end: 1629689108024490800
duration: 5377731900

耗时5.3秒

第二次排序

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func arrSort(arr []int) []int {
    for i := 1; i < len(arr); i++ {
        if arr[0] > arr[i] {
            num := arr[i]
            arr = append([]int{num}, (append(arr[:i], arr[i+1:]...))...)
        } else {
            for _i := 1; _i < i; _i++ {
                if arr[_i] > arr[i] {
                    num := arr[i]
                    var mNums = make([]int, len(arr[_i:i]))
                    copy(mNums, arr[_i:i])
                    arr = append(append(arr[:_i], num), (append(mNums, arr[i+1:]...))...)
                    break
                }
            }
        }
        // fmt.Printf("%v: %vn", i, arr)
    }
    return arr
}

输出

复制代码
1
2
3
4
5
6
start: 1629689520944933200
排序前: [793274 498081 266786 151008 636829 243626 651548 305886 697888 831901] ... [715529 760583 152069 297222 979203 168585 95815 653064 187794 350723]
排序后: [8 20 31 33 34 40 44 49 61 69] ... [999912 999938 999939 999947 999955 999957 999964 999984 999986 999994]
end: 1629689535714069200
duration: 14569136000

[崩溃]，一顿操作猛如虎，一看战绩14.5，还是乖乖先学习一下经典算法吧

学习十大经典算法

…

默写

插入排序

看了十大经典算法的插入算法后，我发现我的第二个思路跟插入算法有点相似，于是我试着跑了一下插入算法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
func arrSort(arr []int) []int {
    for i := range arr {
        preIndex := i - 1
        current := arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        }
        arr[preIndex+1] = current
    }
    return arr
}

输出

复制代码
1
2
3
4
5
6
start: 1629690074829951700
排序前: [793274 498081 266786 151008 636829 243626 651548 305886 697888 831901] ... [715529 760583 152069 297222 979203 168585 95815 653064 187794 350723]
排序后: [8 20 31 33 34 40 44 49 61 69] ... [999912 999938 999939 999947 999955 999957 999964 999984 999986 999994]
end: 1629690076919296600
duration: 2089344900

2.08秒？啥？这是为什么？差距居然这么大

仔细观察一下自己的代码
以下逻辑看起来比较复杂，但是其实只有两步关键代码

  • s1 把最小的数插到第一位
  • s2 把遍历到的当前数插入到第二位与其之间
复制代码
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
func arrSort(arr []int) []int {
	// 计算两步关键代码执行次数
    s1 := 0
    s2 := 0
	// 从数组的第二个开始遍历
    for i := 1; i < len(arr); i++ {
    	// 将当前的数与第一个数进行对比，如果第一个数大于当前数
        if arr[0] > arr[i] {
            s1++
        	// 则取出当前数
            num := arr[i]
            // 通过append方法将当前数放在数组第一位
            // 合并当前数之前的数和当前数之后的数而后放在第二位之后
            arr = append([]int{num}, (append(arr[:i], arr[i+1:]...))...)
        } else {
        	// 如果第一个数小于当前数，则从第二个数开始遍历与当前数对比
            for _i := 1; _i < i; _i++ {
            	// 如果但当前数小于第二个数与当前数之间的某个数则把当前数插入到这个数前面
                if arr[_i] > arr[i] {
                    s2++
                	// 取出当前数
                    num := arr[i]
                    // 准备一个新数组
                    var mNums = make([]int, len(arr[_i:i]))
                    // 取出这个数与当前数之间的数
                    copy(mNums, arr[_i:i])
                    // 保留这个数与之前的数的部分再把当前数插入到这后面
                    // 这个数与当前数之间的数拼接当前数之后的数
                    // 新的两部分再拼接到一起
                    arr = append(append(arr[:_i], num), (append(mNums, arr[i+1:]...))...)
                    break
                }
            }
        }
        // fmt.Printf("%v: %vn", i, arr)
    }
    fmt.Printf("s1: %v s2: %vn", s1, s2)
    return arr
}

输出

复制代码
1
2
s1: 17 s2: 99971

插入排序
也可以分为两步关键代码

  • s1 把大于当前数的值往后移动一位
  • s2 把预先记录好的值插入到后移结束后的位置
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func arrSort(arr []int) []int {
    s1 := 0
    s2 := 0
    for i := range arr {
        preIndex := i - 1
        current := arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            s1++
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        }
        s2++
        arr[preIndex+1] = current
    }
    fmt.Printf("s1: %v s2: %vn", s1, s2)
    return arr
}

输出

复制代码
1
2
s1: 2500603989 s2: 100000

可以看出插入排序的步骤执行的次数比我自己写的要多得多
可是实际执行的速度确是完全相反
我单独按照执行次数大致模拟执行了关键代码
我的代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
i := 100
for s1 :=0; s1 < 17; s1++ {
    num := arr[i]
    arr = append([]int{num}, (append(arr[:i], arr[i+1:]...))...)
}
_i := 50
for s2 := 0; s2 < 99971; s2++ {
    num := arr[i]
    var mNums = make([]int, len(arr[_i:i]))
    copy(mNums, arr[_i:i])
    arr = append(append(arr[:_i], num), (append(mNums, arr[i+1:]...))...)
}

耗时12.45秒
插入排序

复制代码
1
2
3
4
5
6
7
for s1 := 0; s1 < 2500603989; s1++ {
    arr[preIndex+1] = arr[preIndex]
}
for s1 := 0; s1 < 100000; s1++ {
    arr[preIndex+1] = 10000
}

耗时2.07秒

到这里可以看得出来，我的算法虽然在操作数的步骤上节省了次数，但是所执行的代码效率却低很多

好吧，还是老老实实的先默写一遍经典的插入排序算法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func arrSort(arr []int) []int {
    for i := 1; i < len(arr); i++ {
        preIndex := i
        for j := i - 1; j >= 0; j-- {
            if arr[j] > arr[preIndex] {
            	// 在我上面的第一种排序中没用到这种互换的写法
            	// 后面在菜鸟教程的算法中学的[狗头]
                arr[preIndex], arr[j] = arr[j], arr[preIndex]
                preIndex--
            } else {
                break
            }
        }
    }
    return arr
}

输出

复制代码
1
2
3
4
5
6
7
start: 1629704397774304200
排序前: [793274 498081 266786 151008 636829 243626 651548 305886 697888 831901] ... [715529 760583 152069 297222 979203 168585 95815 653064 187794 350723]
s1: 2500603989
排序后: [8 20 31 33 34 40 44 49 61 69] ... [999912 999938 999939 999947 999955 999957 999964 999984 999986 999994]
end: 1629704401410920900
duration: 3636616700

耗时3.6秒，还是比插入算法慢
这次默写是在我在分析自己写的算法与插入排序算法之前写的
现在可以初步猜测我默写的算法中与插入算法的区别在于

  1. 插入算法是把当前数取出来前面的数在特定条件下往后移一位，后移结束再把预先取出的值插入到指定位置
  2. 我默写的算法则是每次都做一次前后数互换，虽然不需要后移结束后再做插入。但是显然这种互换操作应该是比只做后移效率要低

用同样的方式测试一下

复制代码
1
2
3
4
5
6
j := 100
preIndex:= 99
for s1 := 0; s1 < 2500603989; s1++ {
    arr[preIndex], arr[j] = arr[j], arr[preIndex]
}

耗时3.6秒，果然

重新默写

复制代码
1
2
3
4
5
6
7
8
9
10
11
func arrSort(arr []int) []int {
    for i, current := range arr {
        preIndex := i - 1
        for ; preIndex >= 0 && arr[preIndex] > current; preIndex-- {
            arr[preIndex+1] = arr[preIndex]
        }
        arr[preIndex+1] = current
    }
    return arr
}

基本一致
最后再用其他语言加深一下印象

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
// javascript
const arrSort = (arr) => {
    for (let i in arr) {
        let preIndex = i - 1
        const current = arr[i]
        for (; preIndex>=0 && arr[preIndex] > current; preIndex--) {
            arr[preIndex+1] = arr[preIndex]
        }
        arr[preIndex+1] = current
    }
    return arr
}
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
// php
function arrSort($arr) {
    foreach ($arr as $i => $current) {
        $preIndex = $i - 1;
        for (; $preIndex >= 0 && $arr[$preIndex] > $current; $preIndex--) {
            $arr[$preIndex+1] = $arr[$preIndex];
        }
        $arr[$preIndex+1] = $current;
    }
    return $arr;
}
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
-- lua
function arrSort(arr)
    for i,current in ipairs(arr) do
        local preIndex = i-1
        while (preIndex >= 1 and arr[preIndex] > current) do
            arr[preIndex+1] = arr[preIndex]
            preIndex = preIndex - 1
        end
        arr[preIndex+1] = current
    end
    return arr
end
复制代码
1
2
3
4
5
6
7
8
9
10
11
# python
def arrSort(arr):
    for i in range(len(arr)):
        preIndex = i - 1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex+1] = current
    return arr

Day3见

[捂脸]，搞这么久，后面的排序算法还是留到Day3吧

最后

以上就是幸福小虾米最近收集整理的关于排序算法-插入排序 #算法学习题目引入设计题目开始学习的全部内容，更多相关排序算法-插入排序内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(80)

相关文章

简单算法——直接插入、冒泡、直接选择
简单算法——直接插入、冒泡、直接选择
排序算法——直接插入排序（insertSort）
排序算法——直接插入排序（insertSort）
插入排序（N个数排序）
插入排序（N个数排序）
JavaScript-冒泡排序、选择排序、插入排序一、冒泡排序二、选择排序三、插入排序
JavaScript-冒泡排序、选择排序、插入排序一、冒泡排序二、选择排序三、插入排序
排序算法-插入排序 #算法学习题目引入设计题目开始学习
排序算法-插入排序 #算法学习题目引入设计题目开始学习
计算机考研专业课一专业课二,考研常识：考研里的专业课一和专业课二分别指什么...
计算机考研专业课一专业课二,考研常识：考研里的专业课一和专业课二分别指什么...
计算机科学不等于数学
计算机科学不等于数学
自我反思/感悟
自我反思/感悟

评论列表共有 0 条评论

立即
投稿
返回
顶部