插入排序/折半插入排序

插入排序/折半插入排序

插入排序

插入排序(英语：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在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤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));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

折半插入排序

折半插入排序（Binary Insertion Sort）是一种基于插入排序的排序算法。它的思想是将待排序的序列分为已排序区和未排序区，然后逐个将未排序区的元素插入到已排序区的适当位置，使整个序列保持有序。

算法的详细步骤如下：

1. 假设待排序序列为arr，初始时将arr[0]作为已排序区，arr[1]到arr[n-1]作为未排序区，其中n是序列的长度。
2. 从未排序区选择第一个元素arr[i]（i从1开始），将其插入到已排序区的适当位置。
3. 在已排序区使用折半查找（二分查找）找到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，找到插入位置。
4. 将已排序区中插入位置后的元素都向后移动一个位置，为arr[i]腾出空间。
5. 将arr[i]插入到找到的插入位置，完成一次插入操作。
6. 重复步骤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;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

折半插入排序的核心思想是利用二分查找来确定插入位置，从而减少比较次数，提高排序效率。相比于普通插入排序，折半插入排序的主要优势在于减少了比较的次数，尤其适用于大规模数据的排序。

折半插入排序的时间复杂度为O(n^2)，与普通插入排序相同，但由于减少了比较次数，实际上的运行时间可能会比普通插入排序稍微快一些。它是一种稳定的排序算法，适用于小规模和部分有序的序列。

总结起来，折半插入排序是一种基于插入排序的排序算法，通过利用二分查找确定插入位置，减少比较次数，提高排序效率。它的时间复杂度为O(n^2)，是一种稳定的排序算法，适用于小规模和部分有序的序列。