# Introduction:

There are two kinds of comparison algorithms, one is comparison algorithm, the other is non comparison algorithm.

- Comparison algorithms are: bubble sort, select sort, insert sort, merge sort, heap sort, fast sort, Hill sort.
- Non comparison algorithms are: count sort, cardinality sort, bucket sort.

https://gitee.com/linqiankun/Utils/tree/v3.0/

## Time complexity:

Ranking method | Best case | Average condition | Worst case | Auxiliary space | stability |

Bubble sort | n | n^2 | n^2 | 1 | yes |

Selection sort | n^2 | n^2 | n^2 | 1 | no |

Insertion sort | n | n^2 | n^2 | 1 | yes |

Merge sort | nlogn | nlogn | nlogn | n | yes |

Heap sort | nlogn | nlogn | nlogn | 1 | no |

Quick sort | nlogn | nlogn | n^2 | 1 | no |

Shell Sort | n^1.3 | nlogn～n^2 | n^2 | logn~n | no |

# Comparison algorithm:

## Bubble sort

### General bubble sorting

Bubble sorting is a very simple sorting algorithm. By looping through the elements in the array, the two adjacent elements are compared in turn. If the sorting rules are not met, the position exchange is carried out until no element needs to be exchanged, and the sorting is completed.

This algorithm will slowly make the elements float out in the required order.

Time complexity: O(n) - O (n ^ 2) - O (n ^ 2)

Bubble sort run order:

- Compare adjacent elements and exchange positions according to sorting rules.
- The first step is to operate each pair of adjacent elements. After the operation, the team will finally meet the conditions. The inner layer of the circulatory body circulates one circle.
- Do the above for all elements until the sorting is complete.

`public static void bubbleSorted(int[] array, StatusCode statusCode) { //The outer loop is finished, and the array sorting is finished for (int i = 0; i < array.length; i++) { //After the inner loop runs for one loop, an ordered data will be added at the end of the array for (int j = 0; j < array.length; j++) { int falg = SortUtil.compare(array[i], array[j]); //The sorting direction can be modified if (falg == statusCode.getCode()) { //Exchange data location SortUtil.swap(array, i, j); } } } }`

### Cocktail sort

The two-level cycle of common bubble sorting is constantly compared from front to back, and the cocktail sorting is optimized. The comparison order is modified to a comparison rule that shrinks from front to back to middle. From the front to the back, it can be determined that the last element of the queue is the largest, and from the back to the front, it can be determined that the starting element of the queue is the smallest, so that the sorting is completed at the end of the middle.

`public static void CocktailSort(int[] array, int n) { int left = 0; // Initialization boundary int right = n - 1; while (left < right) { for (int i = left; i < right; i++) // First half round, put the largest element behind { if (array[i] > array[i + 1]) { SortUtil.swap(array, i, i + 1); } } right--; for (int i = right; i > left; i--) // In the second half, put the smallest element in front { if (array[i - 1] > array[i]) { SortUtil.swap(array, i - 1, i); } } left++; } }`

## Selection sort

Select sorting to determine the front end of the array as the sorted queue. Select the best elements satisfying the sorting rules from the subsequent unsorted queues each time and place them at the end of the sorted queue until all the unsorted queues are sorted.

Bubble sorting moves all the data to the right place by exchanging the positions of adjacent data. Select sort every time you traverse, you can select the data you need to place it in the right place.

Time complexity: O(n^2)~O(n^2)~O(n^2)

Select sort run order:

- Determine the minimum queue location.
- Select the best one from the unsorted queue to be placed at the end of the sorted queue.
- Loop through the array until all elements are sorted.

`public static void selectionSorted(int[] array, StatusCode statusCode) { //Determine the minimum position for (int i = 0; i < array.length; i++) { int min = i; //Determine the data stored in the smallest location for (int j = i + 1; j < array.length; j++) { //Use the flag to find the smallest / largest if (statusCode.getCode() == SortUtil.compare(array[j], array[min])) { min = j; } } //Put the smallest first if (min != i) { SortUtil.swap(array, i, min); } } }`

## Insertion sort

### Normal insertion sort

Insert a sort to determine the front end of the array as a sorted queue. The first element of the unsorted queue is selected in each traversal and inserted into the sorted queue by comparison. Until all data is sorted.

