排序基本思想:
从第二个元素开始,用这个元素依次与其前面的每一个元素比较,如大于该元素则将改元素向后移动一个位置直到找到比这个元素小的位置(或者到第一个结束)将这个元素放到改元素的后面即完成排序
算法图示
java代码实现
package com.leiht.sort;
/**
* 直接排序算法java简单实现
*
* @author Leiht
* @date 2015-11-10
*/
public class SortDirect {
public static void main(String[] args) {
int[] numbers = { 56, 45, 78, 67, 99, 13, 34, 49, 55, 34, 12, 77, 1 };
System.out.println("排序之前:");
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + " ");
}
// 直接插入排序
for(int i = 1; i < numbers.length; i++) {
int temp = numbers[i];
int j;
//从第i-1个,即前一个开始往前,如果比当前数据(temp)大,则向后移动一个位置,
//直到比当前小,跳出循环
for(j = i-1; j >= 0; j--) {
if(numbers[j] > temp) {
numbers[j+1] = numbers[j];
}else {
break;
}
}
//将当前数据temp放到J+1的位置,J位置数据比当前数据小
numbers[j+1] = temp;
}
System.out.println();
System.out.println("排序之后:");
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + " ");
}
}
}
分析(稳定性与时间复杂度)
直接插入排序是稳定的排序,可以理解为当两个元素相同的时候不会交换两个元素的位置
文件初态不同时,直接插入排序所耗费的时间有很大差异。若文件初态为正序,则每个待插入的记录只需要比较一次就能够找到合适的位置插入,故算法的时间复杂度为O(n),这时最好的情况。若初态为反序,则第i个待插入记录需要比较i+1次才能找到合适位置插入,故时间复杂度为O(n2),这时最坏的情况。
直接插入排序的平均时间复杂度为O(n2)
- 大小: 54.8 KB
分享到:
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
用java对常用排序算法进行分析与实现.包含: 插入排序 直接插入排序、希尔排序 • 选择排序 简单选择排序、堆排序 • 交换排序 冒泡排序、快速排序 • 归并排序 • 基数排序
数据结构 内部排序算法分析 c语言代码
直接插入排序通过键盘输入建立数组,再经过直接插入排序算法进行排序。在VS上X64编译通过。直接插入排序算法理论参考《算法导论》和张琨的《数据结构与算法分析(C++语言版)》
1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组不同的输入数据作比较;比较...
各种经典的排序算法C分析与实现:选择排序 ,直接插入排序,冒泡排序,希尔排序,快速排序,堆排序 面试必备哦!!
试通过随机数据比较堆排序、直接插入排序算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加...
直接插入排序,折半插入排序,2—路插入排序和表插入排序;希尔排序和链式基数排序;起泡排序,快速排序,归并排序;简单选择排序,树形选择排序和堆排序。 通过输入不同的数据量和数据大小正序,逆序和乱序情况比较...
利用随机函数产生30000个随机整数,利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序,并且 (1) 统计每一种排序上机所花费的时间。 (2) 统计在完全正序,完全逆序情况下记录的比较...
直接插入排序 前面文章已经讲完了交换类排序,接下来开始学习插入类排序。顾名思义,所谓插入排序指我们会为每一个数据安排一个适合它的位置并将其插入,直到所有数据就位则排序完成。 直接插入法便是插入排序的典型...
主要介绍了Python实现的直接插入排序算法,结合实例形式分析了Python直接插入排序算法的定义与使用相关操作技巧,代码备有较为详尽的注释便于理解,需要的朋友可以参考下
算法老师要求做的,希望对学弟学妹有所帮助,里面包含了性能分析对比图
七种排序算法(包括直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,归并排序) 还有两道题 1./*设计并实现一个有效的对n个整数重排的算法,使得所有负数位于非负数之前,给出算法的性能...
1、通过修改程序,实现程序在要求的数据量下求出以下六种内部排序算法的移动次数和比较次数:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。 2、输入的数据量分别按照正序、逆序、随机顺序的不同...
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
本程序实现各种排序算法并分析与比较 直接插入排序, SHELL排序,冒泡排序,快速排序,简单选择排序,堆排序,归并排序
C语言排序中的各种方法(冒泡、插入法、选择排序等)算法分析
(1) 对6种常用内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序 (2) 待排序的表长不小于100,其中数据要用伪随机数产生,至少用5组不同的输入数据做比较 (3) 比较...
他们分别是:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序;2. 待排序表元素的关键字为整型。使用正序、逆序和不同程度的打乱获得不同的数据做测试比较。比较的指标为关键字参加比较的次数和...
主要介绍了C语言基本排序算法之插入排序与直接选择排序实现方法,结合具体实例形式分析了插入排序与直接选择排序的定义、使用方法及相关注意事项,需要的朋友可以参考下