插入排序/折半插入排序
插入排序
插入排序(英语: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[j+1]= 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],则插入位置在[mid+1, 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),是一种稳定的排序算法,适用于小规模和部分有序的序列。
来源地址:https://blog.csdn.net/Tanganling/article/details/133636369