精华内容
下载资源
问答
  • 直接插入排序算法

    热门讨论 2016-11-20 20:13:33
    直接插入排序算法

            直接插入排序是一种简单的排序,以第i个记录为岗哨,将它插入到一个已经排好序的有序表中,从而得到一个新的、记录数增加1的有序表。

             直接插入排序的算法如下:

    void StraightInsertSort(List R,int n)
    {
    	int i,j;						
    	for(i=2;i<=n;i++)				//从第二个记录进行插入
    	{
    		R[0]=R[i];					//第i个记录复制为岗哨,在while循环里面种“监视”数组下标变量j是否越界
    		j=i-1;
    		while(R[0].key<R[j].key)	//与岗哨比较,直至键值不大于岗哨键值
    		{
    			R[j+1]=R[j];
    			j--;
    		}
    		R[j+1]=R[0];				//将第i个记录插入到序列中
    	}
    }



    展开全文
  • 直接插入排序算法演示;直接插入排序算法演示;直接插入排序算法演示;直接插入排序算法演示;直接插入排序算法演示;直接插入排序算法演示;直接插入排序算法演示;直接插入排序算法演示;直接插入排序算法演示;直接插入...
  • 主要介绍了Python实现的直接插入排序算法,结合实例形式分析了Python直接插入排序算法的定义与使用相关操作技巧,代码备有较为详尽的注释便于理解,需要的朋友可以参考下
  • 直接插入排序一、直接插入排序相关知识二、直接插入排序算法的执行流程三、具体代码与运行截图 一、直接插入排序相关知识 直接插入排序的思想是指:每次将一个待排序的元素按大小插入到前面己排好序的有序表中,直到...

    一、直接插入排序相关知识

    直接插入排序的思想是指:每次将一个待排序的元素按大小插入到前面己排好序的有序表中,直到全部元素排序完成。最开始默认当前有序表的第0个元素成为一个已经排序好的有序的子数组 直接插入排序的时间复杂度为O( n2 )。

    二、直接插入排序算法的执行流程

    假设待排序的序列是:38,55,-10,49,67,78,65,38,77,99。

    假设初始的有序 序列是 有序表的第0个元素:38 。其他的都是未排序的。

    第一次比较:

    i=1;

    因为0个元素以及是排序好的 所以从第一个元素开始比较,当前元素(i)是否小于前一个元素(i-1) 此时 55(i) 大于 38(i-1) 则直接进行下一轮循环。
    此时有序表 已排序好的为:38 55 未排序好的为: -10,49,67,78,65,38,77,99

    第二次比较:

    i=2;

    当前元素(i) 是否小于前一个元素(i-1) 此时-10(i)小于 55(i-1) 当前有序表已排序好的为:38,55。
    当前目标是 确定 当前元素i(-10)在有序表中的位置
    首先把当前元素arr[i] 放入 temp 中(temp 充当一个“哨兵”的角色)
    然后进入 第二层的循环。
    第二层的循环变量变量名为j 。

    假设 此时的有序表是升序排列的 所以第二层循环 j 初始值 是 i-1(1)。 因为此刻有序表的最后一个元素下标为 i-1 (1)

    从有序表的 最后一个元素开始找 找到有序表中第一个小于temp 变量的元素(此时a[i] 已经赋值给temp 了)为止 即 a[j]>temp;在循环内进行元素后移的操作 a[j+1]=a[j]

    此刻j = 1 a[j] 为 55 temp 为 -10

    55 大于 temp 则元素后移 a[j+1]=a[j](a[2]=a[1] ) 此时序列为: 38 55 55 49,67,78,65,38,77,99 继续第二层循环。

    此刻j=0; a[j] 为 38 temp 为-10
    38 大于 temp 则元素后移 a[j+1] = a[j] (a[1]=a[0]) 此时的序列为:38 38 55 49,67,78,65,38,77,99 继续第二层循环。

    因为 现在j在0的基础上 减1 (- - ) 所以 j 当前的值为:-1 不满足j>=0 条件 然后跳出循环
    j+1 即 -1 + 1 则为 0 所以 执行 a[j+1] = temp 就是 执行 a[0] = temp;(temp 等于 -10)

    此时序列为: -10 ,38, 55, 49,67,78,65,38,77,99。

    第三次比较

    i=3
    当前元素(i) 是否小于前一个元素(i-1) 此时55(i)小于 49(i-1) 当前有序表已排序好的为:-10,38,55。
    情况和第二次比较过程类似 不再赘述 比较完成之后的序列为:
    -10 ,38, 49, 55,67,78,65,38,77,99。

    第四次比较:

    i=4
    当前元素(i) 是否小于前一个元素(i-1) 此时67(i)大于 55(i-1) 则直接进行下一轮循环。
    当前有序表已排序好的为:-10 ,38, 49, 55,67,78,65,38,77,99。

    第五次比较
    i = 5
    当前元素(i) 是否小于前一个元素(i-1) 此时78(i)大于 67(i-1) 则直接进行下一轮循环。
    当前有序表已排序好的为:-10 ,38, 49, 55,67,78,65,38,77,99。

    第六次比较
    i = 6
    当前元素(i) 是否小于前一个元素(i-1) 此时65(i)小于 78(i-1)
    当前有序表已排序好的为:-10 ,38, 49, 55,67,78,65,38,77,99。
    情况和第二次比较过程类似 不再赘述 比较完成之后的序列为:
    -10 ,38, 49, 55,65,67,78,38,77,99。

    第7次比较
    i = 7
    当前元素(i) 是否小于前一个元素(i-1) 此时38(i)小于 78(i-1)
    当前有序表已排序好的为:-10 ,38, 49, 55,67,65,78,38,77,99。
    情况和第二次比较过程类似 不再赘述 比较完成之后的序列为:
    -10 ,38,38,49, 55,65,67,78,77,99。

    第8次比较
    i = 8
    当前元素(i) 是否小于前一个元素(i-1) 此时77(i)小于 78(i-1) 当前有序表已排序好的为:-10 -10 ,38,38,49, 55,65,67,78,77,99。
    情况和第二次比较过程类似 不再赘述 比较完成之后的序列为:
    -10 ,38,38,49, 55,65,67,77,78,99。

    第9次比较
    i=9
    当前元素(i) 是否小于前一个元素(i-1) 此时99(i)大于于 78(i-1) 当前有序表已排序好的为:-10 -10 ,38,38,49, 55,65,67,78,77,99。
    之后 i=10 跳出循环

    比较过程结束

    三、具体代码与运行截图

    #include <iostream>
    using namespace std;
    template <typename T>
    void insertSort(T arr[], int size) {
    	int i = 0, j = 0;
    	T temp = NULL;
    	for (i = 1;i <size;i++) {
    		if (arr[i - 1] > arr[i]) {
    			temp = arr[i];
    			for (j = i - 1;j >= 0 && arr[j] > temp;j--) {
    				arr[j + 1] = arr[j];
    			}
    			arr[j + 1] = temp;
    		}
    	}
    }
    int main() {
    	
    	int test[10] = {38,55,-10,49,67,78,65,38,77,99};
    	insertSort(test, 10);
    	unsigned int i = 0;
    
    	for (i = 0;i < 10;i++) {
    		cout << test[i] << "   ";
    	}
    	
    	return 0;
    }
    
    

    运行结果如下图:

    在这里插入图片描述

    在这里插入图片描述

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,492
精华内容 5,396
关键字:

直接插入排序算法