# Insert sort

## 1. Insert sorting directly

Moving picture transfer gate.
Thought: when playing poker, uncover the cards one by one and find the insertion position from back to front, so that the cards in your hand are always in an orderly state

```// 1. Direct insertion
public static void insertSort(int[] array) {
// 1. Uncover the cards one by one, and the cards in hand have always been orderly
for (int i = 1; i < array.length; i++) {
// Uncover the i-th card
int curNum = array[i];
// 2. Look forward for a place to insert
int j = i - 1;
while (j >= 0 && curNum < array[j]) {
// Before reaching the insertion position, move the j position backward to leave a space
array[j + 1] = array[j];
j --;
}
// 3. Insert the exposed card
array[j + 1] = curNum;
}
}
```

Time complexity:

Time complexityAverage: O(n^2)Best (in order): O(n)Worst case (in reverse order): O(n^2)

Space complexity: O(1)
Stability: stable
Optimization: search in half. First find the corresponding position of the team in half, and then move it

## 2. Hill sort

Illustration:

Idea: the time complexity of direct insertion sort is O(n) when it is ordered. The idea of Hill sort is to make the array tend to order first, and then carry out direct insertion sort.
Specific method: divide all the records with distance n in the array to be sorted into the same group, and sort the records in each group. In this way, the edges with a distance of N are in order. Then reduce the n value and repeat the above operations. The whole array gradually tends to be in order. Finally, when n = 1, it is directly inserted and sorted.

```// 2. Hill sort
public static void shellSort(int[] array) {
int gap = array.length;
while (gap > 0) {
insertSortGap(array, gap);
// Reduced increment formula
gap = gap /3 + 1;
}
// At this time, the array has become orderly. When gap = 1, it is equivalent to direct insertion sorting
insertSortGap(array,1);
}

private static void insertSortGap(int[] array, int gap) {
// Sort the number of gap s in the array, which is similar to direct insertion sorting
for (int i = gap; i < array.length; i += gap) {
int curNum = array[i];
int j = i - gap;
while (j >= 0 && curNum < array[j]) {
array[j + gap] = array[j];
j -= gap;
}
array[j + gap] = curNum;
}
}
```

Time complexity:

Time complexityAverage: O(n^1.3)Best: O(n)Worst case: O(n^2)

Space complexity: O(1)
Stability: unstable

# Select sort

## 3. Select Sorting directly

Idea: in each round, select the smallest number from the disordered interval and exchange it to the front

```// 3. Select Sorting directly
public static void selectSort(int[] array) {
// Select the smallest decimal from the unordered interval and exchange it to the front ordered interval of the unordered interval [0,i) unordered interval [i,len]
for (int i = 0; i < array.length; i++) {
int minIndex = i;
// Find minimum subscript
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// Once found, swap locations
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
}
```

Time complexity: each round should be traversed from beginning to end. It is not sensitive to data. O(n^2)
Space complexity: O(1)
Stability: unstable
Optimization: two-way selection sorting, finding the largest and smallest elements from the unordered interval each time and putting them at the top and last

## 4. Heap sorting

Animation demonstration.
Idea: it is the same as direct selection sorting, but instead of using each round of traversal to find the minimum number of unordered intervals to be placed at the front, it selects the maximum value (the number at the top of the heap) to be placed at the last side by creating a large root heap
Note: a lot should be built in ascending order; In descending order, small piles should be built

