当前位置:网站首页>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 .
边栏推荐
- SAP UI5 应用的主-从-从(Master-Detail-Detail)布局模式的实现步骤
- pycharm专业版下载安装教程
- 《论文笔记》Multi-UAV Collaborative Monocular SLAM
- 潘多拉 IOT 开发板学习(RT-Thread)—— 实验4 蜂鸣器+马达实验【按键外部中断】(学习笔记)
- Leetcode70 (Advanced), 322
- 【微处理器】基于FPGA的微处理器VHDL开发
- Fs8b711s14 electric wine bottle opener MCU IC scheme development special integrated IC
- Learn C language from scratch day 024
- 【FPGA教程案例9】基于vivado核的时钟管理器设计与实现
- Open3d uses GICP to register point clouds
猜你喜欢
dotnet-exec 0.6.0 released
dotnet-exec 0.6.0 released
Complete knapsack problem (template)
抓包整理外篇——————状态栏[ 四]
Applet live + e-commerce, if you want to be a new retail e-commerce, use it!
创新引领方向 华为智慧生活全场景新品齐发
[selenium automation] common notes
uniapp微信小程序拿来即用的瀑布流布局demo2(方法二)(复制粘贴即可使用,无需做其他处理)
lambda expressions
Les phénomènes de « salaire inversé » et de « remplacement des diplômés » indiquent que l'industrie des tests a...
随机推荐
2022.07.03 (lc_6111_counts the number of ways to place houses)
Parsing of XML
基本放大电路的学习
dotnet-exec 0.6.0 released
【selenium自动化】常用注解
Query for Boolean field as "not true" (e.g. either false or non-existent)
NPM install error forced installation
Applet live + e-commerce, if you want to be a new retail e-commerce, use it!
RB technology stack
Daily practice (18): stack containing min function
Leetcode70 (Advanced), 322
SAP UI5 应用的主-从-从(Master-Detail-Detail)布局模式的实现步骤
Fs8b711s14 electric wine bottle opener MCU IC scheme development special integrated IC
ORB(Oriented FAST and Rotated BRIEF)
lambda表达式
Detailed explanation of openharmony resource management
"Upside down salary", "equal replacement of graduates" these phenomena show that the testing industry has
【FPGA教程案例9】基于vivado核的时钟管理器设计与实现
abc 258 G - Triangle(bitset)
[selenium automation] common notes