学做网站能赚多少钱,做网站公司北京,WordPress安全社区,.net php开发网站开发因为排序这些比较复杂点我就分几期给大家来讲~~~
直接插入排序
直接插入排序是一种简单的排序算法#xff0c;主要用于对少量数据进行排序。其基本思想是将待排序的元素逐个插入到已经排好序的部分中#xff0c;从而形成一个有序序列。
具体步骤如下#xff1a;
初始化主要用于对少量数据进行排序。其基本思想是将待排序的元素逐个插入到已经排好序的部分中从而形成一个有序序列。
具体步骤如下
初始化将数组分为已排序和未排序两部分开始时已排序部分只有一个元素。遍历未排序部分从未排序部分取出一个元素称为“关键元素”然后与已排序部分的元素进行比较。插入找到合适的位置将关键元素插入到已排序部分保持其有序性。重复重复步骤2和3直到未排序部分的元素全部插入到已排序部分。
特点
时间复杂度最坏情况为O(n^2)最好情况为O(n)当数组已经基本有序时。空间复杂度O(1)因为只需要常量空间来存放关键元素。稳定性是稳定排序两个相等的元素在排序后相对位置不变。
直接插入排序适合小规模数据的排序且在数据基本有序时效率较高。
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移
#include stdio.h// 直接插入排序函数
void InsertionSort(int* arr, int n) {int i, key, j;for (i 1; i n; i) {key arr[i];j i - 1;// 将 arr[i] 插入到已排序的序列 arr[0...i-1] 中的正确位置while (j 0 arr[j] key) {arr[j 1] arr[j];j j - 1;}arr[j 1] key;}
}// 打印数组函数
void PrintArray(int* arr, int n) {int i;for (i 0; i n; i) {printf(%d , arr[i]);}printf(\n);
}// 主函数
int main() {int arr[] {283571469};int n sizeof(arr) / sizeof(arr[0]);printf(Original array:\n);PrintArray(arr, n);InsertionSort(arr, n);printf(Sorted array:\n);PrintArray(arr, n);return 0;
}希尔排序
希尔排序是一种基于插入排序的排序算法也被称为递减增量排序。它通过将待排序数组分成多个子数组使每个子数组中的元素进行插入排序从而提高排序效率。其基本思路是通过选择一个增量序列将待排序数组分组进行排序。
具体步骤如下
选择增量首先选择一个增量也叫“间隔”通常是整个数组长度的一半然后逐步减小增量直到增量为1。分组排序根据当前增量将数组分成若干个子数组对每个子数组进行插入排序。重复继续减少增量并对新的分组进行插入排序直到增量为1此时对整个数组进行一次插入排序。
特点
时间复杂度平均和最坏情况下的时间复杂度为O(n(1.5))到O(n2)而最好情况下为O(n log n)具体表现取决于增量序列的选择。空间复杂度O(1)因为只需常量级的辅助空间。稳定性希尔排序一般不稳定可能改变相同元素的相对位置。
希尔排序相较于简单的插入排序在性能上有显著提升适合中等规模的数据排序。
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个 组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工 作。当到达1时所有记录在统一组内排好序。
希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固定 《数据结构(C语言版)》— 严蔚敏 《数据结构-用面相对象方法与C描述》— 殷人昆
void ShellSort(int* a, int n)
{int gap n;while (gap 1){// 1保证最后一个gap一定是1// gap 1时是预排序// gap 1时是插入排序gap gap / 3 1;for (size_t 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;}else{break;}}a[end gap] tmp;}}
}那我们下期再见啦 ~冒泡选择以及快排
