插入排序的正确性证明 以及各种改进方法.

Slides:



Advertisements
Similar presentations
組員: 4A2I0030 賴孟 佳 4A2I0031 丁楚 倩 4A2I0036 何雅 婷 4A2I0087 蘇靜 雯.
Advertisements

回顾上节课的内容 二分 有序 堆 平方级排序算法简单介绍 交换排序 冒泡排序 插入排序 选择排序.
報告書名:父母會傷人 班級:二技幼四甲 姓名:吳婉如 學號:1A2I0034 指導老師:高家斌
新建本科院校 应用型人才培养若干问题探析 张德江.
媽,我們真的不一樣 青少年期與中年期 老師: 趙品淳老師 組員: 胡珮玟4A1I0006 馬菀謙4A1I0040
Trie 魏楚.
引導者的角色 組別:第5組 4A1I0003 劉芷媛 4A1I0004 陳安琪 4A1I0014 陳佳瑩 4A1I0046 葉倢茹
氣喘 組別:第一組 組員: 4A 蔡易儒 4A1I0026 鄭筠蒨 4A1I0034 韓宜瑄 4A1I0035 劉毓眉
情緒與壓力管理─背部舒緩 指導老師:彭易璟 第六組組員:會資三乙 499A0047 謝宛霖 會資三乙 499A0019 吳汶諭
班級:幼保三乙 姓名:吳婉綺4a1i0062 林彤4a1i0066 林妤婕4a1i0095 指導老師:趙品淳老師
班級:二幼三甲 姓名:郭小瑄 、 詹淑評 學號:1A2I0029 、1A2I0025
指導老師:楊淑娥 組別:第一組 成員:劉怡萱4a0i0066 吳珮瑜4a0i0070 林秋如4a0i0075 陳婉婷4a0i0076
組員:4A140013張瓊云 4A1I0039石宜芬 4A1I0909許峻綱 指導老師:王立杰老師
指導老師:陳韻如 姓名:吳宜珊 學號:4A0I0911 班級:幼保二乙
主題:百日咳 班級:幼保二乙 姓名:翁子文 學號:4A0I0071 指導老師:陳韻如
傳統童玩遊戲創新 組別:第八組 班級:幼保二甲 組員: 4A0I0005柯舒涵 4A0I0011謝孟真
第十章 排序 排序定义——将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列叫~ 排序分类 按待排序记录所在位置
数据结构 第10章 内部排序.
常宝宝 北京大学计算机科学与技术系 数据结构(七) 常宝宝 北京大学计算机科学与技术系
C语言程序设计.
<<软件技术基础>>
第十章 内部排序 £10.1 概述 £10.5 归并排序 £10.2 插入排序 £10.6 基数排序 £10.3 快速排序
数据结构 第七章 排序.
助教:李伟力 电子科学与技术系 数据结构第二次习题课 助教:李伟力 电子科学与技术系
第9章 内部排序 概述 插入排序 (直接插入、折半插入、表插入排序、希尔排序) 交换排序 (起泡排序、快速排序)
第10章 排序.
第九章 排序 课前导学 9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序 9.4 选择类排序 9.5 归并排序
行為改變技術 班級:幼保二甲 組員: 4A10H081 蘇靖婷 4A1I0014 陳佳瑩 4A1I0023 尤秀惠 4A1I0074 邱乃晏 指導老師: 楊淑娥 老師.
第八讲 排序算法 —— C++ 实现.
定期定額該積極還是穩健 積極型獲利高,穩健型風險低 財富想倍增,就要選擇波動愈大的積極型基金,愈
心 臟 病 指導老師:陳韻如 班級:幼保二乙 姓名:陳怡伶 學號:4a0i0910.
考试情况 考试安排 试卷题型及预估分值 2013年12月28日上午8:30~10:30,东区5401,5402教室 闭卷笔试
指導老師:陳韻如 班級:幼保二甲 姓名:林靜宜 學號:4A0I0033
第六章 猪场管理 目的:在了解现代养猪生产及其模式的基础上,掌握养猪生产工艺流程设计方法,同时熟悉猪场的现场组织和管理方法。
第十章 内部排序.
10.1 概述 插入排序 快速排序 堆排序 归并排序 基数排序
10.1、基本概念 10.2、插入排序 10.3、快速排序 10.4、选择排序 10.5、归并排序 10.6、基数排序 10.7、讨论
主讲人: 吕敏 { } Spring 2012 ,USTC 算法基础 主讲人: 吕敏 { } Spring 2012 ,USTC.
第十章 排序 10.1排序的基本概念 10.2简单排序方法(复杂度 O(n2))
第十章 内部排序.
本章重点难点 重点:插入排序、快速排序、选择排序、归并排序、基数排序的思想和算法。
第九章 排序 9.1排序的基本概念 9.2简单排序方法(复杂度 O(n2)) 9.3先进排序方法(复杂度 O(nLogn))
Chapter 2 Program Performance
第2讲 绪论(二).
第9章 排序 9.1 排序的基本概念 9.2 插入排序 9.3 选择排序 9.4 交换排序 9.5 归并排序 9.6 基数排序.
数据结构 复习课 王彦 博士,副教授
并行计算 Parallel Computing
Cyclic Hanoi问题 李凯旭.
递归与分治策略.
第九章 排序 (Sort)
数据结构 本 章 说 明 10.1 概 述 10.2 插入排序 10.3 快速排序 10.4 堆 排 序 10.5 归并排序
Chap3 Linked List 鏈結串列.
党员干部要争做社会主义 社会公德的表率 党员干部要争做 社会公德的表率 中共河南省委党校 周海涛.
Chapter14 Divide and Conquer
第九章 排序 概述 插入排序 交换排序 选择排序 归并排序 *基数排序 *外排序.
第十章内部排序 概述 插入排序 快速排序 选择排序 归并排序 基数排序.
计算机软件技术基础 数据结构与算法(5).
顺序表的删除.
中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥) 2004年12月
算法基础 上机实验 1 学 期: 2016 (秋).
3.16 枚举算法及其程序实现 ——数组的作用.
算法基础 上机实验 1 学 期: 2015 (秋).
主題四: 教育發展與大學學群 報告人: 張明敏老師.
第九章 排序 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
排序查找 概述 插入排序 交换排序 选择排序 归并排序 主讲:朱佳 博士.
第10章 排序 排序的基本概念 插入排序 选择排序 交换排序归并排序 基数排序 性能比较 主要知识点.
基于列存储的RDF数据管理 朱敏
主讲人: 吕敏 { } Spring 2012 ,USTC 算法基础 主讲人: 吕敏 { } Spring 2012 ,USTC.
算法的基本思想: 第6章 内部排序 6.2 气泡排序 将待排序的记录看作是竖着排列的“气泡”,关键字较小 的记录比较轻,从而要往上浮。
第二章 线性表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
Presentation transcript:

