Interviewer: Xiao Ming, right? What sort algorithms do you know, which ones are stable sort? Xiaoming: I have a summary of this!

The definition of sort stability

In layman’s terms, it guarantees that the first two numbers that are equal will be in the same order before and after the order as they are after the order. So just to simplify this, if Ai is equal to Aj, if Ai was in front of position, it still has to be in front of position Aj.

How does stable sorting behave in real life?

For example: some school hair scholarship, only row in the first three have a prize, the results of a sort of the original in the third joint third to get to the fourth, he estimates not happy 😂

Next, we use Java code to deduce the common sorts, the premise: there is an array ARR, the request from the smallest to the largest sort.

Selection sort

The idea of simple selection sort is to start at the first position and work backwards, selecting the smallest value in the subsequent unordered sequence and placing it at that position. Very simple, directly on the code:

// Select sortfor(int i = 0; i < arr.length - 1; I ++) {// do the ith sort int k = I;for(int j = k + 1; j < arr.length; J++){// select the smallest recordif(arr[j] < arr[k]){ k = j; }} // After the inner loop is complete, that is, the smallest number of the loop is found, then the swap is performedif(i ! Int temp = arr[I]; int temp = arr[I]; arr[i] = arr[k]; arr[k] = temp; }}Copy the code

Is selection sort stable sort?

For example, if there is a sequence [5,8,5,2,9] sorted in ascending order, the first element “5” will be exchanged with the fourth element “2” in the first order, then the relative order of the two “5” in the original sequence will be destroyed, so it can be seen that selective sorting is not a stable sorting algorithm.

Bubble sort

Bubble sort is a comparison and swap between two adjacent elements as required, with the following code:

// Bubble sortfor(int i = 0; i < arr.length - 1; I++) {// outer loop n-1for(int j = 0; j < arr.length - i - 1; J++) {// inner loop n-i-1if(arr[j] > arr[j + 1]) {// TMP = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; }}}Copy the code

Is bubble sort stable sort?

It happens between adjacent elements, so if two elements are equal, we don’t swap them; If two equal elements are not adjacent, then even if the two elements are adjacent by the previous pairwise swap, they will not swap, so the order of the same elements does not change, so bubble sort is a stable sorting algorithm.

Insertion sort

Insertion sort is very similar to arranging the cards in your hand in poker. Touch to the first card without finishing, then every time from the table card (disorderly area) touch the top 1 and insert the left hand card (orderly area) in the correct position. To find the correct position, compare the cards you touch from left to right (or from right to left) with the cards already in your left hand, as follows:

// Insert sortfor(int index = 1; index < length; Int temp = arr[index]; int temp = arr[index]; Int leftindex = index-1;whileArr [leftIndex + 1] = arr[leftIndex]; leftindex--; } arr[leftindex + 1] = temp; // put temp on the void}Copy the code

At first, there will be an ordered sequence of only one element on the left. The comparison starts from the end of the ordered sequence, that is, the element to be inserted is compared with the largest one that has been ordered. If it is larger than it, it will be inserted directly behind it, otherwise, it will continue to find until it finds the position of insertion.

Is insertion sort stable sort?

If an equal element is encountered, the inserted element places the desired element after the equal element. Therefore, the order of equal elements does not change, and the order that comes out of the original unordered sequence is the order that comes out of the sorted sequence, so insertion sort is stable.

Quick sort

A [I] <= a[center_index], where center_index is the array index of the central element, usually the 0th element in the array. The j subscript on the right goes all the way to the left as a[j] > a[center_index]. If neither I nor j can go further, I <= j, swap a[I] and a[j], and repeat the process until I > j. Swap a[j] and a[center_index] to complete a quicksort. When the central element and a[j] exchange, it is possible to disrupt the stability of the previous element, the code is as follows:

