算法回顾系列第二篇:直接插入排序算法
-------------------------------------------
直接插入排序
基本原理:
把n个待排序的元素看成为一个有序表和一个无序表。
开始时有序表中只包含一个元素,无序表中包含有n-1个元素。排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。
程序实现:
public void sort(int[] data) {
int temp;
for(int i=1;i<data.length;i++){//已排序(有序表)的元素个数(第一个元素默认看作已排序).
//有序表的下一个元素(j)如果小于已排序的最大元素(j-1),则交换位置.
//如此向前(j--)与每个元素比较直到找到小于它的元素(data[j]<data[j-1])或者到第一个元素(j>0).
for(int j=i; (j>0)&&(data[j]<data[j-1]); j--){//for的初始化条件j=i只执行1次.
temp = data[j];
data[j] = data[j-1];
data[j-1] = temp;
}
System.out.println("Sort"+i+":"+Arrays.toString(data));//每趟排序后的结果.
}
}
上面程序中:
外层循环i代表已经排序的元素个数(即有序表的元素个数)。从1开始计数,表明第一个元素默认是有序的。
内层循环j代表无序表的第一个元素,j-1即有序表的最后一个元素。两个元素比较:
如果无序表的第一个元素大于有序表的最后一个元素,则结束本趟排序(因为有序表的最后一个元素一定是最大的,无序表的第一个元素如果比它还大,不需要交换位置)。
如果无序表的第一个元素小于有序表的最后一个元素,则交换位置,然后继续与有序表的倒数第二个元素进行比较,直到找到有序表中比它小的元素或者它排在了第一个时,结束本趟排序。
如此直到排序完N-1个元素(第一个元素无需排序)。
性能分析:
1、待排序元素已从小到大排好序(正序)或接近排好序时,所用的比较次数和移动次数较少;
2、当待排序元素已从大到小排好序(逆序)或接近排逆序时,所用的比较次数和移动次数较多。
最坏时间复杂度:O(n^2)
空间复杂度:1。
稳定性:稳定的排序。
分享到:
相关推荐
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
各种基本排序方法(直接插入、希尔、直接选择、冒泡、快速、堆、二路归并)的大致原理和过程、复杂性和稳定性、相应算法的程序段;
数据结构 内部排序算法分析 c语言代码
选择排序,插入排序,希尔排序,堆排序,快速排序,冒泡排序,性能比较。 对于一个随机的数组,可以知道排序所需的比较次数和移动次数。用c++面向对象构建。
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组不同的输入数据作比较;比较...
数据排序中的一种最基本的排序算法 比较次数个移动次数约为n的平凡除4, 时间复杂度约为0(n的平凡)
C语言版的排序方法---插入排序,非常有用的代码,可以实际中使用。
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
希尔排序,直接插入排序,折半插入排序算法的实现,c语言实现希尔排序
易语言算法源码(二分直接插入排序),源码有助于学习易语言算法。@易语言学习论坛。
提供五种排序算法的C++实现方法,输入(待排序元素个数、排序码上界(采用随机生成数组方式)),可选择输出(原始数组、排序后数组、原始数组有序度和无序度、排序过程中数据比较次数与数据移动次数、数组中出现...
数据结构---直接插入排序/快速排序/选择排序/冒泡排序(详细实现算法和性能比较)
使用C语言写的直接插入排序算法,简单易懂,希望对大家学习有帮助