插入排序的正确性证明 以及各种改进方法

插入排序概述 最符合人类思维的简单排序算法 1 3 4 6 7 5 2 1 3 4 5 6 7 2 1 2 3 4 5 6 7 1 3 4 6 7 5 2 1 3 4 5 6 7 2 每一个外循环是将A[i]插入位置,内循环腾出位置 1 2 3 4 5 6 7

j (1) 1 3 4 5 6 7 2 X=2 (2) 1 3 4 5 6 7 7 1 3 4 5 6 6 7 (3) 1 3 4 5 5 6 7 1 3 4 4 5 6 7 1 3 3 4 5 6 7 (4) 1 2 3 4 5 6 7

(1) (2) (3) (4)

(1) (2) (3) (4)

插入排序的效率? 非递归排序算法:冒泡排序、选择排序 < 插入排序 递归算法:归并排序,快速排序 影响插入排序效率的主要因素: 1、比较大小 O(n^2) 2、数组元素移动 O(n^2) → ?

减少比较次数 内循环二分查找 1 3 4 5 6 7 2 O(n^2)+O(nlogn)

减少移动次数 考虑链表 支持快速访问元素的链表? 1 → 3 → 4 → 5 → 6 → 7 2 O(n)+O(n^2)

跳跃表 skip list 5 ? ? ? 从最高层开始查找,依次下降 支持O(logn)查询 用跳跃表优化插入排序,时间复杂度可以和归并和快排媲美

谢尔排序 玄学优化? 让元素交换大步跳跃! 一个好的跳跃序列的选取,决定了谢尔排序的速度 可以达到O(n(logn)^2)甚至更好