网站关键词排名软件推荐,学网络营销好就业吗,ppt模板网站排行,站长检测工具文章目录 #x1f497; 直接插入排序Java代码C代码JavaScript代码稳定性时间复杂度空间复杂度 我们先来学习 直接插入排序, 直接排序算是所有排序中最简单的了,代码也非常好实现,尽管直接插入排序很简单,但是我们依旧不可以上来就直接写代码,一定要分析之后才开始写,这样可以提… 文章目录 直接插入排序Java代码C代码JavaScript代码稳定性时间复杂度空间复杂度 我们先来学习 直接插入排序, 直接排序算是所有排序中最简单的了,代码也非常好实现,尽管直接插入排序很简单,但是我们依旧不可以上来就直接写代码,一定要分析之后才开始写,这样可以提高自己写代码的准确率,整体流程下来,对知识的理解也会加深. 直接插入排序
默认第一个元素为有序的,然后从无序序列中的最左边取元素,从有序序列的右到左依次比较,直到找到合适的位置,然后插入. (简言之: 从无序序列取第一个元素从左到右比较插入到有序序列合适的位置) 用生活中的例子来描述直接插入排序理解起来会更加容易,所以我们这里就用一个生活中常发生的事来类比学习吧,如果我们把直接插入排序用打扑克牌来模拟,会是怎样的效果呢?
现在就来试试吧~
使用玩扑克牌的例子来模拟直接插入排序是一个很好的主意这个例子非常贴近直接插入排序的实际操作过程。让我们详细地通过这个例子来理解直接插入排序
初始状态你的手中还没有牌而洗好的牌堆是无序的。拿起第一张牌从牌堆中拿起最上面的一张牌这是你手中的第一张牌所以它自然就是有序的。继续摸牌再次从牌堆中拿起最上面的一张牌。比较和插入 将这张新拿到的牌与手中已有的牌从右到左进行比较。如果新牌比正在比较的牌小就将手中的这张牌向右移动一个位置为新牌腾出空间。继续这个过程直到找到一个牌位那里的牌比新牌小或者没有牌了也就是这张新牌是目前最小的。 插入新牌将新牌放入这个位置。重复过程继续从牌堆中拿牌并重复上述比较和插入的过程直到牌堆中的所有牌都被拿完并按顺序排列在手中。
这个过程很好地模拟了直接插入排序的逻辑。在每一步中你都保证了手中的牌是有序的通过找到合适的位置为新牌插入。这就是直接插入排序的精髓一步步构建有序序列直到所有元素都被正确地插入。
我们把上面的操作用图示来演示一下,进一步加深理解 , 假设现在的洗好的扑克牌为一组无序序列 : {6,4,9,1,10,2,8}
好,可以开始打牌了~ Java代码
package src.boke;public class InsertSort {public static void main(String[] args){//无序序列int[] arr {6,4,9,1,10,2,8};//调用直接排序方法insertSort(arr);//打印有序序列printArray(arr);}/*** 直接插入排序方法实现* param arr 待排序序列/无序序列*/public static void insertSort(int[] arr){//对传进来的无序序列进行直接插入排序操作for (int i 1; i arr.length; i) {//接收int[i] ,即摸到的牌int key arr[i];int j i-1;for (; j 0 ; j--) {if(arr[j]key){arr[j1] arr[j];}else{break;}}arr[j1] key;}}/*** 打印素组的方法*/public static void printArray(int[] arr){for (int i 0; i arr.length; i) {System.out.print(arr[i] );}}
}
C代码
#include stdio.hvoid insertSort(int arr[], int n) {for (int i 1; i n; i) {int key arr[i];int j i - 1;// 将大于 key 的元素向右移动一个位置while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}
}void printArray(int arr[], int n) {for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);
}int main() {int arr[] {6, 4, 9, 1, 10, 2, 8};int n sizeof(arr) / sizeof(arr[0]);insertSort(arr, n);printArray(arr, n);return 0;
}
JavaScript代码
function insertSort(arr) {for (let i 1; i arr.length; i) {let key arr[i];let j i - 1;while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}
}function printArray(arr) {console.log(arr.join( ));
}// 测试
let arr [6, 4, 9, 1, 10, 2, 8];
insertSort(arr);
printArray(arr); 稳定性
排序稳定性是排序算法的一个重要特性它涉及相等元素的相对顺序在排序前后是否保持不变。
具体来说
稳定排序如果一个排序算法在排序后保持了相等元素在原序列中的相对顺序那么这个算法是稳定的。换句话说如果两个具有相等关键字的元素在排序前是以某种顺序排列的那么在排序后它们仍然以同样的顺序排列这样的排序算法就被认为是稳定的。不稳定排序如果排序算法不能保证相等元素的相对顺序则称这种排序是不稳定的。在这种情况下相等的元素可能会因排序过程而交换位置。
稳定性的重要性主要体现在当元素有多个字段进行排序时。在某些情况下维持数据的初始顺序是重要的。例如在对一组人按照出生日期排序后可能需要对结果按姓名排序如果使用稳定排序算法那么同一天出生的人将按照他们原始的顺序即按姓名的顺序排列。 通过上述测试我们可以知道,当我们在比较key和arr[j] 的时候,如果取了 等号 ,那么此时就是不稳定的,如果没有取 等号 就是稳定的,所以直接插入排序是稳定的吗?
让我们详细解释一下为什么这样会发生
当使用 arr[j] key 进行比较时如果 arr[j] 等于 key那么循环会停止key 将被插入到 arr[j] 的后面。因此原始数组中顺序相邻的、值相等的元素在排序后仍将保持相同的顺序这保证了排序的稳定性。然而如果使用 arr[j] key 进行比较当 arr[j] 等于 key 时排序过程仍会继续尝试找到更前面的位置插入 key。这可能导致 key 被插入到其他相等元素的前面从而改变了这些元素的相对顺序这破坏了排序的稳定性。
结论 : 一个本身就稳定的排序你可以将其实现为不稳定的,但是一个本身就不稳定的排序你无法将其变成稳定的. 所以 : 直接插入排序是稳定的排序 时间复杂度
直接插入排序的时间复杂度是 O(n^2)
直接插入排序的时间复杂度分析涉及到最好情况、平均情况和最坏情况。
最好情况时间复杂度当输入数组已经是有序的每次比较都不需要进行移位操作因为每个元素已经是在其正确的位置上直接插入排序只需要进行一次遍历来确认所有元素都已排序。因此在这种情况下时间复杂度是 O(n)其中 n 是数组的长度。最坏情况时间复杂度在最坏的情况下数组完全逆序即每次插入都需要将元素移动到数组的最前面。这就需要对于每个元素进行从 1 到 i其中 i 是当前元素的索引的比较和移动因此需要的操作数接近于 123…(n−1)这是一个等差数列求和总和是 O(n^2)。平均情况时间复杂度在平均情况下元素需要移动的次数大约是数组长度的一半因此平均情况时间复杂度也是O(n^2)。 空间复杂度
你直接插入排序的空间复杂度是O(1)
直接插入排序的空间复杂度主要考虑的是算法在执行过程中需要额外使用的内存空间。
在直接插入排序中所有的排序操作都是在原始数组上进行的不需要额外的数组来存储数据。排序过程中唯一需要的额外空间是一个用于存储待插入元素的临时变量比如 key。除此之外还需要少量的额外空间用于循环计数和索引存储。
由于这些额外空间的需求量不随待排序的数据量的增加而增加也就是说无论要排序多少数据所需的额外空间量都是固定的因此直接插入排序的空间复杂度是O(1)也就是说它是一个原地排序算法。这也意味着直接插入排序非常节省内存适合于在内存受限的环境中使用。
