Interviewer: You have been paid for three years, choose the sort will not, why should I recruit you?
May 30, 2021 Article blog
During interviews, algorithms are often encountered, especially those that are common.
Chen Shifu graduated 3 years, has been doing java development in a start-up company, recently to a well-known Internet company interview, did a written test question, the interviewer looked at feel good, so want to further examine Zhanggong's coding ability, let him write the selection sorting algorithm, Chen Shifu busy half a day handed in a white paper, the interviewer said: you have graduated 3 years, even a selection of sorting method can not write out, I participate in the computer grade exam will be this. C hen Shifu a face of helplessness, but really should not, such as the selection of sorting such a basic algorithm, usually should master a good right.
The written test before the editor also encountered the situation of handwriting sorting algorithm, about the selection of sorting may be basically written out, but if you can optimize the program again, it would be better, I believe can leave a better impression on the interviewer. Let's first look at what selection sorting method:
Select sorting is an unstable sorting algorithm. I t works by selecting the smallest (or largest) element from the data element to be sorted each time, storing it at the beginning of the sequence, then continuing to look for the smallest (large) element from the remaining unsorted elements, and then placing it at the end of the sorted sequence. and so on until all the data elements to be sorted are queued.
stability
Select sorting is to select the smallest current element for each location, such as the smallest for the first position, the second smallest for the second element in the remaining element, and so on, until the n-1 element, the nth element does not have to be selected, because only it has one of the largest elements. S o, in a selection, if an element is smaller than the current element and that small element appears after an element equal to the current element, then the stability is compromised after the exchange.
For example, sequence 6 8 6 3 9, we know that the first time we select the first element 6 and 3 exchange, then the relative before and after order of the two 6s in the original sequence is destroyed, so the selection of sorting is an unstable sorting algorithm.
About time complexity
The swap operation for which the sort is selected is between 0 and (n - 1). T
he comparison operation for which the sort is selected is n (n - 1) / 2 times. T
he assignment to select the sort is between 0 and 3 (n - 1). N
umber of comparisons O (n^2), the number of comparisons is independent of the initial state of the keyword, the total number of comparisons N s (n-1) plus (n-2) s.1 s n s (n - 1)/2. T
he number of interchanges O(n), preferably 0 in order, n-1 in the worst case, n/2 in reverse order. T
he number of interchanges is much smaller than the bubbling sort, and because the swap takes more CPU time than the comparison requires, the n-value is smaller, and the selection sort is faster than the bubbling sort. T
he time complexity of the sort selected directly is O (n*n) and the spatial complexity is O(1). T
he time complexity of the tree selection sort is O (nlog2n) and the spatial complexity is O(n). T
he average time complexity of heap sorting is O (nlog2n), which is efficient, but the implementation is relatively complex and the spatial cost is O(1).
Let's look at the selection sorting algorithm code written in java
/**
* Select sort
*
* @param arr
*/
public static void selectionSort(int[] arr) {
int min;
int length = arr.length;
for ( int i = 0; i < length; i++) {
/ / Initialize the minimum data array subscript in unsorted sequences
min = i;
for ( int j = i + 1; j < length; j++) {
/ / Continue to find the minimum element in the unspiled element, and save it subscript
if (arr[j] < arr[min]) {
min = j;
}
}
// Put the minimum element in the unscorted sequence to the end of the ranked sequence
if (min != i) {
swap(min, i, arr);
}
}
}
/**
* Exchange order
*
* @param x
* @param y
* @param arr
*/
private static void swap(int x, int y, int[] arr) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
Call the instance
public static void main(String[] args) {
int arr[] = { 2, 17, 2, 11, 7, 6, 19, 9, 14, 20, 17, 13, 14, 2, 10};
System.out.println(String.format( "original array = %s\n", Arrays.toString(arr)));
selectionSort(arr);
System.out.println(String.format( "sorted array = %s\n", Arrays.toString(arr)));
}
The output
For the selection of sorting algorithm, if still not very good understanding, let's look at the animation, which will be easier to understand.
I wonder if you fully understand the selection sorting algorithm.
The selection of sorting method is basically quite good, when the data size is small, or recommended to use, but relative to other sorting algorithms (such as fast sorting) efficiency is obviously somewhat inadequate.
Small editor believes that the idea of choosing the sorting method is still very important, to pay attention to.
Recommended lessons: Java Basics Getting Started with Framework Practice, In-depth Analysis of Java Object Oriented