Sorting algorithm a table overview

Other notes:

  • In counting sort, k, k, k is a range of integers
  • Stability refers to whether it is possible to swap the order of the same number in the sequence. For example, if there are two 8s in the sequence, the order is 8 88 and 8 ‘8^{‘}8’. If the order may change to 8 ‘8^{‘}8’ and 8 88 after the sorting, then this sort is an unstable sorting algorithm. If it is not possible to change the order, it is a stable algorithm.
  • Only merge sort can be used for external sort
  • In the following code, swap is used to exchange elements as follows:
private static void swap(int nums, int i, int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

Copy the code

The sorting algorithm and its implementation

Quick sort

  • Here is:

  • Principle: Select an axis element key, through the I j ijij pointer to locate the element, the array to be sorted into the left is less than or equal to key and the right is greater than or equal to key two groups, recursive operation.

  • Time complexity: binary idea, so the average complexity O(nlog ⁡ n)O(n \log n)O(nlogn); However, if the axes of binary selection are extremely uneven each time, it will be higher. For example, if the elements are only divided into 1 and N −1 n-1N −1, it will need to be divided n times, and the number group will be traversed each time, so the worst complexity is O(n2) O(n^2)O(n2). For example, complete positive order, complete reverse order will have the worst case

  • Space complexity: Only axes consume space, whereas dichotomy requires an axis for each part, so space is O(log ⁡ n)O(\log n)O(logn)

  • Stability: According to the figure, when I, J, iJIj are all located at the key of the axis element, position exchange will occur, so there is no stability

  • Reference code

public static void quickSort(int[] nums, int l, int r){ if(l >= r) return; int i = l - 1, j = r + 1; Int key = nums[l]; while(i < j){ while(nums[++i] < key); While (nums[--j] > key); If (I < j) swap(nums, I, j); } quickSort(nums, l, j); quickSort(nums, j + 1, r); }Copy the code

Heap sort

  • Diagram: Relatively complex, not yet
  • Principle: build the big top heap, loop n nn times, each time: swap the top element and the bottom element so that the largest element in the heap is in the correct place of sorting, then adjust the heap downward to complete the heap reconstruction.
  • Time complexity: Each heap adjustment obviously requires tree height h=log ⁡ nh= \log nh=logn comparison. There are a total of N nn numbers and n nn rounds of heap adjustment are required, so the complexity is O(nlog ⁡ n)O(n \log n)O(nlogn). In addition, the heap build time complexity can be reduced to O(n)O(n) O(n)O(n) O(n)O(n) if the heap build time complexity can be reduced to O(n)O(n) O(n)O(n) if the heap build time complexity can be reduced to O(n)O(n) O(n)O(n)
  • Space complexity: constant space is consumed to store temporary variables for comparison
  • Stability: Elements at the bottom of the heap are placed on top of the heap for downsizing, and no matter how downsizing the heap is compared, there is no guarantee that the same elements will not be swapped.
  • Reference code
public static void heapSort(int[] nums){ for (int i = (nums.length >>> 1) - 1; i >= 0; I --){// create heap siftDown(nums, I, nums.length); } for(int i = nums.length - 1; i > 0; I --){// sort swap(nums, 0, I); siftDown(nums, 0, i); } } private static void siftDown(int[] heap, int i, int len){ int curNum = heap[i]; int half = len >>> 1; While (I << half){// Until there are no children int lcIdx = (I << 1) + 1; Int rcIdx = lcIdx + 1; // right child index int temp = heap[lcIdx]; If (rcIdx < len && temp < heap[rcIdx]){temp = heap[lcIdx = rcIdx]; } if (curNum >= temp) break; heap[i] = temp; i = lcIdx; // heap[I] = curNum; }Copy the code

Merge sort

  • Here is:

  • Principle: For two sorted array merge, just need to pass through the two array pointer I j ijij, put the comparison result into the new array, then move the pointer. Merge sort divides an array in pairs until it is of length 1 (ordered), and then merges it to complete the operation.

  • Time complexity: Typical didivide and conquer, time complexity O(nlog ⁡ n)O(n \log n)O(nlogn)

  • Space complexity: Create an auxiliary array to store the merge result during the merge. The length of the array only needs to be the same as the length of the original array, so it is O(n)O(n) O(n)

  • Stability: the order will not be affected when merging, with stability

  • Reference code

public void mergeSort(int nums, int l, int r){ if(l >= r) return; int mid = (l + r) >> 1; mergeSort(nums, l, mid); mergeSort(nums. mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r){ if (nums[i] <= nums[j]) temp[k++] = nums[i++]; else temp[k++] = nums[j++]; } //temp is an external open array while (I <= mid) temp[k++] = nums[I ++]; while (j <= r) temp[k++] = nums[j++]; for (i = l, j = 0; i <= r; i++, j++) nums[i] = temp[j]; }Copy the code

Selection sort

  • Here is:

  • How it works: One round can find the minimum value of an array. The sorting method is to find the minimum value of an array in each round. It is the easiest way to understand the sorting method.

  • Time complexity: n/2 N /2n/2 traversal is required, each traversal needs to search n/2n/ 2n/2 elements on average, therefore, time complexity O(n)O(n) O(n)O(n)

  • Spatial complexity: Constant auxiliary space is required for temporary traversal of comparison elements

  • Stability: Each selection is from front to back, so it can be stable

  • Reference code

public static void selectSort(int nums){ for(int i = 0; i < nums.length; i++){ int idx = i; for(int j = i; j < nums.length; j++){ if(nums[j] < nums[i]) idx = j; } swap(nums, i, idx); }}Copy the code

Insertion sort

  • Here is:

  • Principle: In the sorted sequence, the new array can be ordered by traversing to find the correct position to insert. Therefore, the insertion sort can be inserted into the sorted array from front to back. (An array of elements can be considered an ordered array.)

  • Time complexity: on average, it takes N /2n/ 2n/2 operations to find and insert elements, so the time complexity O(n2) O(n^2)O(n2); If the array is already in ascending order, only n−1 n-1N −1 comparisons are required, so the best time complexity is O(n)O(n) O(n)O(n) and binary search optimization can be reduced to O(log ⁡ n)O(\log n)O(logn)

  • Space complexity: constant auxiliary space is required to store temporary variables during insertion after comparison

  • Stability: can be stable, set the comparison method so that the same time inserted in the back

  • Reference code

public static void insertSort(int nums){ for(int i = 1; i < nums.length; i++){ int temp = nums[i]; for(int j = i; j > 0 && nums[j - 1] > temp; j--){ nums[j] = nums[j - 1]; } nums[j] = temp; }}Copy the code
  • Binary lookup insert sort (that is, using dichotomy optimization when finding insert positions)
public static void insertSort(int nums){ for(int i = 1; i < nums.length; i++){ int temp = nums[i]; int l = 0, r = i - 1; while(l <= r){ int mid = (l + r)/2; if(nums[mid] > temp) r = mid - 1; else l = mid + 1; } for(int j = i; j > low; j--){ nums[j] = nums[j - 1]; } nums[j] = temp; }}Copy the code

Hill sorting

  • Here is:

  • Principle: The insertion sort improvement method, by narrowing the incremental insertion sort to reduce the time complexity, gap to start with half of the array, halving each time, each round to complete an insertion sort across the gap.

  • Time complexity: O(n1.3) O(n^{1.3})O(n1.3), difficult to prove, can be written as O(nlog ⁡ n)O(n \log n)O(nlogn)

  • Space complexity: same time complexity

  • Stability: Unstable due to grouping

  • Reference code

public static void shellSort(int[] nums){ int gap = nums.length; while(true){ gap /= 2; for(int i = 0; i < gap; i++){ temp = nums[i]; for(int j = i; j > 0 && temp > nums[j]; j -= gap){ nums[j] = nums[j - gap]; } nums[i] = temp; } if(gap == 1) break; }}Copy the code

Bubble sort

  • Here is:

  • Principle: “wheel type competition, each winner will participate in the next competition, until the strongest selection; Each time the strongest remaining character is chosen, a match is required.”

  • Time complexity: O(n2) O(n^2)O(n2)

  • Space complexity: constant

  • Stability: stability

  • Reference code

public static void bubbleSort(int nums){
    for(int i = 1; i < nums.length; i++){
        boolean changed = false;
        for(int j = 0; j < nums.length - i;j++){
            if(nums[j] > nums[j + 1]){
                swap(nums, j, j + 1);
                changed = true;
            }
        }
        if(changed == false) break;
    }
}

Copy the code
  • Two-way bubbling (time optimized, also known as “cocktail sequencing”)
public static void bubbleSort(int nums){ int l = 0, r = nums.length - 1, shift = 1; while(l < r){ boolean changed = false; for(int i = l; i < r; i++){ if(nums[i] > nums[i + 1]){ swap(nums, i, i + 1); shift = i; } } r = shift; for(int i = r - 1; i >= l; i--){ if(nums[i] > nums[i + 1]){ swap(nums, i, i + 1); shift = i + 1; } } l = shift; }}Copy the code

Count sorting

  • Illustration: relatively simple, so no illustration
  • Principle: statistical number of occurrences can be
  • Time complexity: Is related to integer ranges
  • Spatial complexity: Is related to integer ranges
  • Stability: stability
  • Reference code
public static void countingSort(int nums){ int[] counter = new int[65535]; For (int I = 0; i < nums.length; i++){ counter[nums[i]]++; } int idx = 0; for(int i = 0; i < counter.length; i++){ while(counter[i] > 0) nums[idx++] = counter[i]; }}Copy the code
  • Limitations: Can only sort integers; A larger integer range opens up more space

Examples of sorting algorithms

Brush problem need to master several algorithms

  • The algorithm idea of quicksort and merge sort: divide and conquer. Divide and conquer is to divide a complex problem into two or more identical or similar sub-problems until the sub-problems can be solved simply and directly. The solution of the original problem is the combination of the solutions of the sub-problems. Obviously in the end, quicksort’s simple concatenation and mergesort’s ordered array merge belong to the simple problem described here.
  • The core advantage of heap sort – find k maximum values. Earlier we said that the heap build time complexity can be reduced to O(n)O(n) O(n)O(n) by adjusting the heap build time complexity up, and each time the heap build time complexity down is O(log ⁡ n)O(\log n)O(logn). Therefore, heap sorting is used to find k maximum values, that is, adjust the heap upward to obtain the maximum value of the heap top, adjust the heap downward to continue to obtain the maximum value of the heap top, and repeat. Thus, when k is small (
  • In fact, most of the time, counting sort is the best algorithm when we know the range of numbers to sort and the maximum and minimum values are not far apart

Leetcode sorting algorithm examples

  • Leetcode [75] Color classification [medium] : Given an array containing n elements of red, white, and blue, sort them in place so that elements of the same color are adjacent and arranged in red, white, and blue order. In this case, we used integers 0, 1, and 2 to represent red, white, and blue, respectively.
  • 【 实 战 例 句 】 The counting sort array is an integer, and the range between 0 and 2 is very small.
class Solution { public void sortColors(int[] nums) { int[] counter = new int[3]; for(int i = 0; i < nums.length; i++){ counter[nums[i]]++; } int idx = 0; for(int i = 0; i < 3; i++){ while(counter[i] > 0){ nums[idx++] = i; counter[i]--; }}}}Copy the code
  • Leetcode [1366] ranks teams by vote [medium] Now has a special ranking system that ranks teams according to the order in which they are ranked in the voter’s mind, and each voter is required to rank all participating teams from highest to lowest. The ranking rules are as follows: Teams are ranked according to the number of “first place” tickets they receive. If there is a tie between multiple teams, the number of “second place” tickets will continue to be considered. And so on, until there is no longer a juxtaposition. If a tie still occurs after all votes are considered, the teams are ranked alphabetically. You are given a string array of votes representing the ranking given by all the voters, and you rank all the teams according to the above ranking rules. Return a string that represents the rank of all teams sorted by the ranking system.
  • A counting sorting method is provided, and HashMap can also be solved. By counting the voting information of each team to sort, finally get the sorting result can be printed. This is equivalent to counting characters with an array of size 26, which is a common method.
class Solution { public String rankTeams(String[] votes) { int len = votes[0].length(); int[][] map = new int[26][len + 1]; For (int I = 0; i < 26; i++) map[i][len] = i; for(int i = 0; i < votes.length; {// votes count String s = votes[I]; for(int j = 0; j < len; j++){ map[s.charAt(j) - 'A'][j]++; }} Arrays. Sort (map, (a, b) ->{array.sort (map, (a, b) ->{ i < len; i++){ if(a[i] < b[i]) return 1; if(a[i] > b[i]) return -1; } return 0; }); StringBuilder sb = new StringBuilder(); for(int i = 0; i < len; I++) {/ / sb. To obtain the results corresponding to team append ((char) (' A '+ map [I] [len])); } return sb.toString(); }}Copy the code
  • Leetcode [973] K points closest to the origin (typical application of heap sorting)
  • K strongest values in leetcode[1471] array (typical application of heap sort)
  • Leetcode [1481] Least Number of Unique Integers after K Removals
  • Leetcode [179] Maximum number (collation design)
  • Leetcode [242] Valid Anagram
  • Leetcode [524] Longest Word in Dictionary through Deleting
  • Largest Perimeter Triangle leetCode [976] Largest Perimeter Triangle
  • Leetcode [1451] Rearrange Words in a Sentence
  • Leetcode [853] Car Fleet N A Car travels along a lane to a common destination located miles away from Target. Each car I travels along the lane to the destination from its initial position[I] (miles) at a constant speed of speed[I] (miles). A car never passes another car in front of it, but it can catch up and follow at the same speed as the car in front. At this point, we ignore the distance between the two cars, that is, they are assumed to be in the same position. A fleet is a non-empty collection of cars traveling at the same speed at the same location. Note that a car can also be a fleet of cars. Even if a vehicle catches up with a convoy at its destination, they are still considered the same convoy.
  • 【 试 题 链 接 】 If a car starts at the front but arrives at its destination later than a car starting at the back, it can be said that it has been overtaken and will form a convoy. So calculate the arrival time, sort it, and count the fleet
class Solution { public int carFleet(int target, int[] position, int[] speed) { int n = position.length, res = 0; double[][] cars = new double[n][2]; For (int I = 0; i < n; i++){ cars[i][0] = position[i]; cars[i][1] = (double)(target - position[i])/speed[i]; } / / start sorting Arrays. Sort (cars, (a, b) - > Double.com pare said ([0] a [0], b)); double cur = 0; for(int i = n - 1; i >= 0 ; -) {/ / I can catch up with the vehicle ahead if (cars [I] [1] > cur) {cur = cars [I] [1]. res++; } } return res; }}Copy the code

summary

  • Fast sort is slow in basic order or reverse order; Basic orderly insertion, hill, bubble fast; Bubble sort slowly in reverse order
  • Any method of grouping confusion is unstable
  • The advantages and disadvantages of average time O(nlog ⁡ n)O(n \log n)O(nlogn) method should be clear: fast discharge speed is the fastest, but may appear slow, unstable; Merging is stable and can be used for external sorting, but consumes large space; Heap sort applies to the top K rows, unstable
  • Count sort is nice, but if it’s an integer and the range is small, use count sort
  • Find the first k by heap sort or by selection sort
  • The core of quicksort is the idea of partition