“This is the fifth day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.
Java language is used for the purpose of the competition, and js/ TS version will be updated later.
Basic introduction
- Internal sorting
- All data that needs to be processed is loaded into internal memory for sorting.
- classification
- Insertion sort
- Direct insertion sort (stable, takes no extra space, O(n2))
- Hill sort (unstable, takes no extra space, O(nlogn))
- Selection sort
- Simple selection sort (unstable, takes no extra space, O(n2))
- Heap sort (unstable, takes no extra space, O(nlogn))
- Exchange sort
- Bubble sort (stable, takes no extra space, O(n2))
- Quick sort (unstable, takes no extra space, O(nlogn))
- Merge sort (stable, taking up extra space, O(nlogn))
- Radix sort (buckets sort) :(stable, takes up extra space, O(n* number of buckets))
- Insertion sort
- External sorting
Time complexity
- methods
- Ex post statistical method
- Ex ante estimation method
- Time frequency T(n) : The number of executions of statements in an algorithm
- Algorithm call time is proportional to the number of statements executed in the algorithm
- Time complexity O(n
- If T(n) is different, O(n) might be the same
- Common time complexity
- 1, log2n, n, nlog2n, n2, n3, nk, 2n, n!
- Average time complexity
- Worst time complexity
Spatial complexity
The storage space consumed by the algorithm
Relevant concepts
- Stable: does not change the relative position after sorting, for example, a= B, a was before B, after sorting still before B
- unstable
- Internal sort: All sort operations take place in memory
- External sort: A large amount of data is stored in disks, requiring data transfer between disks and memory
Bubble sort
Compare the values of adjacent elements from front to back, and find that reversing the exchange causes the larger values to gradually move from front to back.
-
The rules
- We loop through the array size -1 times
- The number of sequences per trip is gradually decreasing
- If we find that no swap has occurred in a particular sort, we can end the sort early (optimization)
public static void bubbleSort(int[] arr) {
int temp = 0; // Temporary variables
boolean flag = false; // Identifies the variable, indicating whether sorting has been done
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp; }}/ / optimization point
if(! flag) {// In a sort. Not a single exchange has occurred, which means it's in order
break;
} else {
// Reset the flag for next judgment
flag = false; }}}Copy the codeSelection sort
Select an element according to the specified rules, and then swap positions according to the specified to achieve the purpose of sorting.
-
The rules
- There are n minus 1 rounds of sorting
- Assume that the current number is the smallest, and compare from each subsequent number once
- If a smaller number is found, redetermine the minimum number and get the subscript
- After iterating through this array, swap
- Then narrow it down and repeat the process
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
// If it is not the minimum, record the minimum subscriptminIndex = j; }}// Find min subscript changed
if(minIndex ! = i) {inttemp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }}}Copy the codeInsertion sort
The element to be sorted is inserted to find the appropriate position of the element, so as to achieve the purpose of sorting
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int insertVal = arr[i]; // Store the values to be inserted
int index = i - 1; // The index of the number to be inserted that precedes the sorted array
while (index >= 0 && arr[index] > insertVal) {
// Move the number of the position back
arr[index + 1] = arr[index];
// Keep looking ahead
index--;
}
// Determine whether to insert
if (index + 1! = i) {// When exiting the loop, the insertion position has been found
arr[index + 1] = insertVal; }}}Copy the codeProblems: When the number to be inserted is relatively small, the number of backward moves increases significantly, which affects the efficiency
Hill sorting
Reduced increment sort
// Switch method (inefficient)
public static void shellSort(int[] arr) {
int temp = 0;
// Get gap: step size, group number
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// The gap position is the second element of the first group. Each time the gap increases by 1, switch a group and compare with the previous group one by one
for (int i = gap; i < arr.length; i++) {
// Compare forward, and the range of comparisons expands until the entire group
for (int j = i - gap; j >= 0; j -= gap) {
// If the current element is larger than the element with the added step, swap
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
/ / insert method
public static void shellSort2(int[] arr) {
// Get the step size
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// Insert sort directly from the gap element, one by one
for (int i = gap; i < arr.length; i++) {
// The subscript and value of the current element to be inserted
int index = i;
int value = arr[index];
if (arr[index] < arr[index - gap]) {
while (index - gap >= 0 && arr[index] < arr[index - gap]) {
arr[index] = arr[index - gap];
index -= gap;
}
// Find the position, break out of the loop, and assignarr[index] = value; }}}}Copy the codeQuick sort
The improvement of bubble sort, the basic idea: through a sort will be sorted into separate two parts of the data, one part of the data is smaller than the other part of the data, and then according to the sub-method of quick sort respectively. Procedures run recursively
// Quicksort
public static void quickSort(int[] arr, int left, int rigth) {
int l = left;/ / left subscript
int r = rigth;/ / right subscripts
// The value of the pivot
int pivot = arr[(rigth + left) / 2];
int temp = 0;// temp temporary variables are referenced at swap time
// While purpose:
// 1. Place the value smaller than pivot to the left
// 2. Place the value greater than pivot on the right
while (l < r) {// Premise: The left side is always less than the right side
// Keep looking to the left of pivot until the value is greater than or equal to the pivot value
while (arr[l] < pivot) {
l += 1;// or l++, but it seems inefficient to increment after, because you still end up with l=l+1 and l+=1
}
// Keep looking to the right of the pivot until the value is less than or equal to the pivot value
while (arr[r] > pivot) {
r -= 1;
}
// If l >= r then the values on both sides of pivot follow the rule:
// The left is all less than or equal to pivot, and the right is all greater than or equal to pivot.
if (l >= r) {
break;
}
/ / exchange
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
Arr [l] = arr[pivot] = arr[pivot] = arr[pivot] = arr[pivot
if (arr[l] == pivot) {
r -= 1;
}
// if arr[r] = arr[pivot] = arr[pivot], then l++ will be changed
if (arr[r] == pivot) {
l += 1; }}// if l==r, l++, r-- otherwise, the stack overflows in an infinite loop
if (l == r) {
l += 1;
r -= 1;
}
// Recurse to the left
if (left < r)
quickSort(arr, left, r);
// Recursive to the right
if (rigth > l)
quickSort(arr, l, rigth);
}
Copy the codeMerge sort
Adopt the idea of divide and conquer
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8.4.5.7.1.3.6.2};
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2; // Intermediate index
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
// Mergemerge(arr, left, mid, right, temp); }}// Merge methods
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // Initialize I, the initial index of the left ordered sequence
int j = mid + 1; // initialize j, the initial index of the ordered sequence on the right
int t = 0; // Specify the current index of temp array
// Fill the left and right sides (ordered) into the temp array
// Until one of the ordered sequences on the left and right sides is processed
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
} else{ temp[t++] = arr[j++]; }}// Fill all remaining data into temp in turn
while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
// Copy the elements of the temp array to arR
// Note that not all copies are made every time
t = 0;
int tempLeft = left;
while(tempLeft <= right) { arr[tempLeft++] = temp[t++]; }}}Copy the codeRadix sort
Stability, the most efficient stability sorting method
Problem: Space
An array with negative numbers is sorted without using radix sort
// Base sort
public static void radixSort(int[] arr) {
// Calculates the largest number of digits in the array
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if(arr[i] > max) { max = arr[i]; }}// Get the maximum number of digits
int maxLength = (max + "").length();
int[][] bucket = new int[10][arr.length];
// To record each bucket, store the number of buckets
int[] bucketElementCounts = new int[10];
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
// Fetch the value of the corresponding bit of each element
int digitOfElement = arr[j] / n % 10;
// Put the bucket into the corresponding bucket, then the corresponding amount ++
bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = arr[j];
}
int index = 0;
for (int k = 0; k < bucketElementCounts.length; k++) {
if (bucketElementCounts[k] > 0) {
// If there is data in the bucket, it is added to the original array
for (int t = 0; t < bucketElementCounts[k]; t++) {
// Take the element and put it into arRarr[index++] = bucket[k][t]; }}// After I +1, I need to clear 0
bucketElementCounts[k] = 0; }}}Copy the code