数据结构与算法：直接插入、希尔、冒泡排序核心原理总结

文章目录1.直接插入排序2.希尔排序3.冒泡排序直接插入排序算法基本思想直接插⼊排序是⼀种简单的插⼊排序法其基本思想是把待排序的记录按其关键码值的⼤⼩逐个插 ⼊到⼀个已经排好序的有序序列中直到所有的记录插⼊完为⽌得到⼀个新的有序序列 。思路讲解定义endend1tmp三个变量end指向a数列的首数字tmp指向end1数列的值如果end的值大于end1的值则end1的值则改为end的值并且end需要减减此后因为tmp保存了end1的值end又减减后end1指向的值等于tmp指向的值完成前两个数字插入排序。时间复杂度O(n^2)空间复杂度O(1)代码实现void InsertSort(int* arr, int n) { for (int i 0; i n-1; i) { int end i; int tmp arr[end 1]; while (end 0) { if (arr[end] tmp) { arr[end 1] arr[end]; end--; } else { break; } } arr[end 1] tmp; } }希尔排序基本思路希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是先选定⼀个整数通常是gap n/31把 待排序⽂件所有记录分成各组所有的距离相等的记录分在同⼀组内并对每⼀组内的记录进⾏排 序然后gapgap/31得到下⼀个整数再将数组分成各组进⾏插⼊排序当gap1时就相当于 直接插⼊排序。 它是在直接插⼊排序算法的基础上进⾏改进⽽来的综合来说它的效率肯定是要⾼于直接插⼊排序算 法的。思路讲解希尔排序会先定义gap循环内gapgap/31按例图所示gap5时头结点与相隔5距离的结点相互比较如果头结点更大则会发生交换数列的加加以此循环gap1时相当于插入排序但是由于gap的排序会使得希尔排序比插入排序效率更高。希尔排序时间复杂度求值十分复杂时间复杂度O(N^1.3)空间复杂度O(1)代码实现void ShellSort(int* arr, int n) { int gap n; while (gap 1) { gap gap / 3 1; for (int i 0; i n - gap; i) { int end i; int tmp arr[end gap]; while (end 0) { if (arr[end] tmp) { arr[end gap] arr[end]; end - gap; } else { break; } } arr[end gap] tmp; } } }冒泡排序基本思路冒泡排序Bubble Sort是一种基于交换的稳定排序算法其核心思想是通过相邻元素的比较与交换将待排序序列中较大的元素逐步 “冒泡” 到序列的末尾重复该过程直至整个序列有序。思路讲解定义两个循环外层循环从数组数量最大开始递减end4内层循环从i1开始等于0会让代码越界为什么要定义两个循环一个循环一轮不能把数组变成有序因此需要多个循环遍历使其变得是有序数列。最后代码用到swap函数需要注意他们两个值交换的是地址不是值的交换如果值改变形参的改变不影响实参的改变。时间复杂度O(n^2)空间复杂度O(1)代码实现void sawp(int* a, int* b) { int tmp *a; *a *b; *b tmp; } void BubbleSort(int* arr, int n) { for (size_t end n; end 0; end--) { int exchange 0; for (size_t i 1; i end; i) { if (arr[i - 1] arr[i]) { sawp(arr[i - 1], arr[i]); exchange 1; } } if (exchange 0) { break; } } }