重庆市交通建设工会网站,四川网站建设开发,网页设计培训贵不贵,漂亮网站欣赏详细描述
插入排序的基本思想是#xff1a;将一个记录插入到已经排好序的有序表中#xff0c;从而得到一个新的、记录数增 1 的有序表。
在其实现过程中使用双层循环#xff0c;外层循环针对除了第一个元素之外的所有元素#xff0c;内层循环针对当前元素前面的有序表进行…详细描述
插入排序的基本思想是将一个记录插入到已经排好序的有序表中从而得到一个新的、记录数增 1 的有序表。
在其实现过程中使用双层循环外层循环针对除了第一个元素之外的所有元素内层循环针对当前元素前面的有序表进行待插入位置查找并进行移动。
选择排序详细的执行步骤如下
从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤 3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置重复步骤 2~5。
算法图解 问题解疑
插入排序是原地排序算法吗
插入排序算法的运行并不需要额外的存储空间所以空间复杂度是 O(1)也就是说这是一个原地排序算法。
插入排序是稳定的排序算法吗
对于值相同的元素可以选择将后面出现的元素插入到前面出现元素的后面这样就可以保持原有的前后顺序不变所以插入排序是稳定的排序算法。
插入排序的时间复杂度是多少
最好情况时间复杂度为 O(n)最坏情况时间复杂度为 O(n2)平均时间复杂度为 O(n2)。
代码实现
排序接口 package cn.fatedeity.algorithm.sort;/*** 排序接口*/public interface Sort {int[] sort(int[] numbers);}
排序抽象类 package cn.fatedeity.algorithm.sort;/*** 排序抽象类*/public abstract class AbstractSort implements Sort {protected void swap(int[] numbers, int src, int target) {int temp numbers[src];numbers[src] numbers[target];numbers[target] temp;}}
插入排序类 package cn.fatedeity.algorithm.sort;/*** 插入排序类*/public class InsertionSort extends AbstractSort {Overridepublic int[] sort(int[] numbers) {if (numbers.length 1) {return numbers;}for (int i 1; i numbers.length; i) {for (int j i; j 0; j--) {// 一直交换到顺序相反if (numbers[j - 1] numbers[j]) {break;}this.swap(numbers, j, j - 1);}}return numbers;}}
