赢卡购网站建设,天津平台网站建设报价,微信官方网站,wordpress采集自动伪原创插入排序/折半插入排序
插入排序
插入排序(英语#xff1a;Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列#xff0c;对于未排序数据#xff0c;在已排序序列中从后向前扫描#xff0c;找到相应位置并插入。插入排序在实现上#xff0c;通常…插入排序/折半插入排序
插入排序
插入排序(英语Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。插入排序在实现上通常采用in-place排序(即只需要要用道O(1)的额外空间的排序)因而从后向前扫描过成功需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。
概述
Insertion Sort和打扑克牌时从牌桌上逐一拿起扑克牌在手上排序的过程相同。
举例
输入 {5 2 4 6 1 3}。
首先拿起第一张牌, 手上有 {5}。
拿起第二张牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。
拿起第三张牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。
以此类推。
动图演示 算法
一般来说插入排序都采用in-place在数组上实现。具体算法描述如下
从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5
import java.util.Arrays;public class InsertionSort {// 插入排序算法类似打扑克牌public static void main(String[] args) {int[] arrays {5, 2, 4, 6, 1, 3};insertionSort(arrays);}private static void insertionSort(int[] arrays) {for (int i 1; i arrays.length; i) {// 为了保证空间复杂度不变我需要利用arrays这个数组int temp arrays[i];int j;for (j i - 1; j 0 temp arrays[j]; j--) {arrays[j 1] arrays[j];}arrays[j1] temp;}System.out.println(Arrays.toString(arrays));}
}折半插入排序
折半插入排序Binary Insertion Sort是一种基于插入排序的排序算法。它的思想是将待排序的序列分为已排序区和未排序区然后逐个将未排序区的元素插入到已排序区的适当位置使整个序列保持有序。
算法的详细步骤如下
假设待排序序列为arr初始时将arr[0]作为已排序区arr[1]到arr[n-1]作为未排序区其中n是序列的长度。从未排序区选择第一个元素arr[i]i从1开始将其插入到已排序区的适当位置。在已排序区使用折半查找二分查找找到arr[i]在已排序区的插入位置。 首先确定查找区间的左边界left为0右边界right为i-1。然后计算中间位置mid为(left right) / 2。比较arr[i]与已排序区的中间元素arr[mid]的大小 如果arr[i]小于arr[mid]则插入位置在[left, mid-1]区间令right mid - 1。如果arr[i]大于等于arr[mid]则插入位置在[mid1, right]区间令left mid 1。 重复上述步骤直到left right找到插入位置。 将已排序区中插入位置后的元素都向后移动一个位置为arr[i]腾出空间。将arr[i]插入到找到的插入位置完成一次插入操作。重复步骤2到步骤5直到所有元素都被插入到已排序区。
public static void binaryInsertionSort(int nums[]) {for (int i 1; i nums.length; i) {int low 0;int high i - 1;int temp nums[i];while (high low) {int mid (high low) / 2;if (nums[mid] temp) {high mid - 1;} else {low mid 1;}}for (int j i; j low; j--) {nums[j] nums[j - 1];}nums[low] temp;}}折半插入排序的核心思想是利用二分查找来确定插入位置从而减少比较次数提高排序效率。相比于普通插入排序折半插入排序的主要优势在于减少了比较的次数尤其适用于大规模数据的排序。
折半插入排序的时间复杂度为O(n^2)与普通插入排序相同但由于减少了比较次数实际上的运行时间可能会比普通插入排序稍微快一些。它是一种稳定的排序算法适用于小规模和部分有序的序列。
总结起来折半插入排序是一种基于插入排序的排序算法通过利用二分查找确定插入位置减少比较次数提高排序效率。它的时间复杂度为O(n^2)是一种稳定的排序算法适用于小规模和部分有序的序列。
