精华内容
下载资源
问答
  • 插入排序的原理在于,将数字序列 d 分为两个序列(前者有序,后无序),每遍历一个元素就将该元素插入到前部份的合适位置。 插入排序算法原理很容易理解,实现步骤如下: i = 0,将 d[i] 插入到 i 之前的...

    插入排序的原理在于,将数字序列 d 分为两个序列(前者有序,后者无序),每遍历一个元素就将该元素插入到前半部份的合适位置。

    插入排序的算法原理很容易理解,实现步骤如下:

    1. i = 0,将 d[i] 插入到 i 之前的有序序列之中;
    2. i = i + 1,将 d[i] 插入到 i 之前的有序序列之中,插入的过程为将自己与自己之前的元素进行比较,如果自己比其前面的元素都大,则什么也不用做;否则就插入到合适的位置;
    3. 终止条件: i = n - 1。

    插入排序的时间复杂度(平均条件下)为 O(n * n)。

    实现代码如下:

    void insertSort(double *dataIn, int sizeIn)
    {/* 2012/08/23, by wbprime@myopera.com */  
        for (int i = 0; i < sizeIn; ++i) {
            for (int j = 1; j < i && dataIn[i] < dataIn[i-j]; ++j) {
                swap(dataIn[i], dataIn[i-j]);
            }
        }
    }
    展开全文
  • 查找指定元素是否在前部分序列,不在则查找是否在后部分序列 # 2.若元素在序列中,则将序列再次分割,重复1 # 3.知道找到满足条件的记录,后子序列不存在,即不包含元素 import random Range = 10 Length = 5...

    前提:二分法查找

    # 二分法查找,又称对半查找,是一种较为高效的简单查找方法,且要求元素采用顺序存储结构
    # 原理:
    # 1.查找指定元素是否在前半部分序列,不在则查找是否在后半部分序列
    # 2.若元素在序列中,则将序列再次分割,重复1
    # 3.知道找到满足条件的记录,后者子序列不存在,即不包含元素
    
    import random
    Range = 10
    Length = 5
    dst = 5
    flag = 0
    
    list = random.sample(range(Range),Length)    #在指定序列中随机获取指定长度片段
    list.sort()
    print('sorted list:',list)
    
    low = 0
    high = Length-1
    
    while low<=high:
        mid = (low+high)//2
        if list[mid] == dst:
            flag = 1
            break
        elif list[mid] > dst:
            high = mid - 1
        elif list[mid] < dst:
            low = mid + 1
    
    if flag:
        print('5在第',mid+1,'位')
    else:
        print("错误查询")
    
    
    

    二分法插入排序

    # 二分法插入排序是在插入排序的基础上,使用二分法查找将元素插入的方法
    # 基本原理:(升序)
    # 1.将元素依次放入有序序列中
    # 2.取出待排序元素,与有序序列的前半段进行比较
    # 3.缩小有序序列范围,进一步划分比较,直至范围内仅有1或2个数字
    # 4.将插入值与范围进行比较
    # 3.重复实现升序
    # 实现过程:外层循环控制循环次数,中层循环实现有序排列,内层循环实现查找插入
    import random
    
    # 生成序列
    Range = 10
    Length = 5
    list = random.sample(range(Range),Length)
    print('before sort:',list)
    
    # 元素插入
    for i in range(1,Length):            #从第2个元素开始,插入到前一部分元素中
        beg,end = 0,i-1                  #定义插入范围
        mid = (beg + end) // 2           #定义二分/中间边界
    
        while beg < end:                #当边界顺序时,进行二分比较
            mid = (beg + end) // 2
            if mid == beg:               #如果中间值与边界相等,则边界已确定,结束二分
                break
            #在确定中间与边界不相等时,对边界继续缩小
            if list[i] == list[mid]:
                break
            elif list[i]<list[mid]:
                end = mid
            else:
                beg = mid
    
        #首先确定是否因为找到同值而提前终止
        if list[i] == list[mid]:
            list.insert(mid, list[i])
            list.pop(i + 1)
        else:
            if beg == end:              #如果范围内仅仅有一个值
                if list[i] < list[beg]:
                    list.insert(beg,list[i])
                else:
                    list.insert(beg+1, list[i])
                list.pop(i + 1)
            elif beg < end:             #如果范围内有两值
                if list[i] < list[beg]:
                    list.insert(beg,list[i])
                elif list[i] < list[end]:
                    list.insert(end, list[i])
                else:
                    list.insert(end+1, list[i])
                list.pop(i + 1)
            else:
                print("wrong, start at ",beg,', and end with ',end)
    
    print('after sort:',list)
    

    二分插入排序的原理较为简单,但是二分边界的确定以及范围比较的实现较为繁琐

    展开全文
  • 每次对N有序子数组进行 插入排序 ,然后减少N,重复对有序子数组进行 插入排序,直到N为1 对于中等数量级,通常只慢高级排序一点,实现简单,适合嵌入式开发 归并排序 分治策略:先排序左部分,再排序右部分,...

    初级排序

    选择排序

    不断选择剩余元素的最小者

    $O(N^2)$

    插入排序

    将后续元素插入到已经有序的元素适当的位置

    $O(N^2)$

    希尔排序

    每次对N有序子数组进行 插入排序 ,然后减少N,重复对有序子数组进行 插入排序,直到N为1

    对于中等数量级,通常只慢高级排序一点,实现简单,适合嵌入式开发

    归并排序

    分治策略:先排序左半部分,再排序右半部分,最后合并,合并需要使用额外N控件的中间数组

    $O(NlogN)$

    快速排序

    分治策略:将数组分为三部分,比元素v小的元素,v元素,比v大的元素,可以理解这是一种入座算法,通过不断让元素入座(同时保证左子树都小于右子树),实现整体数组有序。

    注意需要事先Shuffle,不然最多需要 $N^2/2$ 比较

    优化:熵最优(大量重复元素情况),小数组使用插入排序,三取样(切分数尽量为中位数)

    优先队列

    适用于流式输入,插入通过上浮,删除通过下沉来实现有序

    堆排序,先下沉后上浮

    https://en.wikipedia.org/wiki/Sorting_algorithm

    转载于:https://www.cnblogs.com/enigmaxp/p/9635465.html

    展开全文
  • 上篇已经介绍了插入排序算法,但它的不足也很明显:虽然插入排序对几乎已经排好序的数据进行操作时,效率很高,可以达到线性排序的效率,但当对乱序数据进行操作时,效率还是较低,相信个世纪前的美国计算机科学家...

    上篇已经介绍了插入排序算法,但它的不足也很明显:虽然插入排序对几乎已经排好序的数据进行操作时,效率很高,可以达到线性排序的效率,但当对乱序数据进行操作时,效率还是较低,相信半个世纪前的美国计算机科学家D.L.shell也为此而苦恼着...

    shell排序,也称递减增量排序法,1959年以其设计者D.L.shell 命名的排序算法。

    算法思想:

    比较、移动无序数组中相隔距离较远的数,每进行一组比较,可以避免多个元素交换,减少在插入排序中数据每次移动都要进行多次的无关移动所带来的大量额外开销。是指上,就是一种分组插入的方法。光说不练空把式,下面以升序无序数组{24,5,3,8,67,12,6,11,2,9,32,56,13,10,19,37,25}为例,演示希尔排序:


    经过这组排序出来,小数已经开始趋于前方,大数趋于后方

    最后在以间隔为一进行排序,其实就是普通的插入排序了,这里就忽略不写了,下面是算法的Java实现:


    public static void sort(int[] arr){
    
    		int h = 1;
    		while(h < arr.length/3) h = 3*h + 1;
    		while(h >= 1){
    			for(int i=h;i=0 && arr[j]>temp){
    					arr[j+h] = arr[j];
    					j -= h;
    				}
    				arr[j+h] = temp;
    			}
    			h /= 3;
    		}
    	}
    

    个人完整代码请参见github:https://github.com/WangHuaJie/algrethoms/blob/master/shellSort.java

    未完待续~

    reference:

    1.《Algorithms》(中文版)Robert Sedgewick , Kevin Wayne 著,谢路云 译  P162~P165

    2.百度百科:http://baike.baidu.com/link?url=5Lwhl06PXHN1M_ATPjz_g9LBZjAhsqXWNFk_y5tm5Wn-o5H8wj5NufXYKr0NdzXN

    3.维基百科:http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F


    /*
      1.本文为原创技术文章,首发CSDN个人站点(http://blog.csdn.net/u011429947)。
      2.所做文章仅用于相互学习和交流,转载请注明作者及出处。
      3.由于个人能力有限,错误之处在所难免,如能指出,非常感谢。
    */
    



    展开全文
  • 4.1.2 插入排序 100 4.1.3 排序题与sort函数的应用 101 4.2 散列 106 4.2.1 散列的定义与整数散列 106 4.2.2 字符串hash初步 109 4.3 递归 111 4.3.1 分治 111 4.3.2 递归 112 4.4 贪心 118 4.4.1 简单贪心 118 ...
  • 2.1.35不均匀的概率分布。...插入排序时高斯分布时间两倍于泊松分布、几何分布、离散分布。选择排序时高斯分布约倍于泊松分布、几何分布、离散分布。后三时间相当,但比起选择排序性能要差6...
  • 严蔚敏:数据结构题集(C语言版)

    热门讨论 2009-09-02 18:38:34
    10.2.1 直接插入排序 10.2.2 其他插入排序 10.2.3 希尔排序 10.3 快速排序 10.4 选择排序 10.4.1 简单选择排序 10.4.2 树形选择排序 10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.6.1 多关键字的排序 10.6.2 链式...
  • 61 第4章 数据结构 64 4.1 线性表 64 4.1.1 链表 64 4.1.2 栈 65 4.1.3 队列 65 4.1.4 块状链表 66 4.2 集合 67 4.2.1 散列表 67 4.2.2 并查集 69 4.3 排序 71 4.3.1 朴素排序算法 71 4.3.1.1 插入排序 71 4.3.1.2 ...
  • 10.2.2 其他插入排序 10.2.3 希尔排序 10.3 快速排序 10.4 选择排序 10.4.1 简单选择排序 10.4.2 树形选择排序 10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.6.1 多关键字的排序 10.6.2 链式基数排序 10.7 各种...
  • 数据结构实验

    2012-04-13 09:55:47
    实验7:至少三种排序算法的程序实现 (第十六周星期三7、8节) 一、 实验目的 1.掌握简单插入排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。 2.对各种查找、排序技术的时间、空间复杂性有...
  • 4.2 常用数组排序算法 实例099 使用选择排序法对一维数组进行排序 实例100 使用冒泡排序法对一维数组进行排序 实例101 使用快速排序法对一维数组进行排序 实例102 使用直接插入法对一维数组进行排序 实例103 ...
  • 4.2 常用数组排序算法 实例099 使用选择排序法对一维数组进行排序 实例100 使用冒泡排序法对一维数组进行排序 实例101 使用快速排序法对一维数组进行排序 实例102 使用直接插入法对一维数组进行排序 实例103 ...
  • 4.2 常用数组排序算法 实例099 使用选择排序法对一维数组进行排序 实例100 使用冒泡排序法对一维数组进行排序 实例101 使用快速排序法对一维数组进行排序 实例102 使用直接插入法对一维数组进行排序 实例103 ...
  • 4.2 常用数组排序算法 117 实例099 使用选择排序法对一维数组进行排序 117 实例100 使用冒泡排序法对一维数组进行排序 118 实例101 使用快速排序法对一维数组进行排序 119 实例102 使用直接插入法对一维数组进行排序...
  • 下一节排序中,有序的含义也是如此。 对于长度为n的有序线性表,利用二分法查找元素X的过程如下: 步骤1:将X与线性表的中间项比较; 步骤2:如果X的值与中间项的值相等,则查找成功,结束查找; 步骤3:如果X小于...
  • 实例044 插入排序法 实例045 归并排序法 2.6 算法应用 实例046 算法应用——百钱买百鸡 实例047 算法应用——韩信点兵 实例048 算法应用——斐波那契数列 实例049 算法应用——水仙花数 实例050 算法应用...
  •  本书适合Visual C++的初学,如高校学生、求职人员作为练习、速查、学习使用,也适合Visual C++程序员参考、查阅。 目 录 第1篇 编程基础 第1章 开发环境 1.1 工程创建 实例001 如何创建基于对话框的MFC...
  •  本书适合Visual C++的初学,如高校学生、求职人员作为练习、速查、学习使用,也适合Visual C++程序员参考、查阅。 目 录 第1篇 编程基础 第1章 开发环境 1.1 工程创建 实例001 如何创建基于对话框的MFC...
  • 排序:交换类、插入类、选择类 树、二叉树、图:深度优先(DFS)、广度优先(BFS) 递归 分治 滑窗 三大牛逼算法:回溯、贪心、动态规划(DP) 怎么学? 刷题 leetcode力扣官网,覆盖简单、中等、困难,刷够300题...
  • 详细设计: 整个系统除了主函数外,另外还有14个函数,实现八大功能:输入功能、显示功能、查找功能、排序功能、插入功能、保存功能、读取功能。各个函数的详细设计说明分别如下: 主函数 main() 利用无限次循环...
  • 2.2.2 时间戳排序算法 30 2.3 多版本并发控制技术 31 2.3.1 基于时间戳排序的多版本技术 31 2.3.2 使用验证锁的多版本两阶段加锁 32 2.4 确认(乐观的)并发控制技术 32 2.5 数据项粒度和多粒度...
  • 同时,无论插入还是擦除,其都能始终保持指向未擦除元素的永久指针。 dynamic_bitset:C++17 的动态位集合,只有头文件。 Forest:实现了AVL、二进制搜索、KD和四叉树的模板库。 Hashmaps: C++中开放寻址哈希表...
  • CruiseYoung提供的带有详细书签的电子书籍目录 ... Visual C++ 2010入门经典(第5版) 基本信息 原书名: Ivor Horton's Beginning Visual C++ 2010 原出版社: Wrox 作者: (美)Ivor Horton [作译者介绍] ...
  • CruiseYoung提供的带有详细书签的电子书籍目录 ... 该资料是《Visual C++ 2010入门经典(第5版)》的源代码及课后练习答案 对应的书籍资料见: Visual C++ 2010入门经典(第5版) ...原书名: Ivor Horton's Beginning ...
  • Visual C++ 2008入门经典--详细书签版

    热门讨论 2013-02-02 16:07:15
     本书系编程语言先驱ivor horton的经典之作,是c++编程方面最畅销的图书品种之一,不仅涵盖了visual c++ 2008编程知识,还全面介绍了标准c++语言和c++/cli。本书延续了ivor horton讲解编程语言的独特方法,从中...
  •  本书系编程语言先驱ivor horton的经典之作,是c++编程方面最畅销的图书品种之一,不仅涵盖了visual c++ 2008编程知识,还全面介绍了标准c++语言和c++/cli。本书延续了ivor horton讲解编程语言的独特方法,从中...
  • 实例022 在表格中插入宠物照片 38 实例023 Dreamweaver创建表单 40 实例024 Dreamweaver中创建和附加CSS样式 42 实例025 Dreamweaver控制弹出信息 45 实例026 Dreamweaver控制浏览器的窗口 46 实例027 通过...
  • 实例022 在表格中插入宠物照片 38 实例023 Dreamweaver创建表单 40 实例024 Dreamweaver中创建和附加CSS样式 42 实例025 Dreamweaver控制弹出信息 45 实例026 Dreamweaver控制浏览器的窗口 46 实例027 通过...
  • 出于类似的考虑,在本人译作的译文中,亦常尝试着,采用插入空格、短逗号(正常逗号只用于 独立句但不是完整句 的场合)、增加虚词等‘不规范’的辅助方式,来尽量避免 译意的模糊性和二义性,提高译文的可读性。...

空空如也

空空如也

1 2
收藏数 32
精华内容 12
关键字:

者半插入排序算法