广西玉林网站建设,孝感做网站,ui设计的优势与不足,网站建设的主要特征经典排序算法----直接插入排序算法及其改进#xff08;稳定#xff09; 定义#xff1a; 直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中#xff0c;从而得到一个新的#xff0c;记录数加一的有序表。 实现思想 我们预留了一个哨兵#xff0c;这里我们将…经典排序算法----直接插入排序算法及其改进稳定 定义 直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中从而得到一个新的记录数加一的有序表。 实现思想 我们预留了一个哨兵这里我们将用到它来保存一个临时值 插入排序是在一个已经有序的小序列的基础上一次插入一个元素。当然刚开始这个有序的小序列只有1个元素就是第一个元素。比较是从有序序列的末尾开始也就是想要插入的元素和已经有序的最大者开始比起如果比它大则直接插入在其后面否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的那么插入元素把想插入的元素放在相等元素的后面。 所以相等元素的前后顺序没有改变从原无序序列出去的顺序就是排好序后的顺序所以插入排序是稳定的。 基本思想 每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列中的适当位置直到全部记录插入完成为止。 代码实现 void InsertSort(SqList *L)
{int i, j, count1, count2;count2 count1 0;for (i 2; i L-length;i){if (L-r[i]L-r[i-1]) //若是前面第一个都不满足顺序那么我们就要去循环{L-r[0] L-r[i];for (j i - 1; L-r[j]L-r[0]; j--) //将大的数据全部向后移动从后向前防止数据覆盖{count1;L-r[j 1] L-r[j]; //记录后移}L-r[j 1] L-r[0]; //插入到正确位置count2;}}printf(loop move count:%d, swap insert count:%d\n, count1, count2);
} 性能分析 空间上只需要一个记录辅助空间所以关键看时间复杂度
平均比较和移动次数约为(n^2)/4,所以时间复杂度为O(n^2)。
其性能要比冒泡和简单选择排序好些 转载于:https://www.cnblogs.com/ssyfj/p/9510735.html
