青岛网站建设首选营销吧系统,投资公司投资流程,上海工商信息查询网,网站设计风格有哪些1.直接插入排序
插入排序的思想:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为止#xff0c;得到一个新的有序序列 。
你可以想像成打牌一样,比如说斗地主,一张一张的摸牌,然后把手上的这些牌变成手续的排列.…1.直接插入排序
插入排序的思想:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
你可以想像成打牌一样,比如说斗地主,一张一张的摸牌,然后把手上的这些牌变成手续的排列. 具体步骤如下 将第一个元素视为已排序的序列将第二个元素与已排序序列进行比较找到合适的位置插入。 将第三个元素与已排序序列进行比较找到合适的位置插入。 以此类推将后续的元素与已排序序列进行比较并插入。 最终得到一个完整的有序序列。
假设现在有一组数据需要排序:
初始序列5 2 4 6 1 3 将第一个元素5视为已排序序列不需要进行比较直接插入。
已排序序列5
未排序序列2 4 6 1 3 将第二个元素2与已排序序列进行比较找到合适的位置插入。
已排序序列2 5
未排序序列4 6 1 3 将第三个元素4与已排序序列进行比较找到合适的位置插入。
已排序序列2 4 5
未排序序列6 1 3 将第四个元素6与已排序序列进行比较找到合适的位置插入。
已排序序列2 4 5 6
未排序序列1 3 将第五个元素1与已排序序列进行比较找到合适的位置插入。
已排序序列1 2 4 5 6
未排序序列3 将最后一个元素3与已排序序列进行比较找到合适的位置插入。
已排序序列1 2 3 4 5 6
未排序序列空
最终得到有序序列1 2 3 4 5 6
int arr[] { 5, 2, 4, 6, 1, 3};
InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
//直接插入排序
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--;}else{break;}}a[end 1] tmp;}
} 外部循环从第一个元素迭代到倒数第二个元素。 在每次迭代中定义一个变量end它的初始值为当前外部循环的索引i。 定义一个变量tmp用于存储下一个待插入的元素即a[end1]。 在内部循环中从end开始向前遍历数组比较tmp与当前元素a[end]的大小。 如果tmp小于a[end]则将a[end]向后移动一位即a[end1] a[end]并将end减1。 重复步骤4和步骤5直到找到tmp应该插入的位置即tmp大于等于a[end]。 将tmp插入到正确的位置即a[end1] tmp。 重复步骤1到步骤7直到所有元素都被排序。
2.希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是
先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 希尔排序的特性总结 希尔排序是对直接插入排序的优化。 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就
会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的
4.希尔排序的时间复杂度都不固定 我们这里的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按 照 O(N^1.3)来算.
简而言之希尔排序就是在上面的直接插入排序上加入了预排序,巧妙的就是当gap为1的时候,其实走的就是直接插入排序,可以说希尔排序是直接插入排序的升级版本.
//希尔排序(便于理解版)
void ShellSort1(int* a, int n)
{int gap n;while (gap 1){//gap / 2;gap gap / 3 1;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}
}
//希尔排序(少一层循环版)
void ShellSort2(int* a, int n)
{int gap n;while (gap 1){//gap / 2;gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}elsebreak;}a[end gap] tmp;}}
}
代码详解:
ShellSort1版本的希尔排序算法 首先初始化一个间隔值gap为数组的长度n。 在一个循环中当间隔值大于1时执行以下操作 a. 将间隔值gap除以3并加1得到新的间隔值gap。 b. 在一个嵌套循环中从0到gap-1对每个间隔进行插入排序 从当前间隔值的位置开始向后遍历数组每次以间隔值gap递增。 对于每个位置i将其作为插入排序的起始位置将a[igap]作为待插入的元素tmp。 在内部循环中从当前位置向前遍历比较tmp与当前元素a[end]的大小。 如果tmp小于a[end]则将a[endgap]的值更新为a[end]并将end减去间隔值gap。 如果tmp大于等于a[end]则跳出内部循环。 将tmp插入到正确的位置即a[endgap] tmp。 重复步骤2直到间隔值gap为1完成整个排序过程。
ShellSort2版本的希尔排序算法 首先初始化一个间隔值gap为数组的长度n。 在一个循环中当间隔值大于1时执行以下操作 a. 将间隔值gap除以3并加1得到新的间隔值gap。 b. 在一个嵌套循环中从0到n-gap-1对每个间隔进行插入排序 从当前位置i开始将其作为插入排序的起始位置将a[igap]作为待插入的元素tmp。 在内部循环中从当前位置向前遍历比较tmp与当前元素a[end]的大小。 如果tmp小于a[end]则将a[endgap]的值更新为a[end]并将end减去间隔值gap。 如果tmp大于等于a[end]则跳出内部循环。 将tmp插入到正确的位置即a[endgap] tmp。 重复步骤2直到间隔值gap为1完成整个排序过程。
这两个版本的希尔排序算法的区别在于内部循环的起始位置不同ShellSort1从j开始每次以间隔值gap递增而ShellSort2从0开始每次以1递增。
