4.图解-折半插入排序 Binary insert sort

逃离我推掉我的手 2022-04-13 13:13 193阅读 0赞

### 1. 思想 ###

>   折半插入排序是对直接插入排序的改进。 直接插入排序就是不断的依次将元素插入前面已经排好序的序列中。  
>   由于前半部分为已经排好的序列，这样就不用按顺序依次比较寻找插入点，而是采用折半查找的方法来加快寻找插入点

### 2.图解-折半查找 ###

![705px-Binary_Search_Depiction.svg.png][]

将关键字 7 折半查找插入到 numbersArray。 查找过程如上图

int[] numbersArray = {1,3,4,6,7,8,10,13,14,18,19,21,24,37,40,45,71};
 
 //第 1 次
 low = 0
 high = 16
 middle = (0+16)/2 = 16/2 = 8
 7 (target at index 4) < 14 (middle at index 8)
 high = middle - 1 = 7
 
 //第 2 次
 low = 0
 high = 7
 middle = (0+7)/2 = 7/2 = 3 R 1
 7 (target at index 4) > 6 (middle at index 3)
 low = middle + 1 = 4
 
 //第 3 次
 low = 4
 high = 7
 middle = (4+7)/2 = 11/2 = 5 R 1
 7 (target at index 4) < 8 (middle at index 5)
 high = middle - 1 = 4
 
 //第 4 次
 low = 4
 high = 4
 middle = (4+4)/2 = 8/2 = 4
 7 (target at index 4) == 7 (middle at index 4)

### 3.Code in Java ###

import java.util.Arrays;
 
 class BinaryInsertionSort {
 
 	public static void main(String[] args) {
 		final int[] input = {4, 10, 3, 1, 9, 15, 40, 45, 71 };
 		System.out.println("Before Sorting - " + Arrays.toString(input));
 		new BinaryInsertionSort().sort(input);
 		System.out.println("After Sorting - " + Arrays.toString(input));
 	}
 
 	private static void sort(int[] dataArr) {
 		for (int i = 1; i < dataArr.length; i++) {
 			int temp = dataArr[i];
 			int low = 0, high = i - 1;
 			while (low <= high) {
 				int mid = (low + high) / 2;
 				if (temp < dataArr[mid]) {
 					high = mid - 1;
 				} else {
 					low = mid + 1;
 				}
 			}
 			int j = i - 1;
 			for (; j >= high + 1; j--) {
 				dataArr[j + 1] = dataArr[j];
 			}
 			dataArr[j + 1] = temp;
 		}
 	}
 
 
 
 }

### Code in C ###

#include <stdio.h>
 #include <stdlib.h>
 
 
 
 // A binary search based function to find the position
 // where item should be inserted
 int binarySearch(int a[], int item, int low, int high)
 {
 if (high <= low)
 return (item > a[low])? (low + 1): low;
 
 int mid = (low + high)/2;
 
 if(item == a[mid])
 return mid+1;
 
 if(item > a[mid])
 return binarySearch(a, item, mid+1, high);
 return binarySearch(a, item, low, mid-1);
 }
 
 // Function to sort an array a[] of size 'n'
 void insertionSort(int a[], int n)
 {
 int i, loc, j, k, selected;
 
 for (i = 1; i < n; ++i)
 {
 j = i - 1;
 selected = a[i];
 
 // find location where selected sould be inseretd
 loc = binarySearch(a, selected, 0, j);
 
 // Move all elements after location to create space
 while (j >= loc)
 {
 a[j+1] = a[j];
 j--;
 }
 a[j+1] = selected;
 }
 }
 
 // Driver program to test above function
 int main()
 {
 int a[] = {1, 18, 19, 21, 24, 37, 3, 4, 16, 7, 8, 10, 13, 40, 45};
 int n = sizeof(a)/sizeof(a[0]), i;
 
 insertionSort(a, n);
 
 printf("Sorted array: \n");
 for (i = 0; i < n; i++)
 printf("%d ",a[i]);
 
 return 0;
 }

### 4.算法分析 ###

与直接排序比较：减少了关键字比较的次数，但记录移动的次数没有变，时间复杂度是 N²

<table style="margin-left:5.4pt;"> 
 <tbody> 
 <tr> 
 <td style="background-color:#4f81bd;border-color:#000000;"> 排序类别 </td> 
 <td style="background-color:#4f81bd;"> 排序方法 </td> 
 <td colspan="3" style="background-color:#4f81bd;"> 时间复杂度 </td> 
 <td style="background-color:#4f81bd;"> 空间复杂度 </td> 
 <td style="background-color:#4f81bd;"> 稳定性 </td> 
 <td style="background-color:#4f81bd;"> 复杂性 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#4f81bd;"> 平均情况 </td> 
 <td style="background-color:#4f81bd;"> 最坏情况 </td> 
 <td style="background-color:#4f81bd;"> 最好情况 </td> 
 </tr> 
 <tr> 
 <td> 插入排序 </td> 
 <td> 折半插入排序 </td> 
 <td> O(N²) </td> 
 <td> O(N²) </td> 
 <td> O(N²) </td> 
 <td> O(1) </td> 
 <td> 稳定 </td> 
 <td> 简单 </td> 
 </tr> 
 </tbody> 
</table>

### 5.参考 ###

[https://en.wikipedia.org/wiki/Binary\_search\_algorithm][https_en.wikipedia.org_wiki_Binary_search_algorithm]

[705px-Binary_Search_Depiction.svg.png]: https://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Binary_Search_Depiction.svg/705px-Binary_Search_Depiction.svg.png
[https_en.wikipedia.org_wiki_Binary_search_algorithm]: https://en.wikipedia.org/wiki/Binary_search_algorithm