Insert class sort
Insert sort is inserting a new keyword in an ordered sequence. To achieve a new ordered sequence. Insertion sort generally has direct insertion sort, split half insertion sort and Hill sort.
1. Insert sort
1.1 Direct insertion sort
/** * moves the array */ by moving the large element back
public static void InsertSort(int[] A) {
for(int i = 1; i < A.length; i++) {
int temp = A[i]; // Temp is used to store elements and prevent subsequent moves from overwriting the previous element
int j;
for(j = i; j > 0 && temp < A[j- 1]; j--) { // If temp is smaller than the previous element, move the array
A[j] = A[j- 1];
}
A[j] = temp; // If temp is larger than the previous element, iterate over the next element}}/** * Here is a bubbling swap to find the best place to insert elements. The traditional way is to compare directly, move the array elements around and find the appropriate location */
public static void InsertSort2(int[] A) { //A[] is the given array to be sorted
for(int i = 0; i < A.length - 1; i++) { // go through the number group
for(int j = i + 1; j > 0; j--) { // Insert the new keyword in the ordered sequence
if(A[j] < A[j- 1]) { // Swap is used directly to move elements
int temp = A[j];
A[j] = A[j- 1];
A[j- 1] = temp; }}}}/** * for loop O(n^2) * for loop O(n^2
Copy the code1.2 Split insertion sort
/* * The main process of sorting from direct insert is: 1. Considering the nature of array linear tables, dichotomy can be used to quickly find the insertion position of keywords and improve the overall sorting time */
public static void BInsertSort(int[] A) {
for(int i = 1; i < A.length; i++) {
int temp = A[i];
// binary search
int low = 0;
int high = i - 1;
int mid;
while(low <= high) {
mid = (high + low)/2;
if (A[mid] > temp) {
high = mid - 1;
} else {
low = mid + 1; }}// Move the element back after inserting the keyword position
for(int j = i - 1; j >= high + 1; j--) {
A[j + 1] = A[j];
}
// Insert the element into the found position
A[high + 1] = temp; }}Copy the code2. Hill sort
Hill sort also known as reduced incremental sort, its essence is insertion sort, but the sequence to be sorted into several sub-sequences according to some rules, and then as the previous insertion sort on these sub-sequences. So when increments are 1, Hill sort is insertion sort, so the most important thing about Hill sort is the selection of increments.
The main steps are:
- Group arrays to be sorted by initial increment D
- Direct insertion sort of elements in each group
- Cut increment D in half, repeating steps 1, 2, and 3
- When d = 1, use direct insertion sort for the last time to complete the sort
/** * Hill sort implementation code is relatively concise, except incremental changes, basically and direct insert sequence is no different */
public static void ShellSort(int[] A) {
for(int d = A.length/2; d >= 1; d = d/2) { // Change the increment from d = "half the array length" to d = 1
for(int i = d; i < A.length; i++) { // Iterate over a range of increments [d, a.length-1]
if(A[i] < A[i - d]) { // If the element after the increment is smaller than the element before the increment, insert sort
int temp = A[i];
int j;
for(j = i - d; j >= 0 && temp < A[j-d]; j -= d) { // Sort the elements in the incremental sequence
A[j + d] = A[j]; // I + d is used here to move elements, since increment D may be greater than array subscript
} // Causes the array sequence to exceed the range of the arrayA[j + d] = temp; }}}}Copy the codeComplexity analysis
Second, exchange class sorting
Swap refers to the comparison of the keyword size of two elements to exchange the positions of two elements in the sequence, and finally achieve the ordered state of the whole sequence. There are bubble sort and quicksort
3. Bubble sort
Bubble sort is the process of comparing the values of two adjacent elements in a sequence and swapping them in the desired ascending or descending order. Finally, the whole sequence is ordered.
/** * bubble sort */
public static void BubbleSort(int[] A) {
for (int i = 0; i < A.length - 1; i++) { // Number of bubbles, number of traversal groups, number of ordered elements
for(int j = 0; j < A.length - i - 1; j++) { // Swap sort the remaining unordered elements
if(A[j] > A[j + 1]) {
int temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp; }}}}Copy the code4. Quicksort
Quicksort is actually a sort of swap class, but it is achieved through multiple partition operations. So this is the divide-and-conquer idea, where you divide a sequence into two subsequences and at each turn it picks a key from the sequence as the pivot, and moves the ones that are smaller than the pivot to the front and the ones that are bigger to the back. When all subsequences of this trip are divided by pivot, a group of shorter subsequences will be obtained, which will become the initial sequence set of the next trip. At the end of each trip, a keyword will reach the final position.
/** * Quicksort is A recursive divide-and-conquer sort based on bubble sort * @param A to be sorted * @param low * @param high */
public static void QuickSort(int[] A, int low, int high) {
if(low >= high) { // Recursive divide-and-conquer completes exit
return;
}
int left = low; // Set the left traversal pointer left
int right = high; // Set the traversal pointer right
int pivot = A[left]; // Set the pivot pivot. The default value is the left-most value of the array
while(left < right) { // Loop condition
while(left < right && A[right] >= pivot) {// If the right pointer points to an element larger than the pivot value, the right pointer moves to the left
right--;
}
A[left] = A[right]; // Replace it the other way around
while (left < right && A[left] <= pivot) {// If the left pointer points to an element less than the pivot value, the left pointer moves to the right
left++;
}
A[right] = A[left]; // Replace it the other way around
}
A[left] = pivot; // Place the pivot value in the final position
QuickSort(A, low, left - 1); // Recursively pivot the element to the left of the value
QuickSort(A, left + 1, high); // The element to the right of the pivot value according to this recursion
}
Copy the codeComplexity analysis
Three, selection sort
Selection sort is to select the element with the smallest keyword from the queue each time until the queue element is selected.
5. Simple selection sort
/** * simply select sort * @param A to be sorted array */
public static void SelectSort(int [] A) {
for (int i = 0; i < A.length; i++) {
int min = i; // Iterate over the minimum subscript in the selection sequence
for (int j = i + 1; j < A.length; j++) { // Iterate over the current sequence and select the minimum value
if(A[j] < A[min]) { min = j; }}if(min ! = i) {// Select and swap minimum values
inttemp = A[min]; A[min] = A[i]; A[i] = temp; }}}Copy the code6. The heap sort
A heap is a data structure that can be thought of as a complete binary tree in which the values of any non-leaf nodes are no greater than (or less than) the values of its left and right children. If the parent is large and the children are small, the heap is called the big top heap; If the parent and child are large, the heap is called the small top heap.
The process of heap sort is actually to construct a heap of heapsort sequences, take the largest in the heap, adjust the remaining elements in the heap, and then find the largest take. This is repeated until the extracted sequence is in order.
The main sorting steps can be divided into (taking the big top heap as an example) :
BuildMaxHeap() BuildMaxHeap()
AdjustMaxHeap() AdjustMaxHeap()
HeapSort(); HeapSort()
/** * heap sort (big top heap) * @param A to be sorted array */
public static void HeapSort(int [] A) {
BuildMaxHeap(A); / / set up the heap
for (int i = A.length - 1; i > 0; i--) { // The number of sorts is len-l
int temp = A[i]; // Replace the top element (A[0]) with the end element to update the array length
A[i] = A[0];
A[0] = temp;
AdjustMaxHeap(A, 0, i); // Resize the new heap, resize the unsorted array again}}/** * create A big top heap * @param A to be sorted array */
public static void BuildMaxHeap(int [] A) {
for (int i = (A.length / 2) - 1; i >= 0 ; i--) { // Filter nodes (non-leaf nodes) in [0,len/2] from bottom to topAdjustMaxHeap(A, i, A.length); }}/** * Adjust the size of the big top heap * @param A array * @param k the subscript of the root of the big top heap * @param len The size of the array */
public static void AdjustMaxHeap(int [] A, int k, int len) {
int temp = A[k];
for (int i = 2*k + 1; i < len; i = 2*i + 1) { // Make heap adjustments from bottom to top, starting with the last leaf
if (i + 1 < len && A[i] < A[i + 1]) { // Compare the size of the two children
i++;
}
if (temp < A[i]) { // If the node is larger than the parent, replace the parent
A[k] = A[i]; // Update the array subscript to continue the heap adjustment up
k = i;
} else {
break; // If this node is smaller than the parent node, the heap adjustment will be skipped and continue upward
}
}
A[k] = temp; // Put the node where it should be after the comparison
}
Copy the codeComplexity analysis
Fourth, other internal sorting
7. Merge sort
Merge sort is to combine multiple ordered tables into a new ordered table. This algorithm is a typical application of divide and conquer. That is, the sequence to be sorted into a number of sub-sequences, each sub-sequence is ordered. Then the ordered subsequence is combined into a whole ordered sequence. The analysis is mainly carried out by two-way merge sort.
The sorting is mainly divided into two steps:
- Split: Split the sequence in half at a time
- Merge: Sort divided sequences in pairs and merge them
private static int[] aux;
/** * initializes the auxiliary array aux * @param A to be arranged array */
public static void MergeSort(int [] A) {
aux = new int[A.length];
MergeSort(A,0,A.length- 1);
}
/** * Split the array into two parts, Merge() * @param A array to be arranged * @param low array start subscript * @param high array end subscript */
public static void MergeSort (int[] A, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
MergeSort(A, low, mid);
MergeSort(A, mid + 1, high); Merge(A, low, mid, high); }}/** * combine [low, mid] with [mid+1, High] ordered sequence merge * @param A unarranged array * @param low array start subscript * @param mid array middle separator subscript * @param high array end subscript */
public static void Merge (int[] A, int low, int mid, int high) {
int i, j, k;
for (int t = low; t <= high; t++) {
aux[t] = A[t];
}
for ( i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
if(aux[i] < aux[j]) {
A[k] = aux[i++];
} else{ A[k] = aux[j++]; }}while (i <= mid) {
A[k++] = aux[i++];
}
while(j <= high) { A[k++] = aux[j++]; }}Copy the code8. Radix sort
Radix sort is special, it is by the size of the keyword digit bits to sort. It is a method to sort single logical keywords by the idea of multi-keyword sorting.
It has two main sorting methods:
- Highest bit priority method (MSD) : according to the weight of the keyword bit, the molecular sequence is divided in descending order
- LSD: the molecular sequence is divided according to the key bit weight
The idea of radix sort:
- distribution
- recycling
/** * find the longest digit in array * @param A waiting array * @return MaxDigit */
public static int MaxDigit (int [] A) {
if (A == null) {
return 0;
}
int Max = 0;
for (int i = 0; i < A.length; i++) {
if(Max < A[i]) { Max = A[i]; }}int MaxDigit = 0;
while (Max > 0) {
MaxDigit++;
Max /= 10;
}
return MaxDigit;
}
/** * internalize the radix sort operation in A two-dimensional array * @param A to be sorted array */
public static void RadixSort(int [] A) {
// Create a two-dimensional array, analogous to the allocation collection operation in rectangular coordinates
int[][] buckets = new int[10][A.length];
int MaxDigit = MaxDigit(A);
//t Is used to extract the number of digits of the keyword
int t = 10;
// Loop by the number of sort runs
for (int i = 0; i < MaxDigit; i++) {
// The number of elements stored in a bucket is the Y-axis of buckets' array
int[] BucketLen = new int[10];
// Allocate operation: put the elements of the array to be sorted into the bucket accordingly
for (int j = 0; j < A.length ; j++) {
// Buckets is the X-axis of buckets' array
int BucketIndex = (A[j] % t) / (t / 10);
buckets[BucketIndex][BucketLen[BucketIndex]] = A[j];
// The number of elements in the bucket increases with this subscript
BucketLen[BucketIndex]++;
}
// Collect the sorted elements from the bucket
int k = 0;
for (int x = 0; x < 10; x++) {
for (int y = 0; y < BucketLen[x]; y++) {
A[k++] = buckets[x][y];
}
}
t *= 10; }}Copy the code### Complexity analysis
Note: In radix sort, n is the keyword number in the sequence, D is the keyword number, and RD is the number of keyword number