Eight sorting, three search is “data structure” among the very basic knowledge points, here in order to review the summary of the common eight sorting algorithm. The investigation of data structure and algorithm knowledge has become one of the most important points for interviewers. There are some algorithms that we will definitely use in our jobs and interviews. Tips: the front is very hungry, please bring POTS and pans.
| Sorting algorithm | Average time complexity |
|---|---|
| Bubble sort | O(n2) |
| Selection sort | O(n2) |
| Insertion sort | O(n2) |
| Hill sorting | O (n1.5) |
| Quick sort | O(N*logN) |
| Merge sort | O(N*logN) |
| Heap sort | O(N*logN) |
| Radix sort | O(d(n+r)) |
This article is suitable for algorithm learning friends, in addition, I organized a mainly contains the Java foundation, data structure, JVM, multithreading and other information, there is a need for friends can point a link to jump to get, link: docs.qq.com/doc/DRkdtRm…
BubbleSort
-
Basic idea: two numbers compare in size, the larger number sinks, the smaller number pops up.
-
Process:
- Compare two adjacent numbers, and if the second number is small, switch places.
- Compare from the back to the front, all the way to the top two numbers. Finally the minimum is swapped to the starting position so that the first minimum position is lined up.
- Continue to repeat the above process, and add section 2.3… N minus 1 minimum number of rows.
- Average time complexity: O(N2)
- Java code implementation:
public static void BubbleSort(int [] arr){
int temp;// Temporary variables
for(int i=0; i<arr.length-1; i++){ Arr. Length -1 times
for(int j=arr.length-1; j>i; j--){
if(arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp; }}}}Copy the code- Optimization:
- For the problem:
After the data order is sorted, the bubble algorithm will continue the next round of comparison until arr. Length-1, and the subsequent comparison is meaningless.
- Solution:
Set the flag bit to true if an exchange occurs. Set to false if there is no swap. In this case, if flag is still false after a round of comparison, that is, there is no exchange in this round, it indicates that the data sequence has been arranged and there is no need to continue.
public static void BubbleSort1(int [] arr){
int temp;// Temporary variables
boolean flag;// Whether to swap flags
for(int i=0; i<arr.length-1; i++){ Arr. Length -1 times
flag = false;
for(int j=arr.length-1; j>i; j--){
if(arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true; }}if(! flag)break; }}Copy the code2. Select sort
- Basic idea:
In an unordered array of length N, the first time through the n-1 number, find the smallest number to swap with the first element; The second time through the n-2 number, find the smallest number to swap with the second element; . The n-1st iteration finds the smallest value and swaps it with the n-1st element. The sorting is complete.
- Process:
-
Average time complexity: O(N2)
-
Java code implementation:
public static void select_sort(int array[],int lenth){
for(int i=0; i<lenth-1; i++){int minIndex = i;
for(int j=i+1; j<lenth; j++){if(array[j]<array[minIndex]){ minIndex = j; }}if(minIndex ! = i){inttemp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; }}}Copy the codeInsertion Sort
- Basic idea:
In the set of numbers to be sorted, assuming that the first n-1 number is sorted, now insert the NTH number into the previous ordered sequence so that the n number is sorted as well. Repeat until everything is sorted.
- Process:
-
Average time complexity: O(N2)
-
Java code implementation:
public static void insert_sort(int array[],int lenth){
int temp;
for(int i=0; i<lenth-1; i++){for(int j=i+1; j>0; j--){if(array[j] < array[j-1]){
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}else{ // No need to swap
break; }}}}Copy the codeShell Sort
- Preface:
Data sequence 1:13-17-20-42-28 By insertion sort, 13-17-20-28-42. Sequence 2:13-17-20-42-14 By insertion sort, 13-14-17-20-42. If the data sequence is basically ordered, it is more efficient to use insertion sort.
- Basic idea:
In a set of numbers to be sorted, subsequences are divided according to a certain increment, and the subsequences are sorted by insertion. Then gradually reduce the increments and repeat the process. Until the increment is 1, the data sequence is basically in order, and finally insertion sort is carried out.
- Process:
-
Average time complexity:
-
Java code implementation:
public static void shell_sort(int array[],int lenth){
int temp = 0;
int incre = lenth;
while(true){
incre = incre/2;
for(int k = 0; k<incre; k++){// Divide into subsequences based on increments
for(inti=k+incre; i<lenth; i+=incre){for(intj=i; j>k; j-=incre){if(array[j]<array[j-incre]){
temp = array[j-incre];
array[j-incre] = array[j];
array[j] = temp;
}else{
break; }}}}if(incre == 1) {break; }}}Copy the code5. Quicksort
- Basic idea :(divide and conquer)
- First, a number is taken from the array as the key value;
- Anything less than this number is to its left, anything greater than or equal to this number is to its right;
- Repeat the second step for the left and right small sequences until each interval has only one number.
- Assist with
- I = 0 at the beginning; j = 9; key=72
Since a[0] has been stored in the key, it can be interpreted as a hole in the array A [0], which can be filled with other data. I’m going to start with j and I’m going to find a number that’s less than key. When j=8, a[0] = a[8]; i++ ; Dig out a[8] and fill in the previous pit A [0]. Such a pit a[0] is solved, but a new pit a[8] is formed. What happens? Easy, find a number to fill the hole a[8]. If I =3, a[8] = a[3]; j– ; Dig out A [3] and fill the previous hole.
Array:72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
0 1 2 3 4 5 6 7 8 9
Copy the code- I = 3; j = 7; key=72
Repeat the steps above, first from back to front, then from front to back. When j=5, a[5] is dug out and filled into the previous pit, a[3] = a[5]; i++; I go back from I, and when I =5, I exit because I ==j. At this point, I = j = 5, and a[5] happens to be the pit dug last time, so insert key into A [5].
Array:48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
0 1 2 3 4 5 6 7 8 9
Copy the code- You can see that everything before a[5] is less than it, and everything after a[5] is greater than it. Therefore, repeat the above steps for a[0… 4] and a[6… 9].
Array:48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
0 1 2 3 4 5 6 7 8 9
Copy the code-
Average time complexity: O(N*logN)
-
Code implementation:
public static void quickSort(int a[],int l,int r){
if(l>=r)
return;
int i = l; int j = r; int key = a[l];// Select the first number as key
while(i<j){
while(i<j && a[j]>=key)// Find the first value less than key from right to left
j--;
if(i<j){
a[i] = a[j];
i++;
}
while(i<j && a[i]<key)// Find the first value greater than key from left to right
i++;
if(i<j){ a[j] = a[i]; j--; }}//i == j
a[i] = key;
quickSort(a, l, i-1);// recursive call
quickSort(a, i+1, r);// recursive call
}
Copy the codeThe key value can be selected in various forms, such as intermediate number or random number, which have different impacts on the complexity of the algorithm.
Merge Sort (Merge Sort)
- Basic idea:
Merge sort is an efficient sorting algorithm based on merge operation. This algorithm is a very typical application of divide and conquer. So let’s think about how to combine two ordered sequences. This is very simple, just compare the first number of 2 numbers, take the smallest number first, after taking the corresponding number deleted in the corresponding sequence. Then compare, if several columns are empty, it can directly take out the data of another column in turn.
// Merge the ordered arrays a[] and b[] into c[]
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
Copy the codeThe basic idea is to divide the array into two groups A and B. If the data in these two groups are all ordered, it can be very convenient to sort these two groups of data. How to get the two groups of data in order? We can divide groups A and B into two groups. By analogy, when there is only one data in the separated group, it can be considered that the group has reached the order, and then the two adjacent groups can be combined. In this way, by first recursive decomposition of the sequence, and then merge the sequence to complete the merge sort.
- Process:
- Average time complexity: O(NlogN)
The efficiency of merge sort is relatively high. Set the length of sequence as N, it takes logN steps to separate the sequence into small sequence, and each step is a process of merging ordered sequence. The time complexity can be denoted as O(N*logN), so the total is O(N*logN).
- Code implementation:
public static void merge_sort(int a[],int first,int last,int temp[]){
if(first < last){
int middle = (first + last)/2;
merge_sort(a,first,middle,temp);// Sort the left half
merge_sort(a,middle+1,last,temp);// Sort the right half
mergeArray(a,first,middle,last,temp); // merge the left and right parts}}Copy the code // Merge two sequences A [first-middle],a[middle+1-end]
public static void mergeArray(int a[],int first,int middle,int end,int temp[]){
int i = first;
int m = middle;
int j = middle+1;
int n = end;
int k = 0;
while(i<=m && j<=n){
if(a[i] <= a[j]){
temp[k] = a[i];
k++;
i++;
}else{ temp[k] = a[j]; k++; j++; }}while(i<=m){
temp[k] = a[i];
k++;
i++;
}
while(j<=n){
temp[k] = a[j];
k++;
j++;
}
for(int ii=0; ii<k; ii++){ a[first + ii] = temp[ii]; }}Copy the code7. HeapSort
- Basic idea:
- 88,85,83,73,72,60,57,48,42,6 icon: ()
- Average time complexity: O(NlogN)
Because the time complexity of each heap restoration is O(logN), the total number of n-1 heap restoration operations is O(logN), and the time complexity of each heap restoration operation is ALSO O(logN). The sum of the second operation times is still order N logN.
- Java code implementation:
// Build the minimum heap
public static void MakeMinHeap(int a[], int n){
for(int i=(n-1) /2 ; i>=0; i--){ MinHeapFixdown(a,i,n); }}N is the total number of nodes. The child nodes of node I are 2* I +1 and 2* I +2
public static void MinHeapFixdown(int a[],int i,int n){
int j = 2*i+1; / / child nodes
int temp = 0;
while(j<n){
// Find the smallest of the left and right child nodes
if(j+1<n && a[j+1]<a[j]){
j++;
}
if(a[i] <= a[j])
break;
// Larger nodes move down
temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
j = 2*i+1; }}Copy the code public static void MinHeap_Sort(int a[],int n){
int temp = 0;
MakeMinHeap(a,n);
for(int i=n-1; i>0; i--){ temp = a[0];
a[0] = a[i];
a[i] = temp;
MinHeapFixdown(a,0,i); }}Copy the code8. RadixSort
BinSort
- Basic idea:
The idea of BinSort is very simple: first create array A[MaxValue]; Then place each number in its appropriate position (for example, 17 in the array of subscript 17); The last traversal number group is the sorted result.
- Here is:
- Question:
BinSort’s sorting method wastes a lot of space when there are large values in the sequence.
RadixSort
- Basic idea:
Cardinality sort is based on BinSort and reduces space overhead by limiting cardinality.
- Process:
(1) First determine the cardinality is 10, the length of the array is 10. Each number 34 will find its position among the 10 numbers. (2) Instead of placing 34 at subscript 34, we divide 34 into 3 and 4. In the first order we place 34 at subscript 4, and in the second order we place 34 at subscript 3, and then we iterate through the array.
- Java code implementation:
public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
/ / A: the original array
//temp: temporary array
//n: the number of digits in the sequence
//k: the largest number of digits 2
/ / r: base 10
// CNT: stores the number of bin[I]
for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
/ / initialization
for(int j=0; j<r; j++){ cnt[j] =0;
}
// Count the number of numbers for each box
for(int j=0; j<n; j++){ cnt[(A[j]/rtok)%r]++; }// CNT [j] = CNT [j]
for(int j=1; j<r; j++){ cnt[j] = cnt[j-1] + cnt[j];
}
for(int j = n-1; j>=0; j--){// Focus on understanding
cnt[(A[j]/rtok)%r]--;
temp[cnt[(A[j]/rtok)%r]] = A[j];
}
for(int j=0;j<n;j++){
A[j] = temp[j];
}
}
}
Copy the codeThe final routine: a small praise, good luck, attention, permanent youth, a small reward, salary increase…
