许昌市建设路小学网站,网站建设选谋者,麻城网站建设,互联网平台宣传推广方案1.基本思想
直接插入排序是一种简单的插入排序法#xff0c;其基本思想是#xff1a; 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为止#xff0c;得到一个新的有序序列 实际中我们玩扑克牌时#xff0c;就用…1.基本思想
直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 实际中我们玩扑克牌时就用了插入排序的思想 2.直接插入排序 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 动图https://pic3.zhimg.com/v2-91b76e8e4dab9b0cad9a017d7dd431e2_b.webp 直接插入排序的特性总结 元素集合越接近有序直接插入排序算法的时间效率越高 时间复杂度O(N^2) 空间复杂度O(1)它是一种稳定的排序算法 稳定性稳定 3.直接插入排序实现思路
我们假设[0,end]是有序的那么我们需要把end1的值插入到有序数组中去然后end
我们以升序为例
定义一个endtmp存a[end1]的值从end的位置开始判断tmp大于还是小于end的值如果tmpa[end]则将a[end]的值向后移动end--接着对比前一个否则跳出循环如果end走到-1那就将tmp存到a[end]即a[0]否则就将tmp存到a[end]的后面即a[end1]tmp我们用for循环控制多趟循环从0开始一直比较到n-1
直接插入排序的时间复杂度为O(N^2) 4.实现代码
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}elsebreak;}a[end 1] tmp;}
}