Select the appropriate place in the unsorted queue, insert the first place. The selection sort comparison occurs when the selection data is not sorted in the queue. Insert sort comparison occurs when the sorted queue is looking for the appropriate location.

Time complexity: O(n)~O(n^2)~O(n^2)

Execution sequence:

- Determine the minimum queue location.
- Takes the first element of the unsorted queue.
- Compare this element with the elements of the sorted queue one by one and put it in the appropriate location.
- Continue until all elements are sorted out.

`public static void insertionSorted(int[] array, StatusCode statusCode) { //By default, the 0 is sorted, i is sorted before for (int i = 1; i < array.length; i++) { int get = array[i]; int j = i - 1; //Search forward from the reverse of current bit value while (j >= 0 && statusCode.getCode() == SortUtil.compare(get, array[j])) { array[j + 1] = array[j]; j--; } //Place on the right side of the position if the comparison conditions are not met array[j + 1] = get; } }`

### Bisection insertion sort

Insertion sorting needs to find out the appropriate location of the selected data in the sorted queue. The search algorithm can be modified to binary search to improve efficiency.

`public static void insertionSortedDichotomy(int[] array, StatusCode statusCode) { for (int i = 1; i < array.length; i++) { int get = array[i]; int left = 0; int right = i - 1; //The location of binary search data is also in the previous queue while (left <= right) { int mid = (left + right) / 2; if (statusCode.getCode() == SortUtil.compare(get,array[mid])) // if (array[mid] > get) right = mid - 1; else left = mid + 1; } //It takes the data of position i, and moves backward after left for (int j = i - 1; j >= left; j--) { array[j + 1] = array[j]; } array[left] = get; } } }`

## Merge sort

In my opinion, merging and sorting is a kind of divide and rule thought, which can solve the problem by making the big things smaller and smaller. Merge sort merges two sorted arrays into a sorted array to complete the sorting of the array. The idea of recursion can be adopted, starting from the merging of two or two, to the merging of four or four, and the merging of eight or eight, until all the data are sorted.

Time complexity: O(nlogn)~O(nlogn)~O(nlogn)

Execution sequence:

- The array with the length of 8 is divided into the array with the length of 4 for merging, and the array with the length of 4 is divided into the array with the length of 2 for merging through recursion.
- If the length of merging return is 4, the length of continue merging is 8. End of sorting.
- Arrays of any length are continuously split according to this idea.

Merge sort

`public static void mergeSortedRecursion(int[] array, StatusCode statusCode, int left, int right) { if (left == right) return; int mid = (left + right) / 2; //First half array merging mergeSortedRecursion(array, statusCode, left, mid); //Merging of the second half array mergeSortedRecursion(array, statusCode, mid + 1, right); //Merging and merging merge(array, statusCode, left, mid, right); }`

Array merging algorithm

`private static void merge(int[] array, StatusCode statusCode, int left, int mid, int right) { int len = right - left + 1; int[] temp = new int[len]; int index = 0; //First half array start int i = left; //Start of the second half array int j = mid + 1; //Merging operation of two groups of data while (i <= mid && j <= right) { temp[index++] = statusCode.getCode() == SortUtil.compare(array[i], array[j]) ? array[i++] : array[j++]; } //The above loop cannot loop all the data of two subarrays to while (i <= mid) { temp[index++] = array[i++]; } while (j <= right) { temp[index++] = array[j++]; } //Put the data into the original int tindex = 0; while (tindex < temp.length) { array[left++] = temp[tindex++]; } }`

## Heap sort

Heap sorting is a sort algorithm based on the data structure of heap. Sort by constructing an unordered array into a large top heap or a small top heap.

Time complexity: O(nlogn)~O(nlogn)~O(nlogn)

Execution rules:

- The input unordered queue is constructed into a large top heap.
- Exchange the heap top element with the heap tail element, and the heap top element is the largest element in the sequence before replacement.
- After the replacement, the reactor structure was adjusted to become a large top reactor again.
- Loop through the second and third steps until the heap element is 1 and the sorting is complete.

Heap sorting algorithm

