插入排序/折半插入排序 插入排序 插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入
插入排序(英语: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在数组上实现。具体算法描述如下:
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[j+1]= temp;}System.out.println(Arrays.toString(arrays));}}
折半插入排序(Binary Insertion Sort)是一种基于插入排序的排序算法。它的思想是将待排序的序列分为已排序区和未排序区,然后逐个将未排序区的元素插入到已排序区的适当位置,使整个序列保持有序。
算法的详细步骤如下:
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),是一种稳定的排序算法,适用于小规模和部分有序的序列。
来源地址:https://blog.csdn.net/Tanganling/article/details/133636369
--结束END--
本文标题: 插入排序/折半插入排序
本文链接: https://www.lsjlt.com/news/424463.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0