网站建设包括的内容有什么,wordpress 上传图片大小,公众号小程序制作步骤,为了选择合适的网络设计方案插入排序
算法思想
插入排序的算法思想其实很容易理解#xff0c;它秉持着一个不变的循环#xff1a;比较-交换-比较-交换…因为我们排序最终的目的是要得到递增或者递减的数据#xff0c;那么在原有的数据中#xff0c;我们可以将数据依次两两进行比较…插入排序
算法思想
插入排序的算法思想其实很容易理解它秉持着一个不变的循环比较-交换-比较-交换…因为我们排序最终的目的是要得到递增或者递减的数据那么在原有的数据中我们可以将数据依次两两进行比较
如果是升序那么就将较小的放在较大的前面如果是降序那么就将较大的放在较小的前面
图解 我们看图解中单次比较过程中拿出来比较的数只会同它左侧的数进行比较而被比较的数随着比较结束也会根据具体情况向后移动或者是进行交换向后移动的过程也称为——补位。在全程的比较中随着补位和交换的进行进行比较操作的数只会与曾经进行过比较操作的数进行比较——简单来说就是比较与被比较是交替进行的。我们总结插入排序算法的核心思路——将待排列元素划分为「已排序」和「未排序」两部分每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
C语言代码分析
//升序情况
void InsertSort(int* arr, int n)
{int end n - 1;//从最后一个数据开始进行比较int tmp arr[end];//保存最后一个数据while (end 0){if (tmp arr[end])//当tmp小于等于arr[end]时说明tmp还没有找到合适的位置{arr[end 1] arr[end];//那么就将arr[end]向后移动end--;//继续向前比较}else//当tmp大于arr[end]时说明tmp已经找到了合适的位置{break;//那么就直接退出循环}}arr[end 1] tmp;
}//降序情况
void InsertSort2(int* arr, int n)
{int begin 0;//从第一个数据开始进行比较int tmp arr[begin];//保存第一个数据while (begin n - 1){if(tmparr[begin])//当tmp大于等于arr[begin]时说明tmp还没有找到合适的位置{arr[begin - 1] arr[begin];//那么就将arr[begin]向后移动begin;//继续向后比较}else//当tmp小于arr[begin]时说明tmp已经找到了合适的位置{break;//那么就直接退出循环}arr[begin 1] tmp;
}在现实生活中扑克牌的排序事实上就是遵循着插入排序的思想 时间复杂度 插入排序的最优时间复杂度为O(n)在数列几乎有序时效率很高。 插入排序的最坏时间复杂度和平均时间复杂度都为O(n2)。
稳定性
鉴于插入排序不会改变前后元素的相对位置所以 稳定
