• Eight sorting algorithms
    • Basic idea 2. Code implementation 3. Time complexity and space complexity
    • 2, Hill sort – 1. Basic idea – 2. Code implementation – 3
    • Basic idea 2. Code implementation 3. Time complexity and space complexity
    • Heap sorting – 1. Basic idea – 2. Code implementation – 3
    • Five, bubble sort – 1. Basic idea – 2. Code implementation – 3. Time complexity and space complexity
    • Quicksort – 1. Basic idea – 2. Code implementation – 3. Time complexity and space complexity
    • Merge sort – 1. Basic idea – 2. Code implementation – 3
    • Eight, radix sort – 1. Basic idea – 2. Code implementation – 3
    • conclusion

Eight sorting algorithms

Links: Sorting algorithm PDF version notes!

First, direct insertion

1. Basic idea

In the set of numbers to be sorted, assuming that the previous (n-1) [n>=2] number is already sorted, we now insert the NTH number into the previous ordered number so that this n number is also sorted. Repeat until everything is sorted.

2. Code implementation

  • 1. Iterate through the array, inserting the second digit forward in each loop

  • 2. Set the insertion number and get the number of digits of the last number in the sorted sequence. Temp and j = I – 1.

  • 3. Start with the last number and loop forward. If the number inserted is less than the current number, move the current number back one bit.

    public static void insertSort(int[] data) { int temp; for(int i = 1; i < data.length; Temp = data[I]; temp = data[I]; int j; for(j = i – 1; j>=0; If (data[j] > temp) {// If (data[j] > temp) {// If (data[j] = data[j]; } else { break; }} data[j+1] = temp; }} 123456789101112131415

3. Time complexity and space complexity

Average complexity of direct insert sort is O(n²), worst time complexity: O(n²), space complexity: O(1), no memory allocated.

Hill sort

In view of the efficiency problem of direct insertion sort, someone has improved and upgraded it, which is now hill sort. Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. Hill sort is an unstable sort algorithm.

1. Basic idea

  • 1. The number of numbers is length, I =length/2, and the numbers with subscript difference of I are divided into a group to form an ordered sequence.

  • 2. Set I = I /2 and divide the numbers with subscript difference of I into a group to form an ordered sequence.

  • 3. Repeat step 2 until k=1 to perform simple insert sort.

Ideas:

  • This sort method, also known as reduced incremental sort, was introduced by D. L. Shell in 1959. The basic idea of the method is as follows: suppose that the sequence of elements to be sorted has N elements, first, take an integer increment (less than N) as an interval to divide all elements into increment subsequences, then put all elements with increment distance into the same subsequence, and implement direct insertion sort in each subsequence respectively. Then, the interval increment is narrowed and the subsequence partitioning and sorting work above is repeated. Until finally increment=1, all elements are sorted in the same subsequence.
  • 2. As the value of increment is large at the beginning, there are few elements in each sub-sequence, and the sorting speed is fast. At the end of the sorting, the value of increment gradually decreases, and the number of elements in the sub-sequence gradually increases.

Example of Hill sort:

2. Code implementation

  • 1. Iterate through the array, inserting the second digit forward in each loop
  • 2. Set the insertion number and get the number of digits of the last number in the sorted sequence. Temp and j = I – 1.
  • 3. Start with the last number and loop forward. If the number inserted is less than the current number, move the current number back one bit.

(1) First determine the interval of subscripts of each group of sequences, and cycle the interval required each time: int I = length/2; i >0 ; i /= 2

(2) and then each group elements in the sequence of insertion sort, a second group of inserted the first number is the first group after insert the first number of the array, from I after every digital insertion sort, sequence is inserted into the sequence is different, is not a subsequence of the circulation, but in a loop for (int j = I; j<length; J++) completes insertion sort of all subsequences.

(3) until I is equal to 0.

public static void shellSort(int[] array) { int length = array.length; for (int i = length / 2; i > 0; I /= 2) {// The interval of the sequence until the interval is one, when there is only one subsequence for (int j = I; j < length; Int temp = array[j]; int temp = array[j]; Int k; for (k = j - i; k >= 0; If (temp < array[k]) {array[k] = array[k]; if (temp < array[k]) {array[k] = array[k]; } else { break; } } array[k + i] = temp; System.out.println(array.toString (array)); } 123456789101112131415161718Copy the code

3. Time complexity and space complexity

The average time complexity and space complexity of Hill sort are O(n²) and O(1).

3. Simple choices

1. Basic idea

The basic principle is as follows: for a given set of records, the smallest record is obtained after the first round of comparison, and then the position of this record is exchanged with the position of the first record; Then the second comparison is made to other records excluding the first record to get the minimum record and exchange it with the second position record; This process is repeated until only one record remains for comparison.

2. Code implementation

  • Int I = 0; int I = 0; i <len ; i++

  • 2. Temporarily set the number in each starting position as min, compare the number with min one by one after the start number, and then save the minimum value to min

  • 3. Swap the minimum value with the start value

    public static void selectSort(int[] array) { int len = array.length; for (int i = 0; i < len; Int min = array[I]; int min = array[I]; // Set the starting number to the minimum value int flag = I; for (int j = i + 1; j < len; If (min > array[j]) {min = array[j]; if (min > array[j]) {min = array[j]; flag = j; } } if (flag ! = i) { array[flag] = array[i]; array[i] = min; } } System.out.println(Arrays.toString(array)); } 123456789101112131415161718

3. Time complexity and space complexity

Simple selection sort takes O(n ^ 2).

Heap sort

1. Basic idea

  • 1. If array[0,…, n-1] represents the sequential storage mode of a complete binary tree, then the internal relationship between parent node Pointers and child node Pointers is as follows:

    Pointer to any node I: parent node: I ==0? Null: (i-1)/2 Left child: 2i + 1 Right child: 2i + 2 1234

  • 2. Stack definitions

    N keyword sequence array[0,…, n-1] if and only if the following requirements are met :(0 <= I <= (n-1)/2) ① array[I] <= array[2i + 1] and array[I] <= array[2i + 2]; Called the small root heap; ② array[I] >= array[2i + 1] and array[I] >= array[2I + 2]; Called the big root heap; 123

  • 3. Build a big top heap

Complete binary tree of n nodes array[0,…, n-1], the last node n-1 is the child of the (n-1-1)/2 nodes. The subtree with (n-1-1)/2 nodes as root is adjusted so that the subtree is called the heap.

For large root heap, the adjustment method is as follows: If [keyword of root node] is less than [keyword of left and right children is larger], then switch.

Then, the subtree root of each node ((n-2)/ 2-1) ~ 0 is adjusted successively to see whether the value of this node is greater than the value of its left and right child nodes. If not, the larger value of the left and right child nodes is exchanged with it. The next level of heap may be damaged after the exchange, so the next level of heap is constructed using the above method. Until the subtree rooted at that node forms the heap.

Build the heap again and again using the above method of adjusting the heap up to the root node.

  • 4. Heap Sort (big top heap)

    (1) Create an initial heap of n elements stored in array[0… n-1]; ② If the top element is exchanged with the bottom element, the maximum value of the sequence is placed in the correct position; ③ Add the first n-1 elements of array[0… n-1] to the root heap again, and repeat step ②③ until only one element is left in the heap. 123

2. Code implementation

/** * @param array */ public static void maxHeapSort(int[] array) {int I; int len = array.length; For (I = len / 2-1; i >= 0; i--) { adjustMaxHeap(array, i, len); } // The top of the heap is the maximum, swap the top of the heap and the last number, re-adjust the maximum heap, the next loop I -- for (I = len-1; i >= 0; i--) { int temp = array[0]; array[0] = array[i]; array[i] = temp; adjustMaxHeap(array, 0, i); } System.out.println(Arrays.toString(array)); } private static void adjustMaxHeap(int[] a, int pos, int len) { int temp; int child; for (temp = a[pos]; 2 * pos + 1 < len; R (I)>=r(2i) r(I)>=r(2i) r(I)>=r(2i+1) child = 2 pos +1; If (child + 1 < len &&a [child] < a[child + 1]) {child++; If (a[child] > temp) {a[pos] = a[child]; } else { break; } } a[pos] = temp; } 1234567891011121314151617181920212223242526272829303132333435363738394041Copy the code

3. Time complexity and space complexity

Time complexity: Build heap: O (n), each adjustment o(log n), so the best, worst, average case: O (n*logn);

Five, bubble sort

Links: Sorting algorithm PDF version notes!

1. Basic idea

A bubble compares all the elements in the sequence in pairs from beginning to end, placing the largest at the end.

Compare all the remaining elements in the sequence again in pairs, placing the largest at the end.

Repeat the second step until only one number remains.

2. Code implementation

/** * @author Fupeng * Bubbling sort optimization 2nd edition * 1st edition optimization adds flag, no number exchange direct return, optimal time complexity O(n) * 2nd edition optimization adds tempPostion to record the position of the last exchange within the loop. */ public static void bubbleSort(int[] array) {int len = array.length - 1; // create a temporary space for the intermediate value int temp; Int tempPostion = 0; For (int I = 0; i < array.length - 1; i++) { int flag = 1; For (int j = 0; int j = 0; j < len; If (array[j] > array[j + 1]) {temp = array[j + 1]; temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; Flag = 0; TempPostion = j; }} // Reduce the number of inner loops by giving len the position last swapped; If (flag == 1) {system.out.println (array.toString (array)); return; } } System.out.println(Arrays.toString(array)); } 1234567891011121314151617181920212223242526272829303132333435363738Copy the code

3. Time complexity and space complexity

Bubble sort is a stable sorting algorithm whose best time complexity is O(n), worst time complexity is O(n²), average time complexity is O(n²) and space complexity is O(1).

Quicksort

1. Basic idea

Quicksort uses a divide-and-conquer strategy to divide a list into two sub-lists. Steps as follows:

  • 1. Pick an element from the sequence, called pivot.
  • 2. Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition ends, the benchmark is in the middle of the array. This is called a partition operation.
  • 3. Recursively arrange subarrays of values less than the base element and those greater than the base element.

At the bottom of the recursion, the size of the column is zero or one, so it’s sorted. The algorithm must end because in each iteration it puts at least one element in its final position.

2. Code implementation

public static void quickSort(int[] array) {
    sort(array, 0, array.length - 1);
    System.out.println(Arrays.toString(array));
}

private static void sort(int[] a, int low, int high) {
    int i = low;
    int j = high;
    if (a.length <= 1) {
        return;
    }
    if (i >= j) {
        return;
    }
    int index = a[i];
    while (i < j) {
        while (i < j && a[j] >= index)
            j--;
        if (a[j] < index)
            a[i++] = a[j];
        while (i < j && a[i] <= index)
            i++;
        if (a[i] > index)
            a[j--] = a[i];
    }
    a[i] = index;
    sort(a, low, i - 1);
    sort(a, i + 1, high);
}
1234567891011121314151617181920212223242526272829
Copy the code

3. Time complexity and space complexity

Although the time complexity of fast sorting reaches O(n²), it is better than the average time complexity of O(n logn) sorting algorithm in most cases.

Merge sort

1. Basic idea

Merge-sort is a sorting method based on the idea of merging. It adopts the classic divide-and-conquer strategy (divide problems into small problems and solve them recursively). The Conquer phase “tinkered” with the answers obtained in the conquer phases, i.e. divide and conquer.

  • Divide and conquer

It can be seen that this structure is very much like a complete binary tree, and the merge sort in this paper is achieved by recursion (or by iteration). Step by step can be understood as the process of recursively dismantling the molecular sequence, recursion depth is log2n.

  • 2. Merge adjacent ordered subsequences to the cure stage, we need to merge two ordered subsequences into an ordered sequence, such as the last merge in the figure above, to merge two ordered subsequences [4,5,7,8] and [1,2,3,6] into the final sequence [1,2,3,4,5,6,7,8]. Let’s look at the implementation steps.



2. Code implementation

public static void mergeSort(int[] array) { int[] temp = new int[array.length]; MergeSort (array, 0, array.length-1, temp); // Create a temporary array whose length is equal to that of the original array before sorting. System.out.println(Arrays.toString(array)); } private static void mergeSort(int[] arr, int left, int right, int []temp) { if(left < right) { int mid = (left+right) / 2; mergeSort(arr, left, mid, temp); // mergeSort(arr, mid+1, right, temp); // Merge (arr, left, mid, right, temp); Private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int I = left; private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int I = left; Int j = mid+1; Int t = 0; / / while temporary array pointer (I < = mid & j < = {right) if (arr [I] < = arr [j]) {\ [t++] = arr [i++]; } else { temp[t++] = arr[j++]; }} while (I < = mid) {/ / on the left to the remaining elements filling into the temp temp [t++] = arr [i++]; } while(j <= right) {temp[t++] = arr[j++]; } t = 0; While (left <= right) {arr[left++] = temp[t++]; }} 1234567891011121314151617181920212223242526272829303132333435363738Copy the code

3. Time complexity and space complexity

Merge sort is stable sort, it is also a very efficient sort, can take advantage of the full binary tree characteristics of sorting generally not too bad performance. Arrays.sort() in Java uses a sort algorithm called TimSort, which is an optimized version of merge sort. Every time you can see from the above figure, merge the average time complexity is O (n), and the depth of full binary tree is | log2n |. The total average time complexity is O(nlogn). In addition, merge sort is best, worst, the average time complexity is O(nlogn).

Radix sort

1. Basic idea

  • 1. The idea of radix sort is to first rank the digits, then rank the tens digit based on the digits, and so on, until the highest digit is traversed, and the sort is finished.
  • 2. Radix sort is not comparative sort, but through the process of allocation and collection
  • 3. Initialize 10 fixed buckets with subscripts from 0 to 9
  • 4. By obtaining ten alleles of the numbers to be sorted, put the item corresponding to this number into the corresponding bucket
  • 5. There are two kinds of radix sort: LSD and MSD, least bit first (starting from the right) and maximum bit first (starting from the left).

2. Code implementation

public static void radixSort(int[] array) { ArrayList<ArrayList<Integer>> queue = new ArrayList<>(); for (int i = 0; i <10 ; i++) { queue.add(new ArrayList<>()); Int Max = array[0]; int Max = array[0]; for (int i = 1; i < array.length; i++) { if (max < array[i]) { max = array[i]; } } int time = 0; while (max > 0) { max /= 10; time++; } for (int i = 0; i < time; I++) {// loop each digit (ones, tens, hundreds) for (int j = 0; j < array.length; Int x = array[j] % (int) math.pow (10, I + 1)/(int) math.pow (10, I); ArrayList<Integer> queue3 = queue.get(x); queue3.add(array[j]); queue.set(x, queue3); } int count = 0; for (int k = 0; k < 10; k++) { while (queue.get(k).size() > 0) { ArrayList<Integer> queue4 = queue.get(k); array[count] = queue4.get(0); queue4.remove(0); count++; }}}} 123456789101112131415161718192021222324252627282930313233343536Copy the code

3. Time complexity and space complexity

Merge sort is stable sort, it is also a very efficient sort, can take advantage of the full binary tree characteristics of sorting generally not too bad performance. Arrays.sort() in Java uses a sort algorithm called TimSort, which is an optimized version of merge sort. Every time you can see from the above figure, merge the average time complexity is O (n), and the depth of full binary tree is | log2n |. The total average time complexity is O(nlogn). In addition, merge sort is best, worst, the average time complexity is O(nlogn).

conclusion