网站怎么做360免费优化,横琴人寿保险公司官网,安美东莞网站建设,php旅游网站开发背景插入排序 概述步骤代码示例输出结果 概述
插入排序是一种最简单直观的排序算法#xff0c;它的工作原理是通过创建有序序列和无序序列#xff0c;然后再遍历无序序列得到里面每一个数字#xff0c;把每一个数字插入到有序序列中正确的位置。
插入排序是一种简单直观的排序… 插入排序 概述步骤代码示例输出结果 概述
插入排序是一种最简单直观的排序算法它的工作原理是通过创建有序序列和无序序列然后再遍历无序序列得到里面每一个数字把每一个数字插入到有序序列中正确的位置。
插入排序是一种简单直观的排序算法其基本思想是将未排序的元素逐个插入到已排序序列中的正确位置从而构建有序的序列。
插入排序在插入的时候有优化算法在遍历有序序列找正确位置时可以采取二分查找
插入排序的时间复杂度为 O(n^2)但是在处理小型数组或基本有序的数组时插入排序的性能往往比其他复杂的排序算法更好。此外插入排序是稳定的排序算法即具有相等值的元素在排序后的相对位置不会改变。
步骤
插入排序的过程如下 从第一个元素开始认为该元素已经是有序序列。 取出下一个元素将其与已排序的元素从右到左依次比较。 如果已排序的元素大于当前元素则将已排序的元素后移一位继续比较前一个已排序的元素。 重复步骤 3直到找到一个已排序的元素小于或等于当前元素或者到达已排序序列的起始位置。 将当前元素插入到已排序序列中找到的位置后面。 重复步骤 2 到 5直到所有元素都被插入到有序序列中。
插入排序每次将一个元素插入到已排序序列中并将该元素放置在正确的位置上。通过逐步扩大已排序的部分最终完成整个数组的排序。 将0索引的元素到N索引的元素看做是有序的把N1索引的元素到最后一个当成是无序的。遍历无序的数据将遍历到的元素插入有序序列中适当的位置如遇到相同数据插在后面。 N的范围0~最大索引 代码示例
需求采用插入排序将下列数据进行排序数据如下{3, 23, 36, 37, 40, 43, 44, 38, 5, 47, 15, 47, 36, 26, 27, 2, 46, 4, 19, 23, 50, 23, 48};
例如
package text.text02;/*
插入排序插入排序是一种最简单直观的排序算法它的工作原理是通过创建有序序列和无序序列然后再遍历无序序列得到里面每一个数字把每一个数字插入到有序序列中正确的位置。插入排序在插入的时候有优化算法在遍历有序序列找正确位置时可以采取二分查找*/
public class text13A {public static void main(String[] args) {int[] arr {3, 23, 36, 37, 40, 43, 44, 38, 5, 47, 15, 47, 36, 26, 27, 2, 46, 4, 19, 23, 50, 23, 48};//定义一个变量记录无序序列的起始索引int startIndex -1;//遍历数组找到无序序列的起始索引for (int i 0; i arr.length - 1; i) {//表明前i-1个数和第i1个数都小于第i个数说明前i个数都是有序的第i1个数以后都是无序的if (arr[i] arr[i 1]) {//将无序序列的起始索引赋值给startIndexstartIndex i 1;break;}}//调用method1方法遍历数组将无序序列中的数据插入到有序序列中(顺序查找/基本查找)int[] arr1 method1(arr, startIndex);//调用method2方法遍历数组将无序序列中的数据插入到有序序列中(折半查找/二分查找)int[] arr2 method2(arr, startIndex);//调用printfArray方法遍历输出数组数据System.out.println(这是基本查找/顺序查找的方法);printfArray(arr1); //2 3 4 5 15 19 23 23 23 26 27 36 36 37 38 40 43 44 46 47 47 48 50System.out.println(); //换行System.out.println(这是折半查找/二分查找的方法);printfArray(arr2); //2 3 4 5 15 19 23 23 23 26 27 36 36 37 38 40 43 44 46 47 47 48 50}//遍历数组方法1将无序序列中的数据插入到有序序列中(顺序查找/基本查找)public static int[] method1(int[] arr, int startIndex) {for (int i startIndex; i arr.length; i) {//定义一个变量记录i的值因为后面要更改j的值j--如果直接更改i则循环永远不到达到i arr.lengthint j i;while (j 0 arr[j - 1] arr[j]) { //j表示无序序列的其实索引j-1表示有序序列的最后索引//交换数据int temp arr[j];arr[j] arr[j - 1];arr[j - 1] temp;j--;}}return arr;}//遍历数组方法2将无序序列中的数据插入到有序序列中(折半查找/二分查找)public static int[] method2(int[] arr, int startIndex) {//利用循环交换数组元素进行排序for (int i startIndex; i arr.length; i) {//调用judgeIndex方法获取要插入元素的位置int index judgeIndex(arr, i);//定义一个变量记录要插入的数int number arr[i];//利用循环将已排序部分中要插入位置之后的元素向右移动为待插入元素腾出空间从 i1 开始向左遍历将每个元素向右移动一位直到达到插入位置 index。for (int i1 i; i1 index; i1--) {arr[i1] arr[i1 - 1];}//将记录要插入的值的变量赋值给要插入的位置arr[index] number;}return arr;}//定义方法用来判断要插入的数的位置public static int judgeIndex(int[] arr, int startIndex) {//定义变量记录已经排序的数中的起始索引int min 0;//定义变量记录已经排序的数中的结束索引int max startIndex - 1;//利用循环找到要插入的位置while (min max) {//获取已排序的数的中间索引int mid (min max) / 2;//如果中间索引所对应的数等于要插入得数if (arr[mid] arr[startIndex]) {return mid;}//如果中间索引所对应的数小于要插入得数if (arr[mid] arr[startIndex]) {min mid 1;}//如果中间索引所对应的数大于要插入得数if (arr[mid] arr[startIndex]) {max mid - 1;}}//当循环结束时“min” 指针指向了插入位置的右侧。在每次二分查找的过程中如果目标元素小于当前中间元素那么 “max” 指针会更新为 “mid - 1”如果目标元素大于当前中间元素那么 “min” 指针会更新为 “mid 1”。最终当满足 “min max” 时说明目标元素应该插入的位置就是 “min” 指向的位置。因此当二分查找未找到目标元素时插入位置就是 “min” 所指向的位置所以返回 “min”。如果找到目标元素那么也返回该元素在数组中的位置。return min;}//遍历输出数组数据public static void printfArray(int[] arr) {for (int i 0; i arr.length; i) {System.out.print(arr[i] \t);}}
}
输出结果
