当前位置：网站首页>I was beaten by the interviewer because I didn't understand the sorting
I was beaten by the interviewer because I didn't understand the sorting
2022-07-05 00:51:00 【Java geek Technology】
Today, ah fan will talk about this Java Various sorting algorithms in , Because I met an interview senior developer before , The result turned out to be a Nine Nine Multiplication Table problem , A fan heard what the reader said at that time , Instantly understand what it means , This feeling is a little deceptive , But it's actually the interviewer who wants to examine your sorting algorithm , It may also be really boring .
Sorting algorithm
What is a sorting algorithm , In fact, there is not much to say about this , Just express your meaning clearly , So called sorting , Is to make a string of records , According to the size of one or some of the keywords , An operation arranged incrementally or decrementally .
The types of sorting algorithms can be said to be relatively diversified , Right time , Efficiency of space , Different sorting algorithms have different advantages and disadvantages , Some use time for space , Some exchange space for time , Today, ah fan will list them one by one .
Bubble sort
What is bubble sorting ？
Bubble sorting is to compare two adjacent numbers in turn , Put the decimals first , Big numbers in the back .
Like a bubble , Like a bubble , Float straight up .
Bubble sorting is to compare two adjacent numbers in turn , Put the decimals first , Big numbers in the back .
In fact, the process of comparison is like this ：
The first comparison ：
First of all, compare No 1 And the first 2 Number , Put decimals first , Big numbers in the back , Then compare the 2 Number and number 3 Number , Put decimals in front , Big numbers in the back , Then compare until the end , such , The largest number is put on the last side .
The second comparison ：
First of all, compare No 1 And the first 2 Number , Put decimals first , Big numbers in the back , Then compare to the penultimate number , Then the second comparison ends , In this way, the one in the last position is the largest , Then the penultimate position is the second largest number .
Then go on like this , The third time is to take the third number , So it goes through the cycle , It must be understandable to say so , Suppose the number of sequences to be sorted is n, You need to go through n-1 round , Finish sorting . In the first round , The number of comparisons is n-1 Time , After each round, reduce 1 Time .
Let's use code to realize ：
public static void main(int[] a) {
int temp;
// Need to compare n-1 round
for (int i = 0; i < a.length-1; i++) {
// according to a.length-i-1, The number of comparisons per round is reduced round by round 1 Time
for (int j = 0; j < a.length-i-1 ; j++) {
// Compare adjacent numbers , Replace if qualified
if (a[j] > a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
Insertion sort
There are many kinds of insertion sorting
- Direct insert sort
- Bisection insertion sort
- Shell Sort
These sorting methods all belong to insert sorting ,
Let's first look at direct insertion sorting ：
The comparison process is like this , The second data of the array starts to compare forward , At the beginning, compare the second number with the one in front of him , If If they meet the conditions, let them exchange positions .
Suppose we give an array , We should sort from small to large , The array is [3,1,4,6,5,17,12,11] Now , The first step is to hold 1 and 3 Compare , If 1 Less than 3 , This is the time , Just put 1 and 3 Change the position ,[1,3,4,6,5,17,12,11] .
Next, compare the third number with the second , If it matches, it will be exchanged , But here we have to move on , Just use 4 and 3 and 1 Compare them separately , Then keep repeating like this . Until all the data are arranged , We get the result we want , Let's write a code to see what it looks like .
public static void basal(int[] array) {
// Start with the second
if (array == null || array.length < 2) {
return;
}
for (int i = 1; i < array.length; i++) {
int cur = array[i];
// cur Landing sign , Prevent the minimum number to be inserted
boolean flag = false;
// Reverse traversal , Constantly shifting
for (int j = i - 1; j > -1; j--) {
if (cur < array[j]) {
array[j + 1] = array[j];
}else {
array[j + 1] = cur;
flag = true;
break;
}
}
if (!flag) {
array[0] = cur;
}
}
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
Since we have said before , There are many ways to insert sorting , Then we have to talk about other insertion sorting , Then I'm looking at the differences between them , I don't know if they're right ？
Since we have just said sorting, we need to talk about array backward every time , But our previous judgment conditions can be optimized , In this way, other different insertion sorts are derived from the optimization , Next, let's take a look at the binary search insertion sort .
Binary search insert sort
The core of optimizing direct insertion sorting is ： Quickly locate the position where the current number is to be inserted . Find a given value in an ordered array , The fastest way is undoubtedly binary search , At least in a fan's heart, if you want to optimize, you must choose whether you can use the binary search method at the first time ？
Let's take a look at the code implementation , Then look at his shortcomings , Why do many people choose not to use binary search insert sorting .
// Use the binary search method provided by the system , Locate the insertion position
// Unstable sequencing
public static void optimized(int[] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 1; i < array.length; i++) { int cur = array[i];
int[] sorted = Arrays.copyOf(array, i);
int index = Arrays.binarySearch(sorted,cur); if (index < 0) {
index = -(index + 1);
}
for (int j = i - 1; j > index - 1; j--) {
array[j + 1] = array[j];
}
array[index] = cur;
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
In the Middle East: , A fan uses the system's own Arrays, Then the binary search insertion sort , Why use it like this ？ stay JDK Provided in Arrays.binarySearch(), Method requires an ordered array to be passed in To implement , Why not use this method ？
Suppose before sorting , Two numbers are equal , But after sorting , Both of them may change the order, which means that the sorting algorithm is unstable . This is what we call stability .
Since there is such an unstable sort , Should there be a stable sort ？ Yes, it is , There is , So what is a stable sort ？ Yes , Everyone is right , Bubble sort is stable sort , Because bubble sorting only changes the positions of adjacent elements when their sizes do not meet the requirements , It does not change the relative order between the same elements , So it's a stable sort algorithm .
Since we just said that there is also Hill sort in this interpolation sort , Let's take a look at Hill sort .
Shell Sort
Tell the truth , When ah fan first knew this sort , Just want to say , Is it someone named Hill who improved , result , It's a discovery , Shell Sort , Also known as （（ Reduced delta sort ）, because D.L.Shell On 1959 It was named after it was put forward in 1949 , Actually, it should be called Shell's Sort.
Hill sort is to divide the whole sequence of records to be sorted into several subsequences for direct insertion sort , To be recorded throughout the sequence “ The basic order ” when , All records are then directly inserted in sequence .
In fact, it is equivalent to a simple grouping first , The array to be sorted in steps gap Grouping , Then the elements of each group are sorted by direct insertion ; Every time gap Reduce by half , Cycle the above operations ; When gap=1 when , Using direct insertion , To complete the order .
The code implementation is like this
public static void sort(int[] a) {
int length = a.length;
int h = 1;
while (h < length / 3) h = 3 * h + 1;
for (; h >= 1; h /= 3) {
for (int i = 0; i < a.length - h; i += h) {
for (int j = i + h; j > 0; j -= h) {
if (a[j] < a[j - h]) {
int temp = a[j];
a[j] = a[j - h];
a[j - h] = temp;
}
}
}
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
Selection sort
Selection sort （Selection sort） It is a simple and intuitive sorting algorithm .
This is a little bit easier , Why do you say that? , It is because it directly finds the smallest or largest element in the unordered sequence , To the beginning of the collating sequence , then , Continue to find the smallest from the remaining unsorted elements （ Big ） Elements , And then at the end of the sorted sequence . And so on , Until all the elements are sorted .
In fact, it is similar to bubble sorting in idea , But it's just different .
Let's look at the code implementation ：
public static void sort(int[] a) {
for (int i = 0; i < a.length; i++) {
int min = i;
// Select the position with the lowest value to be sorted
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
// Exchange when the minimum value is not equal to the current value
if (min != i) {
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
Since ah fan has listed these sorts for you , So we come back to another question , Sort so much , How to choose , Why choose , This involves time complexity and space complexity , Or use space for time , Or use time for space .
summary
Bubble sort
Average time complexity | The best situation | The worst | Spatial complexity |
O(n²) | O(n) | O(n²) | O(1) |
Direct insert sort
Average time complexity | The best situation | The worst | Spatial complexity |
O(n²) | O(n²) | O(n²) | O(1) |
Binary search sort
Average time complexity | The best situation | The worst | Spatial complexity |
O(n²) | O(n²) | O(n²) | O(1) |
Shell Sort
Average time complexity | The best situation | The worst | Spatial complexity |
O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(1) |
Selection sort
Average time complexity | The best situation | The worst | Spatial complexity |
O(n²) | O(n²) | O(n²) | O(1) |
That's all for today's sorting , Have you learned ？
Out of order ！ Out of order ！
Java There are many excellent partners in Geek technology wechat group discussing Technology , Occasionally, there are irregular information sharing and red envelope distribution ！ If you want to improve yourself , And want to make progress with excellent people , Interested friends , You can reply in the background of the official account below ： Add group .
边栏推荐
- 2022.07.03(LC_6111_统计放置房子的方式数)
- 程序员SQL数据脚本编码能力弱，BI做不出来怎么办？
- 【海浪建模3】三维随机真实海浪建模以及海浪发电机建模matlab仿真
- 那些一门心思研究自动化测试的人，最后都怎样了？
- 华为200万年薪聘请数据治理专家！背后的千亿市场值得关注
- Arbitrum：二维费用
- Huawei employs millions of data governance experts! The 100 billion market behind it deserves attention
- Deux nombres se remplacent
- Parameter passing mechanism of member methods
- const、volatile和restrict的作用和用法总结
猜你喜欢
随机推荐
【海浪建模1】海浪建模的理论分析和matlab仿真
Learn C language from scratch day 024
程序员SQL数据脚本编码能力弱，BI做不出来怎么办？
Basic concept and usage of redis
leetcode494,474
Recursive execution mechanism
ORB(Oriented FAST and Rotated BRIEF)
Get to know ROS for the first time
两个数相互替换
npm install报错 强制安装
P4281 [AHOI2008]紧急集合 / 聚会(LCA)
【C】(笔试题)指针与数组，指针
Verilog tutorial (11) initial block in Verilog
潘多拉 IOT 开发板学习（RT-Thread）—— 实验4 蜂鸣器+马达实验【按键外部中断】（学习笔记）
Learning of basic amplification circuit
lambda表达式
MySQL uses the explain tool to view the execution plan
【海浪建模3】三维随机真实海浪建模以及海浪发电机建模matlab仿真
Hill sort of sorting
揭露测试外包公司，关于外包，你或许听到过这样的声音