广西冶金建设公司网站,萧山做网站设计,做一个网站成本是多少,小众但惊艳的公司名称目录 1.直接插入排序2.希尔排序 1.直接插入排序 基本思想#xff1a; 把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的数据插入完成为止。 当插入第i个元素时#xff0c;前面的a[0],a[1],...,a[i-1]个数据已经排好序了#xff0c;此时用… 目录 1.直接插入排序2.希尔排序 1.直接插入排序 基本思想 把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中直到所有的数据插入完成为止。 当插入第i个元素时前面的a[0],a[1],...,a[i-1]个数据已经排好序了此时用a[i]与a[i-1],a[i-2],...进行比较找到插入位置就将a[i]插入原来位置上的元素顺序后移 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 (a[end] tmp){a[end 1] a[end];end--;}else//a[end]tmp说明前i1个数已经有序了{break;}}a[end 1] tmp;}
}元素集合月接近有序直接插入排序算法的时间效率更高 时间复杂度O(N^2) 稳定性稳定 2.希尔排序 希尔排序是直接插入排序的优化 1.预排序 2.直接插入排序 基本思想 先选定一个整数把待排序文件中所有数据分成gap个组所有距离为gap的数据分在同一个组里并对每一组的数据进行排序。然后取gapgap/31重复上述分组的操作。当gap1时所有数据在同一组的已经排好序了 void ShellSort(int* a, int n)
{int gap n;while(gap 1){//1保证最后一个gap一定是1//gap》1是预排序//gap1是插入排序gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
} 当gap1时都是预排序目的是让数组更接近有序。当gap1时数组已经接近有序了这样就会很快 时间复杂度ON^1.3)ps时间复杂度是不固定的 稳定性不稳定