```// 4. Stacking and discharging
public static void heapSort(int[] array) {
// 1. Create a large root heap
int end = array.length;
for (int i = (end - 1) / 2; i >= 0 ; i--) {
// Adjust downward from the last non cotyledon node
adjustDown(array, i, end);
}
// 2. Select the maximum number of exchange positions
while (end > 0) {
// Change the maximum number to the last side
swap(array, 0, end);
// Reduce disordered interval
end --;
//Then adjust downward
adjustDown(array, 0, end);
}
}
// Adjust downward: adjust the value of the parent node to be greater than that of the child node. Compare and exchange with the parent node after finding the largest child node
private static void adjustDown(int[] array, int parent, int end) {
// Default maximum child node
int child = 2 * parent + 1;
// The parent node that may need to be adjusted is a very small number. After exchanging with the largest child node, it is still smaller than the child node, so it needs to be adjusted. Therefore, the loop should be in the while loop until it is larger than the child node or there is no child node to end the loop
while (child <= end) {
// If there is a right child and the right child is greater than the left child, update the maximum child node
if (child + 1 <= end && array[child + 1] > array[child]) {
child += 1;
}
// At this time, the child is already the largest child node
if (array[child] > array[parent]) {
// If the largest child node is larger than the parent node, exchange
swap(array, child, parent);
// Start the next round of adjustment from the child node
parent = child;
child = 2 * parent + 1;
} else {
// Greater than child node, jump out of loop
break;
}
}
}
// change of position
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
```

Time complexity: O(logn)
Space complexity: O(1)
Stability: unstable

# Exchange sort

## 5. Bubble sorting

Idea: in the unordered interval, the largest number bubbles to the end of the unordered interval through the comparison of adjacent numbers

```// 5. Bubble sorting
public static void bubbleSort(int[] array) {
// Unordered interval [0, len-i], i represents the number of ordered intervals
for (int i = 0; i < array.length; i++) {
// Ergodic unordered interval
for (int j = 0; j < array.length - i - 1; j++) {
// Compare and exchange two adjacent numbers with larger numbers
if (array[j] > array[j + 1]) {
// change of position
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
```

Time complexity: O(n^2)
Space complexity: O(1)
Stability: stable

## 6. Fast exhaust

Idea: select a number as the benchmark, make a round of traversal to determine the position of the benchmark (the position of the benchmark after the array is ordered), and ensure that all on the left are less than the benchmark and all on the right are greater than the benchmark, and then carry out the same operation on both sides of the benchmark. That is, the interval to be sorted is divided into two large and small intervals in each round, and the dividing point in the middle is the benchmark number.

```// 6. Fast exhaust
public static void quickSort(int[] array) {
quick(array, 0, array.length - 1);
}
// recursion
private static void quick(int[] array, int low, int high) {
// End condition
if (low >= high) return;
// Determine the dividing point of the large and small intervals
int piv = pivot(array, low, high);
// Recursion on both sides of interval
quick(array, low, piv);
quick(array, piv + 1, high);
}
// Divide the size range and return the division point subscript
private static int pivot(int[] array, int start, int end) {
// Determine the first place of the interval to be sorted as the benchmark number
int piv = array[start];
// Start looking for the location of the reference number
while (start < end) {
// Find the number less than the reference number from the right
while (array[end] >= piv) {
end --;
}
// Put it in front, because the number less than the reference number should not appear after the reference number
array[start] = array[end];
// Find a number greater than the reference number from the left
while (array[start] <= piv) {
start ++;
}
// Put it behind, because numbers larger than the benchmark should not appear before the benchmark
array[end] = array[start];
}
// The position where the left and right pointers meet is the position where the benchmark number should be after the array is ordered. Because after the previous round of exchange, the left side of the position is all less than the reference number, and the right side is all greater than the reference number
array[end] = piv;
// Returns the position where the reference number should be, and the position where the reference number should be after the array is ordered
return end;
}
```

Time complexity:

Time complexityAverage: O(n * log(n))Best (evenly divided): O(n * log(n))Worst case (ordered): O(n^2)

If it is divided evenly, the recursive logn layer traverses n numbers each time, so the time complexity is O(nlogn). If it is ordered, the reference position does not need to be moved. Each time, the interval will be divided by the first position, which is equivalent to that there is no interval and recursive n layers are required, so the time complexity is O(n^2).

Space complexity:

Time complexityAverage: O(log(n))Best (evenly divided): O(log(n))Worst case: O(n)

The reason is the same as above, the same as the number of recursive layers.

Stability: unstable
Optimization: for the purpose of more uniform division of intervals

1. Randomly selected benchmark
2. Three numbers middle method: select three numbers (leftmost, rightmost and middle) and exchange the number of middle size with the first number

# Merge sort

## 7. Merge and sort

Illustration:

