聪明出于勤奋,天才在于积累。——华罗庚
先说下插入排序实现过程:
对要排序的数组,逐个进行处理,与前面的子序列进行比较,让它插入到合适的位置。
时间复杂度:
某一个模块的函数f()的增长率越小,整个程序执行时间增长率就越小,注意这个里面是指的是函数的增长率就是所说的时间复杂度。它是衡量算法好坏的标准之一,时间复杂度越小,算法的效率越高。 现在的电脑都可以满足小程序所需要的内存,如果遇到比较大的数据群,换台更大点的电脑不实际,优化算法才是最合适的选择。
插入排序的时间复杂度是Ο(N^2):
这个很早就知道但是它是怎们来的纳?今天花了点时间,琢磨了一下,不仅仅是翻到了《数据结构与算法》还翻到了《高等数学》,下面是我个人的理解。
插入排序当中,主要通过两个函数f()确定时间复杂度:
1)要插入进去的关键字与已知子序列之间的比较次数;
2)比较完成之后的序列中移动次数;
嗯,可以开始分析了;先分为两种情形:
1)最幸运:所要排序的数组恰好已经是从小到大的排列起来的,比如(1,2,3,5,6,7,8、、)看看上面两个函数结果,比较次数是(N-1),要移动的次数是0;
2) 最倒霉: 所要排序的数组整个都是逆序的,也就是说是从大到小排列的,比如(7,6,4,2,1、、、),推出比较次数的函数表达式用到了等差数列前N项和的公式,应该是(N+2)(N-1)/2,那么后面的移动次数根据同样的原理是(N+4)(N-1)/2;
OK,上面过程当中的最幸运和最倒霉分别对应的是定义时间复杂度时的下限和上限,每次所要排序的数据都是随机的,排序当中的数据出现各种排序方式的概率是相同的,取上面两种情形最小值和最大值的平均,应该是N^2/4,最后对这个表达式求极限,就是插入排序的时间复杂度了。
贴段自己写的插入排序:
1 import java.util.*; 2 3 public class InsertSort { 4 private static int[] Sort(int[] arr) { 5 int i, j; 6 int insertNote = 0;// 要插入的数据 7 int[] array = arr; 8 // 从数组的第二个元素开始循环将数组中的元素插入 9 for (i = 1; i < array.length; i++) { 10 // 设置数组中的第2个元素为第一次循环要插入的数据 11 insertNote = array[i]; 12 j = i - 1; 13 // 比较关键元素与前一个,若成立后退一个位置 14 // 在最幸运的那种情况当中,这个循环语句是不会执行的 15 for (; j >= 0 && insertNote < array[j]; j--) { 16 array[j + 1] = array[j]; 17 } 18 array[j + 1] = insertNote; 19 } 20 System.out.println(Arrays.toString(array)); 21 return array; 22 } 23 24 public static void main(String[] args) { 25 Random random = new Random(); 26 int[] aa = new int[10]; 27 for (int i = 0; i < 10; i++) { 28 aa[i] = Math.abs(random.nextInt() % 100); 29 } 30 InsertSort.Sort(aa); 31 } 32 }
有点自己的感想:
Java已经提供了很好的排序算法的类,只要引用里面的方法就可以了,还有必要在学习排序算法,分析其中的过程吗?
这样程序员就会慢慢和搞数学的画上等号,我自己觉得,在这个方面应该就是外面的各种培训机构所不能做到的地方,也就是这个地方是大学生比其他培训机构具有的优势,可以分析程序背后纯数学的简单问题。
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
21、折半插入排序 22、21、折半插入排序 22、冒泡排序 21、折半插入排序 22、冒泡排序 23、快速排序 21、折半插入排序 22、冒泡排序 23、快速排序 24、简单选择排序 21、折半插入排序 22、冒泡排序 23、快速排序 24...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
此案例难度系数4,属于Scratch高级编程,插入排序相对而言比选择排序和冒泡排序理解起来要难一点,但是还是相对简单的排序,尤其是对少量元素排序的时候,效率较高;综合考查说话、随机数、无限循环(条件循环)、...
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
用函数实现直接插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 ...
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
选择排序和冒泡排序想必大家都很熟悉,但插入排序一般新手却很难理解,插入排序的Java源代码
插入排序 C语言 Insert sort
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
用函数实现折半插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 5...
插入排序,选择排序,基数排序,冒泡排序的C++实现
mips实现插入排序,带详细注释,spim上可运行
经典的快速排序算法,使用分治法思想,使用C++的插入排序,使用算法课程的基础编程。
简单插入排序思想,将一个无序的数组,想象成由两部分组成,一部分为有序列,一部分为无序列,初始时,有序列为数组第一个元素,无序列为第一个元素之后的元素组成。每次从无序列中取第一个数插入到有序列中,有序列...
随机生成小于5000的数 根据操作通过不同的方法排序 泡泡排序 直接插入排序 折半插入排序 希尔排序 直接选择排序 统计时间 比较次数和交换次数 保存为txt文件
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
对半插入排序的思想是:在插入 Ri时(这时R1,R2,…,Ri–1已经排序),取Ki/2 与Ki 进行比较,如果Ki,则Ri只能插在R1与Ri/2之间,故可以在R1与Ri/2–1 之间递归上述过程,否则可以在Ri/2+1与Ri–1之间递归上述...
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht