直接插入排序 订阅
直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。 [1] 展开全文
直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。 [1]
信息
外文名
Straight Insertion Sort
空间复杂度
O(1)
类    型
插入排序
中文名
直接插入排序
时间复杂度
O(n^2)
稳定性
稳定
直接插入排序简介
在日常生活中,经常碰到这样一类排序问题:把新的数据插入到已经排好的数据列中。例如:一组从小到大排好顺序的数据列{1,2,3,4,5,6,7,9,10},通常称之为有序列,我们用序号1,2,3,…表示数据的位置,欲把一个新的数据8插入到上述序列中。完成这个工作的步骤:①确定数据“8”在原有序列中应该占有的位置序号。数据“8”所处的位置应满足小于或等于该位置右边所有的数据,大于其左边位置上所有的数据。②将这个位置空出来,将数据“8”插进去。直接插入排序(straight insertion sort)的做法是:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止。 [1]  待排序记录 R1,R2,… ,Rn–1, Rn第一步:R1第二步:(R1 ), R2第三步:(R1 , R2), R3……第 j 步:(R1,R2,… ,Rj–1), Rj……第 n 步: (R1,R2,… ,Rn–1), Rn.例:j=5原有序表中关键词比Rj大的记录数:dj比较次数:dj+1 移动次数: dj+2算法 InsertSort (R,n)FOR j=2 TO n DO( //每次将Rj插入到有序表R1,…,Rj–1中K←Kj. R←Rj. i←j-1.WHILE (i>0) AND (Ki>K) DO(Ri+1←Ri.i←i-1.)Ri+1←R.)算法InsertSortA( R, s, e )//引入虚拟记录,Ks-1≤min{Ki| s≤i≤e}ISA1 [逐一排序]FOR j=s+1 TO e DO( i←j-1.K←Kj. R←Rj .WHILE K
收起全文
精华内容
下载资源
问答
  • 直接插入排序

    千次阅读 2017-05-07 12:02:54
    直接插入排序

            直接插入排序的基本思想:将一个记录插入到已经排好序的记录中,从而得到一个有序的,记录数增一的有序表.

            核心代码:

    public static void insertSort(int[] data){
    		for(int i=1; i<data.length; i++){
    			if(data[i]<data[i-1]){ // 如果当前数比前一个数小
    				int cur = data[i]; // 把当前数记录下来
    				int j = i - 1; // 用j来记录当前数的前一个数的下标
    				for(; j>=0&&cur<data[j]; j--){
    					data[j+1] = data[j];
    				}
    				data[++j] = cur; // j要记得++
    			}
    		}
    	}
            完整代码:

    package cn.ccnu.sort;
    
    public class Insert {
    	public static void insertSort(int[] data){
    		for(int i=1; i<data.length; i++){
    			if(data[i]<data[i-1]){ // 如果当前数比前一个数小
    				int cur = data[i]; // 把当前数记录下来
    				int j = i - 1; // 用j来记录当前数的前一个数的下标
    				for(; j>=0&&cur<data[j]; j--){
    					data[j+1] = data[j];
    				}
    				data[++j] = cur; // j要记得++
    			}
    		}
    	}
    	
    	public static void main(String[] args) {
    		int[] data = {10, 3, 12, 5, 4, 9, 4, 7, 6};
    		insertSort(data);
    		for (int i : data) {
    			System.out.print(i + "  ");
    		}
    	}
    }

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20