If there are any deficiencies, please correct them. Thank you very much and learn together.
catalogue
sort
The so-called sorting is to make a string record , according to one or some of them keyword Arranged in ascending or descending order operation . Sorting algorithm is how to arrange records according to requirements. Sorting algorithm has received considerable attention in many fields, especially in the processing of large amounts of data. An excellent algorithm can save a lot of resources. Considering various limitations and specifications of data in various fields, it takes a lot of reasoning and analysis to get an excellent algorithm in line with the reality.
Common sorting algorithms
Bubble sort, insert sort, select sort, Hill sort, merge sort, quick sort
Bubble sorting
Bubble sorting The algorithm is to move the smaller elements forward or to move the larger elements back. This method mainly compares the size of two adjacent elements, and exchanges the positions of the two elements according to the comparison results and algorithm rules. In this way, the sorting purpose can be achieved by comparing and exchanging one by one. The basic idea of bubble sorting is to first compare the size of the keywords of the first and second records. If it is in reverse order, exchange the two records, then compare the keywords of the second and third records, and so on. Repeat the above calculation until the comparison between the keywords of the (n1) and Nth records is completed. After that, The second and third sorting shall be carried out according to the above process until the whole sequence is in order. In the sorting process, it should be noted that when the size of two adjacent elements is the same, this step does not need to exchange positions. Therefore, it also shows that bubble sorting is a strict stable sorting algorithm, which does not change the relative position relationship between the same elements in the sequence.
Code implementation:
public static void main (String[] args){
int arr[] = {9,2,6,8,4};
//Bubble sorting
for(int i =0;i<arr.length;i++){//Outer loop, traversal times
for(int j = i;j<arr.length-i-1;j++){
//Inner loop, in ascending order (if the former is larger than the latter, it will be exchanged, otherwise it will remain unchanged), and in descending order, vice versa
//Cycle once and fix a value
if(arr[j]>arr[j+1]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
//process
2,6,8,4,9
2,6,4,8,9
2,4,6,8,9
2,4,6,8,9
2,4,6,8,9
}Insert sort
Insert sort The algorithm is based on the case that a sequence has been orderly arranged, and the elements are added according to the original sorting method by inserting one element at a time. This comparison starts from the end of the ordered sequence, that is, the element to be inserted into the sequence is compared with the largest element in the ordered sequence first. If it is greater than the largest element, it can be directly inserted after the largest element. Otherwise, it can be compared with the previous one until the position that should be inserted is found. The basic idea of insertion sorting is to insert one record to be sorted into the previously ordered subsequence according to its keyword size at a time, and find the most appropriate position until all records are inserted. During execution, if the position equal to the inserted element is encountered, the element to be inserted is placed after the equal element. Therefore, the sequence of the original sequence is not changed after the element is inserted. We believe that insertion sorting is also a stable sorting method. Insert sort is divided into direct insert sort Binary Insertion Sort And Hill sort 3 categories.
Code implementation:
public static void main (String[] args){
//Insert sort
int arr[] = {7,2,5,6,9};
for(int i = 1 ;i<arr.length; i++){//Outer circulation
for(int j = i;j>0; j--){//The memory loop compares with the data arranged in the front. If the later data is smaller than the previous data, it will be exchanged
if(arr[j]<arr[j-1]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}else{//If not less than, the insertion is completed and the inner loop is exited
break;
}
}
}
}
//process
2,7,5,6,9
2,5,7,6,9
2,5,6,7,9Select sort
Select sort The basic idea of the algorithm is to select the smallest element for each location. The basic idea of selective sorting is based on Direct selection sort And heap sorting are two basic simple sorting methods. First, select all elements from the first position, select the smallest of all elements to this position, then select the second position, and select the smallest of the remaining elements to this position; By analogy, repeat the selection of "minimum element" until the element selection at position (n-1) is completed, then there is only the only maximum element at position n, and there is no need to select at this time. When using this sort, pay attention to one of the details that is different from the bubble method. For example: sequence 58539. We know that selecting the first element "5" for the first time will exchange with element "3", so the relative order between the two same elements "5" in the original sequence will be changed. Therefore, we say that selective sorting is not a stable sorting algorithm, it will destroy the stability in the calculation process.
Code implementation:
public static void main(String[] args){
//Select sort
int arr[] = {6,5,3,2,4};
for(int i = 0 ;i < arr.length; i++){
//The default first is the minimum value
int min = arr[i];
int index = i;
for(int j = i+1; j< arr.length; j++){
if(arr[j]<min){
min = arr[j];
index = j;
}
}
int temp =arr[i];
arr[i] = min;
arr[index] = temp;
System.out.println(Arrays.toString(arr));
}
}
//process
[2, 5, 3, 6, 4]
[2, 3, 5, 6, 4]
[2, 3, 4, 6, 5]
[2, 3, 4, 5, 6]
[2, 3, 4, 5, 6]Shell Sort
It is basically the same as insertion sorting. The difference is that the step size of each cycle is halved. The basic principle is similar to insertion sorting, but the difference is. Insert sort by spacing multiple data.
Code implementation:
public static void main (String[] args){
//Shell Sort
int arr[] = {7,9,5,1,3};
for(int i = arr.length/2;i>0;i/=2){
for(int j = i;j<arr.length;j++){
for(int k = j;k>0&&k-i>=0;k-=i){
if(arr[k]<arr[k-i]){
int temp = arr[k-i];
arr[k-i] = arr[k];
arr[k] = temp;
System.out.println(Arrays.toString(arr));
}else{
break;
}
}
}
}
}
//process
[5, 9, 7, 1, 3]
[5, 1, 7, 9, 3]
[5, 1, 3, 9, 7]
[3, 1, 5, 9, 7]
[1, 3, 5, 9, 7]
[1, 3, 5, 7, 9]Merge sort
Split the list in a peer-to-peer manner. When splitting small and fast, split and merge the smallest pieces according to the original. When merging, start comparing the sizes on the left of the left and right pieces. Small data is placed in a new block. The simplest thing is to split the two halves into the smallest unit, and then merge the two halves of data into an orderly list.
Code implementation:
public static void main(String[] args){
//Merge sort
int arr[] = {7, 5, 3, 2, 4, 1,6};
int start = 0 ;
int end = arr.length-1;
mergeSort(arr,start,end);
}
public static void mergeSort(int[] arr, int start, int end) {
//Judge whether the split is not the smallest unit
if (end - start > 0) {
//Split again and know the data split into one by one
mergeSort(arr, start, (start + end) / 2);
mergeSort(arr, (start + end) / 2 + 1, end);
//Record start / end position
int left = start;
int right = (start + end) / 2 + 1;
//Record the sorting results of each small unit
int index = 0;
int[] result = new int[end - start + 1];
//If the two pieces of data after scoring still exist
while (left <= (start + end) / 2 && right <= end) {
//Compare the size of the two pieces of data, then assign a value, and move the subscript
if (arr[left] <= arr[right]) {
result[index] = arr[left];
left++;
} else {
result[index] = arr[right];
right++;
}
//Subscript of mobile unit record
index++;
}
//When a piece of data does not exist
while (left <= (start + end) / 2 || right <= end) {
//Direct assignment to record subscript
if (left <= (start + end) / 2) {
result[index] = arr[left];
left++;
} else {
result[index] = arr[right];
right++;
}
index++;
}
//Finally, the new data is assigned to the original list and is the subscript after corresponding blocking.
for (int i = start; i <= end; i++) {
arr[i] = result[i - start];
System.out.println(Arrays.toString(arr));
}
}
}
//process
[5, 5, 3, 2, 4, 1, 6]
[5, 7, 3, 2, 4, 1, 6]
[5, 7, 2, 2, 4, 1, 6]
[5, 7, 2, 3, 4, 1, 6]
[2, 7, 2, 3, 4, 1, 6]
[2, 3, 2, 3, 4, 1, 6]
[2, 3, 5, 3, 4, 1, 6]
[2, 3, 5, 7, 4, 1, 6]
[2, 3, 5, 7, 1, 1, 6]
[2, 3, 5, 7, 1, 4, 6]
[2, 3, 5, 7, 1, 4, 6]
[2, 3, 5, 7, 1, 4, 6]
[2, 3, 5, 7, 1, 4, 6]
[1, 3, 5, 7, 1, 4, 6]
[1, 2, 5, 7, 1, 4, 6]
[1, 2, 3, 7, 1, 4, 6]
[1, 2, 3, 4, 1, 4, 6]
[1, 2, 3, 4, 5, 4, 6]
[1, 2, 3, 4, 5, 6, 6]
[1, 2, 3, 4, 5, 6, 7]Quick sort
Quick sort The basic idea is that the elements of the sequence to be sorted are divided into two blocks by a one-time sorting algorithm, in which one part of the elements should be less than or equal to the other part of the sequence elements, and then the elements of the divided two sequences are implemented again according to this method Quick sorting algorithm , the whole process of sorting implementation can be called recursively, and finally the unordered sequence elements to be sorted can be changed into an ordered sequence.
Code implementation:
public static void main(String[] args){
int arr[] = {7, 5, 3, 2, 4, 1, 8, 9, 6};
//Quick sort
int low = 0;
int high = arr.length - 1;
quickSort(arr, low, high);
}
public static void quickSort(int[] arr, int low, int high) {
//If the pointer is in the same position (when there is only one data), exit
if (high - low < 1) {
return;
}
//Flag, starting with high pointer or low pointer (default high pointer)
boolean flag = true;
//Record the actual position of the pointer
int start = low;
int end = high;
//The default middle value is the first value of the low pointer
int midValue = arr[low];
while (true) {
//High pointer movement
if (flag) {
//If the data on the right side of the list is greater than the middle value, move to the left
if (arr[high] > midValue) {
high--;
} else if (arr[high] < midValue) {
//If less than, the initial low pointer value is overwritten, and the low pointer is moved, and the flag bit is changed to move from the low pointer
arr[low] = arr[high];
low++;
flag = false;
}
} else {
//If the low pointer data is less than the middle value, the low pointer moves to the right
if (arr[low] < midValue) {
low++;
} else if (arr[low] > midValue) {
//If the value of the low pointer is greater than the middle value, the data when the high pointer stays is overwritten and the high pointer is moved to the left. Switch to high pointer movement
arr[high] = arr[low];
high--;
flag = true;
}
}
//When the positions of the two pointers are the same, the position of the intermediate value is found and the loop exits
if (low == high) {
arr[low] = midValue;
System.out.println(Arrays.toString(arr));
break;
}
}
//Then there's the middle value, and the one to the left is less than the middle value. The on the right is greater than the middle value.
//Then quickly sort the left and right lists
quickSort(arr, start, low -1);
quickSort(arr, low + 1, end);
}
//process
[6, 5, 3, 2, 4, 1, 7, 9, 8]
[1, 5, 3, 2, 4, 6, 7, 9, 8]
[1, 5, 3, 2, 4, 6, 7, 9, 8]
[1, 4, 3, 2, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]Common sorting is here first..