Sorting Algorithms:Binary Insertion Sort
preface
The blog used for the weak chicken review consolidation, lay a solid foundation, but also hope that the big guy is generous to give advice.
The basic idea
When a new element is inserted into an ordinal group, the binary method is used to find the insertion position
Algorithm complexity analysis
| The worst | The best | The stability of | Spatial complexity |
|---|---|---|---|
| O(n^2) | O(nlog2n) | stable | O(1) |
P.S. Best case: k is the last position of the ordinal group, no shift assignment is required O(n*log2n) worst case: k is the first position of the ordinal group, then the whole ordinal group needs a shift assignment O(n^2) binary search time O(log2n)
Code implementation
import java.util.Arrays;
import java.util.Random;
/ * *
* Binary insert sort, improve insert direct insert sort
* When a new element is inserted into an ordinal group, the binary method is used to find the insertion position
* Best case: each insertion position k is the last position of the ordinal group, no shift assignment O(n*log2n)
* Worst case: each insertion position k is the first ordinal position, then the whole ordinal group needs to shift assignment O(n^2)
* Space complexity O(1)
* Stability and stability
* Binary search time complexity O(log2n)
* @author Wayne Zhang
* @date 2018/07/17
* /
public class BinaryInsertion {
public static void main(String[] args) {
int[] a = new int[10];
//random array
for (int i = 0; i < a.length; i++) {
Random rd = new Random();
a[i] = rd.nextInt(10);
}
System.out.println("Random Array :");
System.out.println(Arrays.toString(a));
System.out.println();
System.out.println("Binary Insertion Sort :");
// Insert sort
// The loop specifies that the element is inserted into the arranged array starting with the second element
for (int i = 1; i < a.length; i++) {
// Get the insertion position
int k = findByBinary(a, i);
/ / save a [I]
int key = a[i];
// The element moves back
for (int j = i - 1; j >= k; j--) {
a[j + 1] = a[j];
}
a[k] = key;
}
System.out.println(Arrays.toString(a));
}
public static int findByBinary(int[] a, int i) {
int highIndex = i - 1;
int lowIndex = 0;
int mid = -1;
while (lowIndex <= highIndex) {
mid = (highIndex + lowIndex) / 2;
if (a[i] >= a[mid]) {
// If equal, ensure that the new element is inserted after the old element
lowIndex = mid + 1;
} else {
highIndex = mid - 1;
}
}
return lowIndex;
}
}
Copy the codereference
Dahua data structure “: https://book.douban.com/subject/6424904/