Thought: if the array has only one number, it must be orderly. Merge sort, first decompose the array into the smallest subsequence, and then merge them, transforming the problem into merging two ordered sequences. It's used in the same fast platoon here Divide and conquer idea (put a connection first and talk later).

```// 7. Merge and sort
public static void mergeSort(int[] array) {
mergeSortInternal(array, 0, array.length - 1);
}
// recursion
private static void mergeSortInternal(int[] array, int low, int high) {
// End condition
if (low >= high) return;
int mid = (low + high) / 2;
// Recursive left and right parts
mergeSortInternal(array, low, mid);
mergeSortInternal(array, mid + 1, high);
// merge
merge(array, low, mid, high);
}
// Merge two ordered arrays array 1: [low, mid] array 2: [mid+1, high]
private static void merge(int[] array, int low, int mid, int high) {
// Starting position of two sections
int s1 = low;
int s2 = mid + 1;
// Merge result acceptance array
int tmp[] = new int[high - low + 1];
int k = 0;
// When s1 and s2 are not out of bounds, put the smaller number in front
while (s1 <= mid && s2 <= high) {
if (array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
}
if (array[s2] <= array[s1]) {
tmp[k++] = array[s2++];
}
}
// The rest of the two sections can be added to the back
while (s1 <= mid) {
tmp[k++] = array[s1++];
}
while (s2 <= high) {
tmp[k++] = array[s2++];
}
// Copy back to the original array
for (int i = 0; i < tmp.length; i++) {
// Note that the copy interval starts at low
array[low + i] = tmp[i];
}
}
```

Time complexity: analog fast scheduling, O(n * log(n))
Space complexity: O(n)
Stability: stable

# stability

If the sorting algorithm can ensure that the relative position of two equal data does not change after sorting, we call the algorithm a stable sorting algorithm
Law.

# Non recursive implementation of fast sorting and merge sorting

Fast exhaust:

```public static void quickSort2(int[] array) {
Stack<Integer> stack = new Stack<>();
int low = 0;
int high = array.length - 1;
int piv = pivot(array, low, high);
if (piv > low + 1) {  //Judge that there are at least two elements on the left
stack.push(low);
stack.push(piv - 1);
}
if (piv < high - 1) {
stack.push(piv + 1);
stack.push(high);
}
while (!stack.empty()) {
high = stack.pop();
low = stack.pop();
piv = pivot(array, low, high);
if (piv > low + 1) {
stack.push(low);
stack.push(piv - 1);
}
if (piv < high - 1) {
stack.push(piv + 1);
stack.push(high);
}
}
}
```

Merge sort:

```public static void mergeSort1(int[] array) {
for (int i = 1; i < array.length; i *= 2) {
merge1(array, i);
}
}
private static void merge1(int[] array, int gap) {
int s1 = 0;
int e1 = s1 + gap - 1;
int s2 = e1 + 1;
int e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;  // Prevention of cross-border
int[] tmp = new int[array.length];
int k = 0;

while (s2 < array.length) {   // There are two merging segments
while (s1 <= e1 && s2 <= e2) {
if (array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
}
if (array[s2] <= array[s1]) {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmp[k++] = array[s1++];
}
while (s2 <= e2) {
tmp[k++] = array[s2++];
}
s1 = e2 + 1;
e1 = s1 + gap - 1;
s2 = e1 + 1;
e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;
}
while (s1 < array.length) {
tmp[k++] = array[s1++];
}
for (int i = 0; i < tmp.length; i++) {
array[i] = tmp[i];
}

}
```

# Test code

```public class TestDemo {
public static void main(String[] args) {
int[] array = {6,6,4,2,9,5,7,1,3};
System.out.println(Arrays.toString(array));
//Sort.insertSort(array);
//Sort.shellSort(array);
//Sort.selectSort(array);
//Sort.heapSort(array);
//Sort.bubbleSort(array);
//Sort.quickSort(array);
//Sort.quickSort1(array);
//Sort.quickSort2(array);
Sort.mergeSort(array);
//Sort.mergeSort1(array);
System.out.println(Arrays.toString(array));
}
}
```

Added by kasitzboym on Sun, 09 Jan 2022 04:13:50 +0200