Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”
This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
Like it and see. Make it a habit. Wechat search [a coding] follow this programmer who is struggling in the Internet.
This article is collected on Github – Technical expert Training, which contains my learning route, series of articles, interview question bank, self-study materials, e-books, etc.
Hello, everyone, I am a ~
Today I’m going to show you the sorting algorithm. I believe that whether beginners learn or interviews, are not not sorting algorithm this, even if you did not learn the algorithm, the bubble sorting is not strange.
Today, one will take you over the “sorting algorithm” hurdle. ⭐ ️
This article supporting source address: “eight sort” source code, extraction code: 5EHP
To prepare
As the old saying goes, “When the troops and horses are not moved, food and grass go first.” If you want to follow the “sorting algorithm” one by one, it is recommended to prepare the following code template.
📢 To watch this tutorial, you need to know basic loop syntax, two-digit swapping, and double-pointers.
📚 recommend reading the code and step by step analysis before trying to write your own.
- Create a new
JavaProject, this article is also based on the Java language code. - Create the following directory structure
- in
MainTestWrite test templates in test classes.
/**
* 测试类
* Author：一条
* Date：2021/09/23
*/
public class MainTest {
public static void main(String[] args) {
// The sequence to be sorted
int[] array={6.10.4.5.2.8};
// Call different sorting algorithms
// BubbleSort.sort(array);
// Create an array with 100000 random data
int[] costArray=new int[100000];
for (int i = 0; i < 100000; i++) {
// generate a number [0,100000]
costArray[i] = (int) (Math.random() * 100000);
}
Date start = new Date();
// Too long, comment out first step print
//BubbleSort.sort(costArray);
Date end = new Date();
System.out.println("Time:"+(end.getTime()-start.getTime())/1000+"s"); }}Copy the codeThe content of this code has two main functions:
- Call different sorting algorithms to test
- Testing different sorting algorithms will
10wThe amount of time it takes to sort the numbers. More concrete understandingTime complexityThe different
Bubble sort
The basic idea
By traversing the out-of-order sequence from front to back, the values of adjacent elements are compared in turn. If the reverse order is found, the values of the elements with larger values are gradually moved from front to back.
Like bubbles rising from the bottom of the water.
Dynamic figure interpretation
! [] (yitiaoit.oss-cn-beijing.aliyuncs.com/img/2021-09… 18.17.49. GIF)
Code implementation
If you do not understand, you can use debug mode to analyze step by step.
/** ** bubble sort * Author: Date: 2021/09/23 */
public class BubbleSort{
public static int[] sort(int[] array){
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length-1; j++) {
// Swap the largest element to the end
if (array[j]>array[j+1]) {// Exchange two values with the temporary variable temp
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp; }}// Prints the sorting result for each step
System.out.println(Arrays.toString(array));
}
returnarray; }}Copy the codeThe output
Analysis step by step
- Initial array:
,10,4,5,2,8 [6] 6Take it out and the last one10The comparison,6 < 10No need to exchange. – >j++;10Take it out and the last one4The comparison,10 > 4And exchange. – >,4,10,5,2,8 [6]- Executed in sequence
j++With the latterMore exchange. - The first layer
iWhen the loop is complete, print the first line – >[6, 4, 5, 2, 8, 10]The last digit at this point10In the right place. – >i++ - from
4Go onMore exchangeSecond to last8Get back to the correct position. - Repeat as above – >…
- Final result – >
[2, 4, 5, 6, 8, 10]
Then go back to the GIF to understand.
Take the test
Remember to comment out the sorting class and print the code step by step.
Time complexity: O(n^2)
Algorithm to optimize
To optimize the point a
After the outer layer is traversed for the first time, the last digit is correct, so j does not need to be compared, so the ending condition should be changed to J-I-1. .
Optimization point 2
In the sorting process, each element keeps approaching its position. If there is no exchange after a comparison, it means that the sequence is orderly. Therefore, a flag should be set in the sorting process to determine whether elements have been exchanged. Thus reducing unnecessary comparisons.
Optimize the code
public static int[] sortPlus(int[] array){
System.out.println("Optimizing bubble Sorting begins ----------");
for (int i = 0; i < array.length; i++) {
boolean flag=false;
for (int j = 0; j < array.length-i-1; j++) {
if (array[j]>array[j+1]){
flag=true;
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp; }}if (flag==false) {break;
}
// System.out.println(Arrays.toString(array));
}
return array;
}
Copy the codeOptimization test
The basic tests see that the loop is terminated when the sequence is sorted, i.e., no swapping occurs.
Time test optimized from 27s to 17s.
Selection sort
The basic idea
Selection sort and bubble sort are very similar, is from the disorderly sequence of data, according to the specified rules to select a certain element, and then according to the specified position exchange to achieve the purpose of sorting.
Dynamic figure interpretation
! [] (yitiaoit.oss-cn-beijing.aliyuncs.com/img/2021-09… 18.52.31. GIF)
Code implementation
public class SelectSort {
public static int[] sort(int[] array) {
System.out.println("Select sort start ----------");
for (int i = 0; i < array.length; i++) {
// Each value is only compared to the value that follows it, so start
for (int j = i; j < array.length; j++) {
// Note which two values are being compared here
if (array[i]>array[j]){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
System.out.println(Arrays.toString(array));
}
returnarray; }}Copy the codeThe output
Analysis step by step
- Initial array:
,10,4,5,2,8 [6] - Come up with
6with10Compare, do not swap – >j++ 6with2Compare, exchange – >j++- Notice that this is taking
2Continue the comparison, do not swap, determine the first digit (the smallest number) is2– >i++ - The cycle continues until you find the first small, the second small… The number of
- Final result – >
[2, 4, 5, 6, 8, 10]
Then go back to the GIF to understand.
Take the test
Time complexity: O(n^2)
Algorithm to optimize
In the appeal code, you can find smaller values by swapping, or you can swap once after all the comparisons.
There is some gain in the occupancy of space, but the gain in time is negligible and will not be demonstrated.
Insertion sort
The basic idea
N out-of-order elements are regarded as an ordered list and an unordered list. At the beginning, the ordered list contains only one element, while the unordered list contains n-1 elements. During the sorting process, a local correct solution is obtained by constantly inserting elements into the ordered list, and the length of the ordered sequence is gradually expanded until the sorting is completed.
Dynamic figure interpretation
! 19.20.05 [2021-09-25] (yitiaoit.oss-cn-beijing.aliyuncs.com/img/2021-09… 19.20.05. GIF)
Code implementation
/**
* 插入排序
* Author：一条
* Date：2021/09/23
*/
public class InsertSort {
public static void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
// Inserts an ordered sequence and enlarges the ordered sequence
for (int j = i; j > 0; j--) {
if (array[j]>array[j-1]) {int temp=array[j];
array[j]=array[j-1];
array[j-1]=temp; }}// System.out.println(Arrays.toString(array));}}}Copy the codeThe output
Take the test
Algorithm to optimize
See Hill sort below for Hill’s optimization of insertion sort.
Hill sorting
Hill sort is an optimization of insertion sort. If you want to insert 1 into [2,3,4,5,6], you need to move the positions of all elements once. That is to say, in some extreme cases, the efficiency is not high, which is also called unstable algorithm.
Hill sort is a more efficient version of an improved insertion sort, also known as reduced increment sort.
The basic idea
Hill sort is to group the records in increments of subscripts, and insert sort is used for each group.
As the increments gradually decrease, each group contains more and more keywords. When the increments decrease to 1, the whole sequence is exactly divided into a group and the algorithm terminates.
Like insertion sort, hill sort goes from local to all, local to local.
Dynamic figure interpretation
Code implementation
/** ** file: * Date: 2021/09/23 */
public class ShellSort {
public static void sort(int[] array) {
System.out.println("Hill sort start --------");
//gap initial increment =length/2 gradually diminishes: gap/2
for (int gap = array.length/2; gap > 0 ; gap/=2) {
// Insert sort swap
for (int i = gap; i < array.length ; i++) {
int j = i;
while(j-gap>=0 && array[j]<array[j-gap]){
// Insert sort by swap
inttemp = array[j]; array[j]=array[j-gap]; array[j-gap]=temp; j-=gap; } } System.out.println(Arrays.toString(array)); }}}Copy the codeThe output
Take the test
Algorithm to optimize
There is no
Quick sort
Quicksort is an improvement over bubble sort, where each swap is a jump.
The basic idea
The data to be sorted is divided into two independent parts, and all the data in one part is smaller than all the data in the other part, and then the two parts of the data are sorted by this method. The whole sorting process can be carried out recursively, so as to achieve an ordered sequence of the whole data.
It embodies the idea of divide and conquer.
Dynamic figure interpretation
! [] (yitiaoit.oss-cn-beijing.aliyuncs.com/img/2021-09… 02.49.17. GIF)
Code implementation
Here’s the idea:
- I’m going to start by looking for a number in this sequence, and I’m going to pick the first number for convenience.
- Iterate over the number group, place the number less than the base number to the left, and the number greater than the base number to the right. This can be done with a double pointer.
- At this point, the base value splits the array in half, and the base value is considered returned.
- Recursive algorithm is used to sort the subarray after partition and conquer.
public class QuickSort {
public static void sort(int[] array) {
System.out.println("Quicksort start ---------");
mainSort(array, 0, array.length - 1);
}
private static void mainSort(int[] array, int left, int right) {
if(left > right) {
return;
}
/ / double pointer
int i=left;
int j=right;
// Base is the base number
int base = array[left];
// The left side is less than the baseline and the right side is greater than the baseline
while (i<j) {
// Look to the right first, descending to the left
while (base<=array[j]&&i<j) {
j--;
}
// Look at the left side, and increase in order to the right
while (base>=array[i]&&i<j) {
i++;
}
/ / exchange
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
// Finally the benchmark is the swap of numbers equal to I and j
array[left] = array[i];
array[i] = base;
System.out.println(Arrays.toString(array));
// Recursively call the left half array
mainSort(array, left, j-1);
// Recursively call the right half of the array
mainSort(array, j+1, right); }}Copy the codeThe output
Analysis step by step
- will
6As a base number, use the left and right Pointers to make the left numberThe < 6The number on the right> 6. - I recurse to the left and right, the left
5Continue the comparison as a base number. - until
left > rightEnd the recursion.
Take the test
Why is quicksort so fast?
Algorithm to optimize
Optimization of a
Median-of-three: at present, we take the first number as the benchmark number. For some ordered sequences, it will waste cycles. We can use the median-of-three method to optimize, and sensible friends can understand by themselves.
Optimization of two
Quicksort is very fast for long sequences, but not as fast as insertion sort for short sequences. Can be used in combination.
Heap sort
This chapter requires a high level of basic knowledge, beginners can skip.
The basic idea
Heap sort is the use of heap data structure and design of a sort algorithm, heap sort is a ** selection sort, ** its worst, best, average time complexity is O(nlogn), it is also unstable sort. First, a brief understanding of the structure of the lower heap.
The heap
A heap is a complete binary tree with the following properties:
- Each node has a value greater than or equal to the value of its left and right children, called the big top heap;
- The value of each node is less than or equal to the value of its left and right children, called the small top heap.
The main use of the maximum or minimum characteristics of heap top elements, through the continuous construction of the big top heap, exchange heap top and heap tail, tail-breaking reconstruction to achieve sorting.
Dynamic figure interpretation
Code implementation
public class HeapSort {
public static void sort(int[] array) {
/ / create a heap
for (int i = (array.length - 1) / 2; i >= 0; i--) {
// Adjust the structure from bottom to top and from right to left from the first non-leaf node
adjustHeap(array, i, array.length);
}
// Adjust the heap structure + swap the top element and the end element
for (int i = array.length - 1; i > 0; i--) {
// Swap the top element with the end element
int temp = array[i];
array[i] = array[0];
array[0] = temp;
// Resize the heap
adjustHeap(array, 0, i); }}/** * adjust the heap *@paramArray To be sorted *@paramParent Parent node *@paramLength Indicates the index of the last element in the sequence */
private static void adjustHeap(int[] array, int parent, int length) {
// Use temp as the parent node
int temp = array[parent];
/ / the left child
int lChild = 2 * parent + 1;
while (lChild < length) {
/ / right child
int rChild = lChild + 1;
If there is a right child and the value of the right child is greater than that of the left child, select the right child
if (rChild < length && array[lChild] < array[rChild]) {
lChild++;
}
// If the value of the parent node is already greater than the value of the child node, it ends
if (temp >= array[lChild]) {
break;
}
// Assign the value of the child to the parent
array[parent] = array[lChild];
// Select the left child of the child node and continue filtering down
parent = lChild;
lChild = 2 * lChild + 1; } array[parent] = temp; System.out.println(Arrays.toString(array)); }}Copy the codeThe output
Analysis step by step
- Build the initial heap, and arrange the queue to form a big top heap (or small top heap), ascending big top heap, descending small top heap;
- Swap the top of the heap with the bottom of the heap, and disconnect (remove from the queue) the bottom of the heap.
- Rebuild the heap.
- Repeat 2 to 3 until only one element (the heaptop element) remains in the queue.
Take the test
Algorithm to optimize
The key of optimization point lies in how we find the position of the top element. Interested students can continue to study.
Merge sort
The basic idea
Merge-sort is a sorting method implemented by merging and adopting the classic divide-and-conquer strategy.
Disordered sequence is continuously divided into half, sorted and then put back, with recursive implementation.
The challenge is how do you merge two sorted arrays?
We can create a temporary array and use fast and slow Pointers to aid our merge.
Although I need extra space to do this sort. But now that computers have a lot of memory, time efficiency is more important than space efficiency.
So space for time is also a direction of optimization.
Dynamic figure interpretation
! [] (yitiaoit.oss-cn-beijing.aliyuncs.com/img/2021-09… 15.20.57. GIF)
Code implementation
public class MergeSort {
public static void sort(int[] array){
divide(array,0,array.length-1);
}
private static int[] divide(int[] array, int left, int right) {
int mid = (left+right)/2;
if(left<right){
divide(array,left,mid);
divide(array,mid+1,right);
// merge left and right
merge(array,left,mid,right);
}
System.out.println(Arrays.toString(array));
return array;
}
public static void merge(int[] array, int left, int mid, int right) {
int[] temp = new int[right-left+1];
int i= left;
int j = mid+1;
int k=0;
// Move the smaller number into the new array first
while(i<=mid && j<=right){
if(array[i]<array[j]){
temp[k++] = array[i++];
}else{ temp[k++] = array[j++]; }}// Move the left number into the array
while(i<=mid){
temp[k++] = array[i++];
}
// Move the remaining number on the right side into the array
while(j<=right){
temp[k++] = array[j++];
}
// Overwrite the nums array
for(int x=0;x<temp.length;x++){
array[x+left] = temp[x];
}
}
}
Copy the codeThe output
Take the test
Algorithm to optimize
Count sorting
It’s all non-comparative sort from here on out.
The basic idea
If we input a number x, if we can find how many numbers are smaller than that number, we can simply place x in the corresponding output array. For example, if x=5 in the test sequence, and 2 of them are smaller than 5, then 5 is undoubtedly the third place.
Dynamic figure interpretation
! [] (yitiaoit.oss-cn-beijing.aliyuncs.com/img/2021-09… 16.05.17. GIF)
Code implementation
public class CountSort {
public static void sort(int[] array) {
System.out.println("Counting sort begins --------");
// Calculate the maximum and minimum values to determine the length of count[]
int max = array[0], min = array[0];
for (int i : array) {
if (i > max) {
max = i;
}
if(i < min) { min = i; }}//count[] is used to store the number of occurrences of each element
int[] count = new int[max - min + 1];
// Count the frequency of occurrences
for (int i : array) {
count[i - min] += 1;// the number of positions +1
}
// Create the final array, the same length as the original array, but the sorting is complete
int[] result = new int[array.length];
int index = 0;// Record the index of the final array
// Loop each element through the index of the counting collator
for (int i = 0; i < count.length; i++) {
// The number of times the loop occurs
for (int j = 0; j < count[i]; j++) {//count[I]: the frequency of this number
result[index++] = i + min;// The value of min is the same as the value of min} System.out.println(Arrays.toString(result)); }}}Copy the codeThe output
Analysis step by step
- The number of occurrences in the original array is recorded in the new array subscript.
- Iterate over the number of occurrences, then put the new array in turn.
Take the test
Honestly, I’m surprised at the speed. The time complexity of counting sort is O(n), but it has the disadvantage of limiting integers in the range [0,k].
Algorithm to optimize
While normal counting sort starts at 0, the code implemented in this article starts at min and is optimized.
conclusion
Time complexity is not covered in this article, because I put a number here and you can’t understand the difference.
Test eight sorting algorithms with an array of 100000 lengths to make abstraction concrete. The advantage of nlogn over n^2 is going to get bigger and bigger when there’s a lot of data, and when n is equal to 10^5, the nlogn algorithm is 6,000 times faster than the n^2 algorithm, so what’s the idea, that if we’re going to process a data set, and we’re going to process it in one day with the Nlogn algorithm, we’re going to process it in 6,020 days with the N ^2 algorithm. That’s about 15 years.
An optimized and improved algorithm may be much faster than a more stupid algorithm, which is why dachang examines the algorithm and why we learn the algorithm.
As the old saying goes: by the wisdom of all, there is no duty; With the strength of many, there is no victory. In order to overcome the mountain of algorithms, I made a team to brush problems, at least one Leetcode algorithm problem every day.
Inferior horse ten riding, gongnever give up.
If you are a freshman and keep studying every day, you will finish at least 1200 more questions than others, and you will probably earn 3-4 times as much when you graduate.
If you are a professional, you can improve yourself every day, get a promotion and raise, and become a technical expert.
As long as you are willing to struggle, always walk on the road of hard work, that your life, the worst result, but is a late bloomer.
Click here to join the program
If the link is blocked, or there is a permission problem, you can private chat author to solve.