首页 / 算法 / 【算法导论】插入排序

【算法导论】插入排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法导论】插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1466字，纯文字阅读大概需要3分钟。

内容图文

没办法就是这么没原则，又开了个坑。每天看点书，不管什么书。

1. 需求：

　　输入：n个数的一个序列（a1, a2,  a3……an）

　　输出: 输出序列的一个排列（a1‘, a2‘, a3‘ ……an‘）,满足a1‘ <=  a2‘ <= a3‘ ……<= an‘

2. 图示：

技术分享图片

3. 伪代码 

INSERTION-SORT(A)

for j=2 to A.length
    key = A[j]
    i = j-1//把A[j]插入到有序数组 A[1...j-1].while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i -1
    A[i + 1] = key

 

4. 理解

　　算法导论不愧是本好书啊，看这伪代码的注释多精髓，

　　把 A[j] 插入到有序数组 A[1...j-1]

　　j是从2开始的，也就是说我们第一次就是做两个数的排序，这样就是比较A1 和 A2.，这个就容易了。这样得到A的前两个数A1 A2就是有序的

　　当J = 3的时候，我们要做的就是在  * A1 * A2 * 三个星号中找到A3的位置（因为A1 <= A2 已经确定了），根据就近原则，我们先用A3跟A2比，如果比A3 比 A2小，就再跟A1比（如果A3比A2大，那肯定就比A1大了），在跟，然后得到一个新的有序序列A1 A2 A3

　　当J = 4的时候   我们要做的就是在  * A1 * A2 *  A3  * 四个个星号中找到A4的位置（因为A1 <= A2 <= A3 已经确定了），根据就近原则，先跟A3比，然后A2， A1， 然后得到一个新的有序序列A1 A2 A3 A4

　　以此类推

 

5.代码。因为伪代码的数组下标是从1开始的，所以一些范围判定要改一下

java　　

            //
            java
            void insertionSort(int[] A) {
        for(int j = 1, len =A.length; j < len; j++) {
            int key = A[j];
            int i = j-1;
            while(i > -1 && A[i] > key) {
                A[i+1] = A[i];
                i = i-1;
            }
            A[i+1] = key;
        }
        return A;
}
//    input: 5 4 2 9 4 12 6 8 1 3 35
//    output: 1 2 3 4 4 5 6 8 9 12 35

 

C

            void insertion_sort(int arr[], int len)
{    
    int i, j, key;
    
    for(i = 1; i< len; i++)
    {
        key = arr[i];
        
        j = i - 1;
        
        while(j > -1 && arr[j] > key)
        {
            arr[j+1] = arr[j];
            
            j--;
         }
         
         arr[j+1] = key;
    }
 }

python

            def
             insertion_sort(arr):
    le = len(arr)
    for i in range(1, le):
        key = arr[i]
        j = i - 1

        while j > -1 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1

        arr[j+1] = key

 

 

 

 

 

原文：https://www.cnblogs.com/yeyeck/p/9514371.html

内容总结

以上是互联网集市为您收集整理的【算法导论】插入排序全部内容，希望文章能够帮你解决【算法导论】插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1193513.html

来源：【匿名】