# Introduction:

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

1. Comparison algorithms are: bubble sort, select sort, insert sort, merge sort, heap sort, fast sort, Hill sort.
2. 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:

1. Compare adjacent elements and exchange positions according to sorting rules.
2. 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.
3. 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:

1. Determine the minimum queue location.
2. Select the best one from the unsorted queue to be placed at the end of the sorted queue.
3. 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:

1. Determine the minimum queue location.
2. Takes the first element of the unsorted queue.
3. Compare this element with the elements of the sorted queue one by one and put it in the appropriate location.
4. 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:

1. 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.
2. If the length of merging return is 4, the length of continue merging is 8. End of sorting.
3. 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:

1. The input unordered queue is constructed into a large top heap.
2. Exchange the heap top element with the heap tail element, and the heap top element is the largest element in the sequence before replacement.
3. After the replacement, the reactor structure was adjusted to become a large top reactor again.
4. 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;
}``````

``````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:

1. Select a data from the array as the benchmark.
2. 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.
3. Recursively operate 1 and 2 on two partitions.
4. 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:

1. Determine Hill value
2. Direct insertion sorting in steps of hill value
3. Reduce the hill value and repeat step 2
4. 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;
}
}``````

Keywords: Programming shell less

Added by joecrack on Fri, 13 Mar 2020 09:02:27 +0200