preface
Algorithm is the soul of programming, not algorithm programmers only to do code farmers. 10, 000 crit damage! At the same time, it also aroused my own morale. Frankly speaking, as a programmer, I have always known the importance of algorithm, but I have not been good enough in algorithm, and even seldom touched it after I learned this course in college. Because at the beginning I labeled the algorithm as difficult, annoying, and not used very much, and now I think about it as a way of avoiding the problem. So decided to mend, start from scratch!
This article was published on my personal blog [www.xiongfrblog.cn]
introduce
There are stages in the learning of algorithms, from beginner to simple, then to complex, and then to simple. Finally, simplicity is the ability to pinpoint the simplest solution to a problem once you reach a certain level. Like xiuxian, a real master is enough to repel thousands of horses!
Algorithm inside the most commonly used is also the most basic sorting algorithm and search algorithm, this article mainly explains the algorithm inside the most classic ten sorting algorithm. Here we divide the top ten sorting algorithms into two categories according to their respective implementation principles and efficiency:
- Nonlinear comparison sorting: nonlinear means that the time complexity of the algorithm cannot be broken (nlogn), and the order of the elements is determined by comparing the size.
- Linear noncomparison sorting: the algorithm can break through (nlogn) in time and sort elements without comparison.
The specific classification is shown in the figure above:
Algorithm to compare
The time complexity, space complexity and stability of the algorithm are compared and sorted out here, also in the form of pictures:
The relevant indicators are explained here
Time complexity: Time complexity is intended to estimate the execution time of the method, but in fact, the execution speed of a program on the computer is very fast, and the time is almost negligible, which is meaningless. Therefore, it means the execution times of the most frequently executed code in the algorithm. When n changes, what kind of rule does the number of executions change? Spatial complexity: the measure of the storage space required for the algorithm to execute in the computer, which is also a function of the data size n. Stability: in sorting for two equal elements a,b. If a is in front of B before sorting, a is always in front of B after sorting. Their position does not change because of the order called stability. On the other hand, if the position of a and B may change after sorting, then it is called unstable.
The following is a pair of ten algorithms for a detailed explanation, will give their basic ideas, picture demonstration, and with detailed annotated source code. (All sorting algorithms in this article are in ascending order)
1. Bubble sort
1.1 Basic Ideas
Bubble sort is one of the simplest sorts, and it’s the sort that most people think of most easily. I’m going to sort n numbers, and each time I’m going to compare the first number to the last number, and every round, I’m going to move the largest number to the end of the array, and I’m going to sort the array for n minus 1 rounds.
1.2 Picture Demonstration
1.3 Code Display
public static void bubbleSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
// I controls the number of loops. An array of length len only needs to loop len-1. I starts at 0 so I
for(int i=0; i<len-1; i++) {// loop I = loop I = loop I = loop I
Arr [j+1] [j+1] [j+1] [j+1] [j+1] [j+1] [j+1
for(int j=0; j<len-i-1; j++) {// If the preceding number is larger than the latter, switch places to put the larger number back.
if(arr[j]>arr[j+1]) {
int temp=arr[j+1];
arr[j+1]=arr[j]; arr[j]=temp; }}}}Copy the code2. Select sort
2.1 Basic Ideas
Selection sort bubble sort is modified, is no longer a number before and after compared a number, but in every cycle consists of a number to compare with all the number of time, every time is selected by the number of the relatively small compared the next, and constantly update the index to a decimal So at the end of a cycle can get the number of minimum subscript, You do one more swap to put the smallest number first, and then you go through n minus one loop and you sort it. Compared to bubble sort, the number of comparisons is the same, but the number of data exchanges is greatly reduced.
2.2 Picture Presentation
2.3 Code Display
public static void selectSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
// I controls the number of loops. An array of length len only needs to loop len-1. I starts at 0 so I
for(int i=0; i<len-1; i++) {//minIndex is used to store the lower index of each comparison.
int minIndex=i;
//j controls the number of comparisons, because at the end of each loop the smallest number has been placed first.
// So we can skip this number the next time we loop, so j starts at I +1 instead of starting at 0 every time, and j
for(int j=i+1; j<len; j++) {// For each comparison, record the lower index of the smaller number
if(arr[minIndex]>arr[j]) { minIndex=j; }}// When a loop is complete, you need to move the minimum number selected for the loop to the position at the beginning of the loop.
if(minIndex! =i) {int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
// Print the sorted state of the array at the end of each loop.
System.out.println("The first"+(i+1) +"Effect after this loop:"+Arrays.toString(arr)); }}Copy the code3. Insertion sort
3.1 Basic Ideas
The idea of insertion sort is certainly easy to understand for those of you who play cards, it’s just to fit in. First of all, the first number in the default array is in the correct position, that is, sorted. Then take the next number and compare it with the sorted number from back to front. If the number is smaller than the sorted number in the current position, the sorted number is moved one bit back. Repeat the previous step until you find the right position. When the position is found, the comparison cycle ends and the number is placed in the appropriate position.
3.2 Picture Demonstration
3.3 Code Display
public static void insertSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
// I controls the number of times to loop, because the first number is already in the correct position by default, so I starts at 1, I
for(int i=1; i<len; i++) {int j=i;// The variable j is used to record the position of the number to be sorted, i.e. the original position of the target number
int target=arr[j];// Target is used to record the value of the number to be sorted
// The while loop is used to find the appropriate position in the sorted number for the target value,
J >0; // J >0; // J >0
while(j>0 && target<arr[j-1]) {
// When the value of the target number is less than the value of the previous number in its current position, move the position of the previous number back one bit.
// and j-- makes the target number continue to be compared with the next element
arr[j]=arr[j-1];
j--;
}
// Change the target number.
arr[j]=target;
// Print the sorted state of the array at the end of each loop.
System.out.println("The first"+(i)+"Effect after this loop:"+Arrays.toString(arr)); }}Copy the code1. 4. Smart Car
4.1 Basic Ideas
Hill sort, also known as “shrink increment sort”, divides the array into subsequences, each of which has a small number of elements, and inserts each pair of subsequences separately. Once the array is basically sorted and then you do a direct insertion sort, you sort the entire array. Therefore, the strategy of jump segmentation should be adopted. The concept of “increments” is introduced here, and the records separated by a certain increment are combined into a subsequence in pairs, and then each subsequence is directly inserted to sort, so that the results are basically ordered (that is, the small ones are in the front, the large ones are in the back, and the small ones are in the middle). Hill sort is an updated version of direct insertion sort.
4.2 Picture Demonstration
4.3 Code Display
public static void shellSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;// The length of the array
int k=len/2;// The initial increment is half the length of the array
// The while loop controls the sequence of different molecules in increments, cutting them in half at each increment
// The minimum increment is 1, that is, the last direct insertion sort of the entire array
while(k>0) {
// Insert sort = insert sort = insert sort = insert sort
// So change the '1' to 'k' in the direct insertion sort.
for(inti=k; i<len; i++) {int j=i;
int target=arr[i];
while(j>=k && target<arr[j-k]) {
arr[j]=arr[j-k];
j-=k;
}
arr[j]=target;
}
// The result of sorting by different increments
System.out.println("Increment is"+k+"After sorting:"+Arrays.toString(arr));
k/=2; }}Copy the codeMerge sort
5.1 Basic Ideas
The general idea is to split it recursively from top to bottom, and then merge it gradually from bottom to top.
Recursive splitting: Divide the array into two subsequences, which are divided into four subsequences, and so on until the smallest subsequence has two or one elements.
Gradually merged, it is important to note that merge from bottom to top level can be understood as a recursive hierarchy return) : will the most on the left side of the bottom a subsequence of sorting, then will be ordered by the second is the sequence from left to right, then the two sorted the subsequence of merger and sorted, then the bottom third from left to right subsequence of sorts… After the merge is complete, memory is finished sorting the array
5.2 Picture Demonstration
5.3 Code Display
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {3.8.6.2.1.8};
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
/** * recursive split *@paramArr Array to be split *@paramLeft Minimum subscript * of the array to be split@paramRight Maximum index of the array to be split */
public static void mergeSort(int[] arr,int left,int right) {
int mid=(left+right)/2; // Middle subscript
if(left<right) {
mergeSort(arr,left,mid);// Split the left side recursively
mergeSort(arr,mid+1,right);// Split the right hand side recursively
sort(arr,left,mid,right);// Merge around}}/** * Merge two ordered subsequences *@paramArr Array to be merged *@paramLeft The smallest subscript * of the array to be merged@paramMid Middle index * of the array to be merged@paramRight Maximum index of the array to be merged */
public static void sort(int[] arr,int left,int mid,int right) {
int[] temp=new int[right-left+1]; // A temporary array to hold the results of each merge year
int i=left;
int j=mid+1;
int k=0;// The initial subscript of the temporary array
// The while loop can initially filter out the smaller numbers of the two subsequences to be merged
while(i<=mid && j<=right) {
if(arr[i]<=arr[j]) {
temp[k++]=arr[i++];
}else{ temp[k++]=arr[j++]; }}// Put the remaining numbers from the left-hand sequence into a temporary array
while(i<=mid) {
temp[k++]=arr[i++];
}
// Put the remaining numbers from the right sequence into a temporary array
while(j<=right) {
temp[k++]=arr[j++];
}
// Map the positions of elements in the temporary array to the actual array
for(int m=0; m<temp.length; m++) { arr[m+left]=temp[m]; }}Copy the codeQuick sort
6.1 Basic Ideas
Quicksort also uses a divide and conquer strategy, introducing the concept of ‘base numbers’.
- Find a base number (usually the first number of the array to be sorted as the base number)
- Partition the array so that everything less than or equal to the base number is placed on the left and everything greater than the base number is placed on the right.
- Repeat step 1 and Step 2 to partition the left and right subpartitions until each partition has only one number.
6.2 Picture Demonstration
6.3 Code Display
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72.6.57.88.60.42.83.73.48.85};
quickSort(arr,0.9);
System.out.println(Arrays.toString(arr));
}
/** * partition process *@paramArr Array to be partitioned *@paramLeft Minimum subscript * of the array to be partitioned@paramRight Maximum index of the array to be partitioned */
public static void quickSort(int[] arr,int left,int right) {
if(left<right) {
int temp=qSort(arr,left,right);
quickSort(arr,left,temp-1);
quickSort(arr,temp+1,right); }}/** * sorting process *@paramArr Array to be sorted *@paramLeft minimum subscript * of the array to be sorted@paramMaximum index * of the array to be sorted@returnAfter the sorted base number of position subscript, convenient next partition */
public static int qSort(int[] arr,int left,int right) {
int temp=arr[left];// Define the base number, which defaults to the first element in the array
while(left<right) {// Conditions for loop execution
// Since the default base number is on the left, we first compare the conditions entered into the while loop from the right
// If the current arr[right] is larger than the base number, move the right pointer one bit to the left, but make sure left
while(left<right && arr[right]>temp) {
right--;
}
// if the current arr[right] is smaller than the base number, move the current number to the base number and move the left pointer one bit to the right (left++).
// The current number (arr[right]) is empty, and you need to fill it with a number larger than the base number from the left.
if(left<right) {
arr[left++]=arr[right];
}
// The next step is to find a number larger than the base number on the left and fill in the right position.
If arr[left] is less than or equal to the base number, move the left pointer to the right
while(left<right && arr[left]<=temp) {
left++;
}
// Jump out of the previous loop to show that the current value of arr[left] is greater than the base number, which needs to be filled into the right space, and then the current space is empty.
if(left<right) { arr[right--]=arr[left]; }}// The end of the loop indicates that the left and right Pointers have met. And the meeting place is an empty place,
// In this case, fill the base number in the position and return the subscript of the position to prepare the partition.
arr[left]=temp;
return left;
}
Copy the code7. The heap sort
7.1 Basic Ideas
Before that, let’s talk about the concept of a heap. A heap is a special kind of complete binary tree, which is divided into large top heap and small top heap.
Large top heap: the value of each node is greater than the value of its left and right children. The large top heap is used for ascending sorting.
Small top heap: the value of each node is less than the value of its left and right children. Descending sorting uses the small top heap.
Therefore, the number to be sorted needs to be first constructed into a large top heap format. At this time, the top node of the heap is the largest number, and the elements of the last node of the heap are exchanged. The rest of the tree is restacked, and the first and last nodes are switched again, and the process is repeated until only the last node is sorted.
7.2 Picture Demonstration
7.3 Code Display
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72.6.57.88.60.42.83.73.48.85};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
if(arr==null) {
return;
}
int len=arr.length;
// Initialize the large top heap (from left to right and bottom to top, starting with the last non-leaf node)
for(int i=len/2-1; i>=0; i--) { adjustHeap(arr,i,len); }// Swap the top node with the last node and adjust the rest of the heap
for(int j=len-1; j>0; j--) { swap(arr,0,j);
adjustHeap(arr,0,j); }}/** * Arrange the tree into a heap *@paramArr Specifies the array to be sorted@paramNode at the beginning of I@paramJ The length of the array */
public static void adjustHeap(int[] arr,int i,int j) {
int temp=arr[i];// Define a variable to hold the starting node
//k is the left subscript of this node
for(int k=2*i+1; k<j; k=2*k+1) {
// Compare the sizes of the left and right child nodes. K always records the subscript of the larger of the two
if(k+1<j && arr[k]<arr[k+1]) {
k++;
}
// Compare the larger value in the child node with the current node, and place the larger value in the current node
if(arr[k]>temp) {
arr[i]=arr[k];
i=k;
}else{// Indicates that the heap is already large
break;
}
}
arr[i]=temp;
}
/** * Exchange data *@param arr
* @param num1
* @param num2
*/
public static void swap(int[] arr, int num1,int num2) {
int temp=arr[num1];
arr[num1]=arr[num2];
arr[num2]=temp;
}
Copy the code8. Counting sort
8.1 Basic Ideas
Counting sort takes a whole new approach. Instead of sorting by comparison, it takes the maximum value of the array to be sorted +1 as the length of a temporary array, and then uses the temporary array to record the number of occurrences of each element in the array to be sorted. Finally, we iterate through the temporary array. Because it is in ascending order, we iterate from front to back. We loop out the subscripts of the numbers >0 in the temporary array and put them into the array to be sorted. Counting sort is very efficient, but at the cost of memory, and has the limitation that the array values to be sorted must be limited to a certain range.
8.2 Picture Demonstration
8.3 Code Display
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72.6.57.88.60.42.83.73.48.85};
countSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void countSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
// Save the maximum value of the array to be sorted. The purpose is to determine the length of the temporary array (must).
int maxNum=arr[0];
// Stores the minimum value in the array to be sorted. The purpose is to determine the initial value of the pointer in the final traverse of the temporary array (not required, but this will speed up and reduce the number of loops)
int minNum=arr[0];
// The for loop is to find the maximum and minimum values of the array to be sorted
for(int i=1; i<len; i++) { maxNum=maxNum>arr[i]? maxNum:arr[i]; minNum=minNum<arr[i]? minNum:arr[i]; }// Create a temporary array
int[] temp=new int[maxNum+1];
// The for loop records the number of occurrences of each element in the array to be sorted and saves that number in a temporary array
for(int i=0; i<len; i++) { temp[arr[i]]++; }K =0 is used to record the index of the array to be sorted
int k=0;
// Iterates through the temporary array and reassigns the array to be sorted.
for(inti=minNum; i<temp.length; i++) {while(temp[i]>0) { arr[k++]=i; temp[i]--; }}}Copy the code9. Bucket sorting
9.1 Basic Ideas
Bucket sort is actually count sorting improved version, need to use A mapping function first define A limited number of buckets, and then will be ordered to stay in the array elements according to the function mapping relationship in different barrel inside, now different barrels of the data has been done inside the distinction, such as A bucket number either all greater than B barrels, either all less than the number of B A bucket. But the numbers in buckets A and B are still out of order. So use other sort methods (fast, insert, merge) to sort the data in each bucket with more than one element. Finally, put the elements in the bucket into the array in order to be sorted.
9.2 Picture Demonstration
9.3 Code Display
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {72.6.57.88.60.42.83.73.48.85};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
// Define the number of buckets, where the value of k depends on the situation, and we assume that the number in the array is between 0 and 100.
int k=10;
// Use nested sets to simulate buckets. The outer set represents the bucket and the inner set represents the elements inside the bucket.
List<List<Integer>> bucket=new ArrayList<>();
// The for loop initializes the outer set, that is, the bucket
for(int i=0; i<k; i++){ bucket.add(new ArrayList<>());
}
// The loop is used to map the elements of the array into buckets
for(int i=0; i<len; i++) { bucket.get(mapping(arr[i])).add(arr[i]); }// This loop is used to sort all buckets with more than one element.
for(int i=0; i<k; i++) {if(bucket.size()>1) {
// Since this is a bucket that is simulated by a collection, use the Java method to sort the collection.
// You should write your own method to sort.Collections.sort(bucket.get(i)); }}// Put the sorted numbers back into the array to be sorted
int m=0;
for(List<Integer> list:bucket) {
if(list.size()>0) {
for(Integer a:list) { arr[m++]=a; }}}}/** mapping function *@param num
* @return* /
public static int mapping(int num) {
return num/10;
}
Copy the code10. Radix sort
10.1 Basic Ideas
The data to be sorted is divided into multiple keywords for sorting, that is to say, the essence of radix sort is multi-keyword sort. The idea of multi-keyword sorting is to split the reed sorting keywords of the data to be sorted into multiple sorting keywords. The first sort keyword, the second sort keyword, the third sort keyword…… The sort data is then sorted according to the subkeyword treatment.
10.2 Picture Presentation
10.3 Code Display
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {720.6.57.88.60.42.83.73.48.85};
redixSort(arr,10.3);
System.out.println(Arrays.toString(arr));
}
public static void redixSort(int[] arr, int radix, int d) {
// Cache the array
int[] tmp = new int[arr.length];
// Buckets are used to record information about the elements to be sorted
// The buckets array defines max-min buckets
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// Reset the count array to start counting the next keyword
Arrays.fill(buckets, 0);
// Copy all the elements from data into the TMP array
System.arraycopy(arr, 0, tmp, 0, arr.length);
// Calculate the subkeywords of each data to be sorted
for (int j = 0; j < arr.length; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
// Sort the specified data by subkeywords
for (int m = arr.length - 1; m >= 0; m--) {
intsubKey = (tmp[m] / rate) % radix; arr[--buckets[subKey]] = tmp[m]; } rate *= radix; }}Copy the codeThe resources
- www.cnblogs.com/onepixel/ar…
- Blog.csdn.net/apei830/art…