`void HeapSort(int A[], int n) { int heap_size = BuildHeap(A, n); // Build a maximum heap while (heap_size > 1) // The number of heap (unordered area) elements is greater than 1, and sorting is not completed { // Swap the top element of the heap with the last element of the heap and remove the last element from the heap // The exchange operation here is likely to disrupt the stability of the following elements, so heap sorting is an unstable sorting algorithm Swap(A, 0, --heap_size); Heapify(A, 0, heap_size); // Start with the new heap top element and adjust the heap downward, time complexity O(logn) } }`

Heap algorithm

`int BuildHeap(int A[], int n) // Heap building, time complexity O(n) { int heap_size = n; for (int i = heap_size / 2 - 1; i >= 0; i--) // Heap adjustment from each non leaf node down Heapify(A, i, heap_size); return heap_size; }`

Heap adjustment algorithm

`void Heapify(int A[], int i, int size) // Heap adjustment from A[i] down { int left_child = 2 * i + 1; // Left child index int right_child = 2 * i + 2; // Right child index int max = i; // Select the maximum of the current node and its left and right children if (left_child < size && A[left_child] > A[max]) max = left_child; if (right_child < size && A[right_child] > A[max]) max = right_child; if (max != i) { Swap(A, i, max); // Exchange the current node with its largest (direct) child node Heapify(A, max, size); // Recursive call, continue heap adjustment from current node down } }`

## Quick sort

The rapid sorting of personal feeling is another way of merging and sorting. Through the process of dividing an array into two partitions according to the datum data, and then dividing the partitions recursively, we know that all data segmentation and sorting are completed.

Time complexity: O(nlogn)~O(nlogn)~O(n^2)

Execution sequence:

- Select a data from the array as the benchmark.
- Place the data larger than the datum on one side of the datum, and the data smaller than the datum on the other side, forming two partitions.
- Recursively operate 1 and 2 on two partitions.
- Until the two sides cannot be further divided.

Quick sort

`public static void quickSorted(int[] array, int left, int right, StatusCode statusCode) { if (left >= right) return; int pivot_index = partition(array, left, right, statusCode); // Index of datum //Divide recursively quickSorted(array, left, pivot_index - 1, statusCode); quickSorted(array, pivot_index + 1, right, statusCode); }`

Divide and conquer block

`private static int partition(int[] array, int left, int right, StatusCode statusCode) // Partition function { int pivot = array[right]; // Here, the last element is selected as the benchmark every time int tail = left - 1; // tail is the index of the last element of the subarray less than the benchmark for (int i = left; i < right; i++) // Traverse elements other than benchmark { //It will destroy the stability if (SortUtil.compare(pivot, array[i]) == 0 || !(statusCode.getCode() == SortUtil.compare(pivot, array[i]))) // If (array [i] < = pivot) / / put the elements less than or equal to the benchmark to the end of the previous sub array { SortUtil.swap(array, ++tail, i); } } SortUtil.swap(array, tail + 1, right); // Finally, the benchmark is placed behind the previous subarray, and the remaining subarray is the subarray larger than the benchmark // This operation is likely to disrupt the stability of subsequent elements, so fast sorting is an unstable sorting algorithm return tail + 1; // Returns the index of the benchmark } }`

## Shell Sort

Split the queues to be sorted by selecting different cloth lengths. The insertion order is used within each group. By continuously splitting and sorting, the unordered queue will be changed to be more and more orderly. When the cloth length is 1, the last sorting (insertion sorting) is performed to complete the sorting of the queue.

The time consumption of the last sorting can be reduced by continuously splitting and sorting through the hill value. It can effectively reduce the time consumption of moving array elements.

Time complexity: O(n^1.3)~O(nlogn)~O(n^2)~O(n^2)

Execution sequence:

- Determine Hill value
- Direct insertion sorting in steps of hill value
- Reduce the hill value and repeat step 2
- The last step is to directly insert and sort with the hill value of 1, and the sorting is completed

`public static void shellSorted(int[] array, StatusCode statusCode) { int shell = 0; //Find the maximum Hill value while (shell <= array.length) { shell = shell * 3 + 1; } //Reduce sorting complexity through Hill while (shell >= 1) { //After determining the hill value, the internal use is to insert the sorting directly for (int i = shell; i < array.length; i++) { int j = i - shell; int get = array[i]; while (j >= 0 && statusCode.getCode() == SortUtil.compare(get, array[j])) { array[j + shell] = array[j]; j = j - shell; } array[j + shell] = get; } //jian shell = (shell - 1) / 3; } }`