Public static void sort(int[] a, int low, int height) {int I = low; int j = height;if(I > j) {// put the index before k to prevent the subscript from crossing the boundaryreturn;
        }
        int k = a[i];
        while (i < j) {   
            while(I < j &&a [j] > k) {// Find the small number j--; }while(I < j&&a [I] <= k) {// Find the large number I ++; }if(I < j) {// swap int swap = a[I]; a[i] = a[j]; a[j] = swap; }} // switch K K = a[I]; a[i] = a[low]; a[low] = k; Sort (a, low, i-1); Sort (a, I + 1, height); }Copy the code

Is quicksort stable sort?

For example, if the sequence is 5, 3, 3, 4, 3, 8, 9, 10, 11, now the exchange of central element 5 and 3 (the fifth element, subscript starting from 1) will disrupt the stability of element 3, so quicksort is an unstable sorting algorithm, the instability occurs when the central element and a[j] exchange.

Merge sort

Merge sort is to recursively divide the sequence into short sequences. The recursive exit is that the short sequence has only 1 element (considered to be directly ordered) or 2 sequences (one comparison and exchange), and then merge the sequence of each ordered segment into a long ordered sequence, and continue to merge until the original sequence is all sorted, the code is as follows:

/ / merge sort public class Main {public static void Main (String [] args) {int [] arr = {11,44,23,67,88,65,34,48,9,12}; int[] tmp = new int[arr.length]; // Create a temporary array to store mergeSort(arr,0, arr.leng-1, TMP);for(int i=0; i<arr.length; i++){ System.out.print(arr[i]+""); } } public static void merge(int[] arr,int low,int mid,int high,int[] tmp){ int i = 0; int j = low,k = mid+1; // Start index of left and right sequenceswhile(j <= mid && k <= high){
			if(arr[j] < arr[k]){
				tmp[i++] = arr[j++];
			}else{ tmp[i++] = arr[k++]; }} // If the left sequence is left, copy it all into TMP []while(j <= mid){    
			tmp[i++] = arr[j++];
		}
		
		while(k <= high){
			tmp[i++] = arr[k++];
		}
		
		for(int t=0; t<i; t++){ arr[low+t] = tmp[t]; } } public static void mergeSort(int[] arr,int low,int high,int[] tmp){if(low<high){ int mid = (low+high)/2; mergeSort(arr,low,mid,tmp); // mergeSort(arr,mid+1,high, TMP); // Merge (arr,low,mid,high, TMP); // Merge two ordered sequences}}}Copy the code

Is merge sort a stable sort?

You can see that with 1 or 2 elements, 1 element will not be swapped, and if 2 elements are equal in size, no one will swap them on purpose, and this will not break the stability. So, in the process of merging short ordered sequences, is stability destroyed? No, during the merge process we can ensure that if two current elements are equal, we store the elements in the preceding sequence in front of the resulting sequence, thus guaranteeing stability. So merge sort is also a stable sort algorithm.

Radix sort (also called bucket method)

Radix sort is sorted by low order and then collected; And then sort it in order, and then collect it; And so on, all the way to the highest place.

The code is as follows:

Public static void myRadixSort(int[] arr) {int Max = 0; // Find the largest numberfor (int i = 0; i < arr.length; i++) {
        if(arr[i] > max) { max = arr[i]; }} // Get the largest number of bits inttimes = 0;
    while (max > 0) {
        max = max / 10;
        times+ +; } // Create a two-dimensional list list <ArrayList> list = new ArrayList<>(); // Create 10 lists (each bit has 10 digits from 0 to 9). Each list array is used to store the numbers that need to be loaded in each array from 0 to 9 in each iteration.for(int i = 0; i < 10; i++) { ArrayList list1 = new ArrayList(); List.add (list1); list.add(list1); list.add(list1); list.add(list1); } / /timesSub-distribution and collectionfor (int i = 0; i < times; I++) {// assignfor(int j = 0; j < arr.length; j++) { int x = arr[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i); List.get (x).add(arr[j]); list.get(x).add(arr[j]); } / / collect -- -- -- -- -- -- -- -- -- -- -- - > the 0-9, a total of 10 inside the list of values to an array in the int count = 0;for (int j = 0; j < 10; j++) {
            while(list.get(j).size() > 0) {// Return the JTH line of the two-dimensional list and assign it to list2 ArrayList<Integer> list2 = list.get(j); Arr [count] arr[count] = list2.get(0); List2.remove (0); list2.remove(0); list2.remove(0); count++; }}}}Copy the code

Is cardinal sort stable sort?

As can be seen from above, radix sort is based on sorting separately and collecting separately, so it is a stable sorting algorithm.

Hill sorting

Hill sort is the insertion sort of elements according to the asynchronous length. When the elements are disorderly at the beginning, the step size is the largest, so the number of elements in insertion sort is very small, and the speed is very fast. When the elements are basically ordered, the steps are small, insertion sort is very efficient for ordered sequences, so hill sort takes a little bit more time than O(n^2). The code is as follows:

Int incrementNum = arr. Length / 2;while (incrementNum >= 1) {
    for(int i = 0; i < arr.length; I++) {// perform insertion sortfor (int j = i; j < arr.length - incrementNum; j = j + incrementNum) {
            if(arr[j] > arr[j + incrementNum]) { int temple = arr[j]; arr[j] = arr[j + incrementNum]; arr[j + incrementNum] = temple; IncrementNum = incrementNum / 2; }Copy the code

Is cardinal sort stable sort?

Because of multiple insertion sorts, we know that a single insertion sort is stable and does not change the relative order of the same elements, but during different insertion sorts, the same elements may move in their respective insertion sorts and eventually their stability will be disturbed, so shell sorts are unstable.

Heap sort

The basic idea of heap sort is to construct the sequence to be sorted as a big top heap, in which the maximum value of the whole sequence is the root node of the top of the heap. Swap it with the trailing element, where the trailing element is the maximum. The remaining n-1 elements are then reconstructed into a heap, which yields the subsmallest values of n elements. The result is an ordered sequence, as shown in the following example:

Public static void sort(int[] arr) {//1. Build the big top heapfor(int i = arr.length / 2 - 1; i >= 0; AdjustHeap (arr, I, arr.length); } //2. Adjust heap structure + swap top and end heap elementsfor(int j = arr.length - 1; j > 0; j--) { swap(arr, 0, j); AdjustHeap (arr, 0, j); // Resize the heap}} /** * Resize the big top heap (only the resize process, * * @param arr * @param I * @param length */ public static void adjustHeap(int[] arr, int I, int length) { int temp = arr[i]; // Get the current element Ifor(int k = i * 2 + 1; k < length; K = k * 2 +1) {// Start at the left child of I, which is 2i+1if(k + 1 < length &&arr [k] < arr[k + 1]) {// If the left child is smaller than the right child, k points to the right child k++; }if(arr[k] > temp) {// If the child is larger than the parent, assign the value of the child to the parent (without swapping) arr[I] = arr[k]; i = k; }else {
            break; } } arr[i] = temp; } /** * swap element ** @param arr * @param a * @param b */ public void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }Copy the code

Is that a stable sort?

We know that the structure of the heap is that the children of node I are 2 * I and 2 * I + 1 nodes. The large top heap requires that the parent node be greater than or equal to 2 of its children, and the small top heap requires that the parent node be less than or equal to 2 of its children. In a sequence of length n, the process of heap sorting starts from the n / 2 value and its children choose the largest (big top heap) or the smallest (small top heap). The choice between these three elements will not destroy the stability of course. But when n / 2-1, n / 2-2… 1 When these parent nodes select elements, they break stability. It is possible that the NTH / 2nd parent swaps the last element, and the NTH / 2-1 parent swaps the last identical element, so the stability between the two identical elements is broken. So heap sort is not a stable sort algorithm.

conclusion

• Unstable sort: selection sort, quicksort, Hill sort, heap sort
• Stable sort: bubble sort, insertion sort, merge sort, radix sort

Welcome to follow the wechat official account for more resources