1. Ten sorting algorithms

Among them, bubble, select, merge, fast, Hill, heap sort belong to comparison sort

Stability understanding

If the relative positions of two elements, which are equal, remain the same before and after sorting, then this is a stable sorting algorithm.

• Before: 5,1,3 (a), 4,7,3 (b)

• Stable order: 1,3 (a), 3(b), 4,5,7

• Unstable order: 1,3 (b), 3(a), 4,5,7

Understand in-place Algorithm

Definition: Not dependent on additional resources or on a small number of additional resources (low spatial complexity), relying only on the output to override the input (such as operating directly on an array of inputs)

2. The tools

Used to provide test data and test code correctness

2.1 Assertion utility classes

public class Asserts { public static void test(boolean value) { try { if (! Value) throw new Exception(" test failed "); } catch (Exception e) { e.printStackTrace(); }}}Copy the code

2.2 Integers Tool classes

Public class Integer {/** generates a random number */ public static Integer[] random(int count, int min, int max) { if (count <= 0 || min > max) return null; Integer[] array = new Integer[count]; int delta = max - min + 1; for (int i = 0; i < count; i++) { array[i] = min + (int)(Math.random() * delta); } return array; } /** combine two arrays */ public static Integer[] combine(Integer[] array1, Integer[] array2) { if (array1 == null || array2 == null) return null; Integer[] array = new Integer[array1.length + array2.length]; for (int i = 0; i < array1.length; i++) { array[i] = array1[i]; } for (int i = 0; i < array2.length; i++) { array[i + array1.length] = array2[i]; } return array; } public static Integer[] same(int count, int unsameCount) { if (count <= 0 || unsameCount > count) return null; Integer[] array = new Integer[count]; for (int i = 0; i < unsameCount; i++) { array[i] = unsameCount - i; } for (int i = unsameCount; i < count; i++) { array[i] = unsameCount + 1; } return array; } /** * Generate an array with ascending heads and tails * disorderCount: */ public static Integer[] headTailAscOrder(int min, int Max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; int begin = (array.length - disorderCount) >> 1; reverse(array, begin, begin + disorderCount); return array; } /** * disorderCount: */ public static Integer[] centerAscOrder(int min, int Max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; int left = disorderCount >> 1; reverse(array, 0, left); int right = disorderCount - left; reverse(array, array.length - right, array.length); return array; } /** * Generate array with ascending header * disorderCount: */ public static Integer[] headAscOrder(int min, int Max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; reverse(array, array.length - disorderCount, array.length); return array; } /** * disorderCount: */ public static Integer[] tailAscOrder(int min, int Max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; reverse(array, 0, disorderCount); return array; } public static Integer[] ascOrder(int min, int Max) {if (min > Max) return null; Integer[] array = new Integer[max - min + 1]; for (int i = 0; i < array.length; i++) { array[i] = min++; } return array; } public static Integer[] descOrder(int min, int Max) {if (min > Max) return null; Integer[] array = new Integer[max - min + 1]; for (int i = 0; i < array.length; i++) { array[i] = max--; } return array; } /** Reverse array */ private static void reverse(Integer[] array, int begin, int end) {int count = (end-begin) >> 1; int sum = begin + end - 1; for (int i = begin; i < begin + count; i++) { int j = sum - i; int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }} public static Integer[] copy(Integer[] array) {return array.copyof (array, array.length); } / * * determine whether array ascending * / public static Boolean isAscOrder (Integer [] array) {if (array = = null | | array. The length = = 0) return false; for (int i = 1; i < array.length; i++) { if (array[i - 1] > array[i]) return false; } return true; } public static void println(Integer[] array) {if (array == null) return; StringBuilder string = new StringBuilder(); for (int i = 0; i < array.length; i++) { if (i ! = 0) string.append("_"); string.append(array[i]); } System.out.println(string); }}Copy the code

2.3 Time test tools

public class Times { private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS"); public interface Task { void execute(); } public static void test(String title, Task task) { if (task == null) return; title = (title == null) ? ": (" [" + title +"] "); System.out.println(title); System.out.println(" start: "+ FMT. Format (new Date())); long begin = System.currentTimeMillis(); task.execute(); long end = System.currentTimeMillis(); System.out.println(" end: "+ FMT. Format (new Date())); Double delta = (end-begin) / 1000.0; double delta = (end-begin) / 1000.0; System.out.println(" time: "+ delta + "); System.out.println("-------------------------------------"); }}Copy the code

2.4 Sort Abstract parent class

Public abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> {/** target array */ protected T[] array; /** private int cmpCount; /** private int swapCount; /** execute time */ private long time; /** DecimalFormat */ private DecimalFormat FMT = new DecimalFormat("#.00"); / * * * pretreatment/public void sort (T [] array) {if (array = = null | | array. The length (2) the return; this.array = array; long begin = System.currentTimeMillis(); sort(); time = System.currentTimeMillis() - begin; } /** object method */ protected void sort(); Array [index1] == array[index2] * returns a value less than 0, array[index1] < array[index2] * returns a value greater than 0, Array [index1] > array[index2] */ protected int CMP (int index1, int index2) {cmpCount++; return array[index1].compareTo(array[index2]); } /** protected int CMP (T value1, T value2) {cmpCount++; return value1.compareTo(value2); } / / protected void swap(int index1, int index2) {swapCount++; T tmp = array[index1]; array[index1] = array[index2]; array[index2] = tmp; } /** Stability test */ @suppressWarnings ("unchecked") private Boolean isStable() {Student[] students = new Sort.Student[20]; for (int i = 0; i < students.length; I ++) {// (0,10) (10, 10) (20,10) (30,10) students[I] = new Student(I * 10, 10); } sort((T[]) students); For (int I = 1; i < students.length; i++) { int score = students[i].score; int prevScore = students[i - 1].score; if (score ! = prevScore + 10) return false; } return true; } private static class Student implements Comparable<Student>{ Integer score; Integer age; public Student(Integer score, Integer age) { this.score = score; this.age = age; } @Override public int compareTo(Student o) { return age - o.age; }} /** Override public int compareTo(Sort o) {int result = (int)(time-o.time); if(result ! = 0) return result; result = cmpCount - o.cmpCount; if(result ! = 0) return result; return swapCount - o.swapCount; } @override public String toString() {return "[" + getClass().getSimplename () +"] \n" + "==>" + NumberString (swapCount) + "\ n" + "more = = >" + numberString (cmpCount) + "\ n" + "execution time = = >" + time * 0.001 + "s" + + "\ n" "Stability = = >" + isStable () + "\ n" + "= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ="; } /** Number formatting */ private String numberString(int number) {if (number < 10000) return "" + number; If (number < 100000000) {return fmt.format(number / 10000.0) + "100000000 "; } return format(number / 100000000.0) + ""; }}Copy the code

3. Bubble Sort

3.1 Execution Process

• Compare each pair of adjacent elements from the beginning, swapping their positions if the first is larger than the second. The element at the end of the round is the largest
• Ignore the largest element found in the first step and repeat the first step until all elements are in order

3.2 Basic Implementation

public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { for (int i = 1; i <= eIndex; i++) { if (cmp(i, i - 1) < 0) { swap(i, i - 1); }}}}Copy the code

3.4 to optimize a

Optimization: If the sequence is fully ordered, bubble sort can be terminated early

Disadvantages: Bubble sort will terminate early only when it is completely ordered, very low probability

public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { boolean sorted = true; for (int i = 1; i <= eIndex; i++) { if (cmp(i,i - 1) < 0) { swap(i, i - 1); sorted = false; } } if (sorted) break; }}Copy the code

3.5 optimization of two

Optimization scheme: If the tail of the sequence has been locally ordered, the position of the last exchange can be recorded to reduce the number of comparisons

<code-pre class="code-pre" id="pre-AZsyhD" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;" >public class BubbleSort<T extends type <T>> extends Sort<T> {/** * If the end of the sequence is already locally ordered, we can record the last position exchanged in order to reduce the number of comparisons * why sortedIndex is 1 (as long as ensure that eIndex-- > 0)? * => If sortedIndex is eIndex, when the array is completely ordered the first time, it will fall back to the original version * => If sortedIndex is 1, when the array is completely ordered the first time, the scan is finished! * */ @Override public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { int sortedIndex = 1; For (int I = 1; i <= eIndex; i++) { if (cmp(i, i - 1) < 0) { swap(i, i - 1); sortedIndex = i; } } eIndex = sortedIndex; } } }</code-pre> </pre></code-box>Copy the code

3.6 Advantages and disadvantages of the algorithm

• Worst, average time complexity: O(n^2), Best time complexity: O(n)

• Space complexity: O(1)

• It’s stable sort

Note: a stable sorting algorithm can also be written as an unstable sorting algorithm with a slight error, as bubble sorting is unstable

<code-pre class="code-pre" id="pre-zmmbCP" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;" >public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { for (int i = 1; i <= eIndex; i++) { if (cmp(i, i - 1) <= 0) { swap(i, i - 1); } } } }</code-pre> </pre></code-box>Copy the code

• In place algorithm

4.1 Execution Process

• Figure out which element is the largest in the sequence, and then swap places with the last element. The element at the end of the round is the largest element
• Ignore the largest element found in the first step and repeat the first step

Let’s take the smallest element as an example

4.2 Basic Implementation

public class SelectionSort<T extends Comparable<T>> extends Sort<T> { @Override public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { int maxIndex = 0; for (int i = 1; i <= eIndex; <= if (CMP (maxIndex, I) <= 0) {maxIndex = I; } } if(maxIndex ! = eIndex) swap(maxIndex, eIndex); }}}Copy the code

4.3 Advantages and disadvantages of the algorithm

• The number of swaps of selection sort is much less than bubble sort and the average performance is better than bubble sort
• The average time complexity is O(n^2), and the space complexity is O(1), which belong to unstable order

Is there room for optimization of selection sorting? => Use heap to select the maximum value

5. Heap Sort

Heap sort can be thought of as an optimization of selection sort

5.1 Execution Process

• Heapify sequences in place
• Repeat until the heap has 1 element
  • Swap top and bottom heap elements
  • The number of elements in the heap minus 1
  • Perform a siftDown operation on position 0

5.2 Basic Implementation

Public class HeapSort<T extends type <T>> extends Sort<T> {private int heapSize; @override protected void sort() {// heapSize = array.length; for (int i = (heapSize >> 1) - 1; i >= 0; i--) { siftDown(i); } while (heapSize > 1) {// Swap (0, --heapSize); SiftDown (0); siftDown(0); Private void siftDown(int index) {T element = array[index]; int half = heapSize >> 1; While (index < half) {childIndex = (index << 1) + 1; childIndex = (index << 1) + 1; T child = array[childIndex]; int rightIndex = childIndex + 1; If (rightIndex < heapSize && CMP (array[rightIndex], child) > 0) {child = array[rightIndex = rightIndex]; If (element, child) >= 0) break; array[index] = child; index = childIndex; } array[index] = element; }}Copy the code

5.2 Advantages and disadvantages of the Algorithm

• Best, worst, average time complexity: O(nlog^n)
• Space complexity: O(1)
• It’s an unstable sort

5.3. Bubble, select, heap sort comparison

@SuppressWarnings({"rawtypes","unchecked"}) public class SortTest { public static void main(String[] args) { Integer[] arr1 = Integers.random(10000, 1, 20000); testSort(arr1, new SelectionSort(), new HeapSort(), new BubbleSort()); } static void testSort(Integer[] arr,Sort... sorts) { for (Sort sort: sorts) { Integer[] newArr = Integers.copy(arr); sort.sort(newArr); // The results of the results of scientific research. } Arrays.sort(sorts); for (Sort sort: sorts) { System.out.println(sort); }}}Copy the code

1. Insertion Sort

6.1 Execution Process

• During execution, insertion sort splits the sequence into two parts (the head is already sorted and the tail is to be sorted)

• Scan each element from the beginning, and when an element is scanned, insert it into the appropriate position in the header so that the header data remains in order

6.2 Basic Implementation

<code-pre class="code-pre" id="pre-cK7r8F" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;" >public class InsertionSort<T extends Comparable<T>> extends Sort<T> { @Override protected void sort() { for (int i = 1;  i < array.length; i++) { int cur = i; while(cur > 0 && cmp(cur,cur - 1) < 0) { swap(cur,cur - 1); cur--; } } } }</code-pre>Copy the code

6.3 Inversion Pair

What is an inverse pair? Reversing the,3,8,6,1 [2] = > array for: < 2, 1 > < 3, 1 > < 8, 1 > < 8, 6 > < 6, 1 >

The time complexity of insertion sort is proportional to the number of inversions

The highest time complexity is O(n^2).

6.4 to optimize a

Optimization idea => Change the exchange to move

• Back up the elements to be inserted first

• In the header ordered data, the element larger than the element to be inserted is moved one position toward the tail

• Place the element to be inserted in its final position

Note: The more inversions there are, the more obvious this optimization is

public class InsertionSort<T extends Comparable<T>> extends Sort<T> { @Override protected void sort() { for (int i = 1; i < array.length; i++) { int cur = i; T val = array[cur]; while(cur > 0 && cmp(val,array[cur - 1]) < 0) { array[cur] = array[cur - 1]; // The optimization focus is here. } array[cur] = val; }}}Copy the code

6.5 optimization of two

Change exchange to binary search (less comparison times)

Dichotomous search comprehension

How do I determine the position of an element in an array? (Assuming the array is full of integers)

• If the array is unordered, the search is traversed from the 0th position. Average time complexity: O(n)

• If the array is ordered, we can use binary search, worst time complexity: order (log^n)

Train of thought

• As follows, suppose we search for an element v in the range [begin, end], mid == (begin + end) / 2
• If v < mid, go to binary search within [begin,mid]
• If v > mid, go binary search in [mid + 1,end]
• If v == mid, return mid

The instance

<code-pre class="code-pre" id="pre-tjxD2m" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;" >/** Binary search - basic implementation * find val's position in ordered array arr, Can't find it returns 1 * / private static int indexOf (Integer [] arr, int val) {if (arr = = null | | arr. Length = = 0) return 1; int begin = 0; (end-begin) int end = arr. Length; while (begin < end) { int mid = (begin + end) >> 1; if(val < arr[mid]) { end = mid; } else if(val > arr[mid]) { begin = mid + 1; } else { return mid; } } return -1; }</code-pre>Copy the code

Binary Search optimization implementation

• Insert val (val); insert val (val)
• Binary searches suitable for insertion sort must return the insertion position of the first element greater than val
  • If val is 5, return 2
  • If val is 1, return 0
  • If val is 15, return 7
  • If val is 8, return 5

• Implementation approach
  • Suppose we search for an element val, mid == (begin + end) / 2 in the range [begin,end]
  • If val < mid, go to binary search in the range [begin,mid]
  • If val >= mid, go binary search in [mid + 1,end]
  • When begin == end == x, x is the position to be inserted
• The instance

[

• Binary search – good for insertion sort
• Find where val can be inserted into the ordered array ARr
• Rule: Binary search is required to return the insertion position of the first element greater than val

private static int search(Integer[] arr,int val) {
    if(arr == null || arr.length == 0) return -1;
    int begin = 0;
    int end = arr.length;
    while (begin < end) {
        int mid = (begin + end) >> 1;
        if(val < arr[mid]) {
            end = mid;
        } else {
            begin = mid  + 1;
        }
    }
    return begin;
}</code-pre> 
Copy the code

Insert sort is finally implemented

Note: Binary search only reduces the number of comparisons, but the average time complexity of insertion sort is still O(n^2).

Public class InsertionSort<T extends type <T>> extends Sort<T> {Override protected void Sort () { for (int begin = 1; begin < array.length; Begin++) {// why pass index instead of value? // => Pass index can also know the previously sorted array range: [0, I) insert(begin,search(begin));}} private void insert(int source,int dest) { Val = array[source]; for (int I = source; I > dest; I --) {array[I] = array[i-1];} Array [dest] = val;} private int search(int index) {T val = array[index]; int begin = 0; int end = index; while (begin < end) { int mid = (begin + end) >> 1; if(cmp(val,array[mid]) < 0) { end = mid; } else { begin = mid + 1; } } return begin; } }Copy the code

6.6 Advantages and Disadvantages of the Algorithm

• Worst, average time complexity is O(n^2), best time complexity is O(n).
• Space complexity is O(1).
• It’s stable sort

7. Merge Sort

7.1 Execution Process

• Continuously split the current sequence into 2 subsequences until no more can be split (only one element in the sequence)
• Continuously merge 2 subsequences into one ordered sequence until only one ordered sequence is left

[

7.2 train of thought

merge

Rough idea

details

• The two groups of sequences that need to be merged exist in the same array and are next to each other

• To better complete the merge operation, it is best to back up one of the sequences, such as [begin,mid].

• Basic implementation

• Case 1: end on the left => end on the left

• Case 2: End the right first => As soon as the right ends, move the left side to the right in sequence

7.3 Basic Implementation

<code-pre class="code-pre" id="pre-fTBJPD" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;" >@SuppressWarnings("unchecked") public class MergeSort<T extends Comparable<T>> extends Sort<T> { private T[] leftArr; @Override protected void sort() { leftArr = (T[]) new Comparable[array.length >> 1]; sort(0, array.length); } private void sort(int begin, int end); private void sort(int begin, int end); int end) { if (end - begin < 2) return; int mid = (begin + end) >> 1; sort(begin, mid); sort(mid, end); merge(begin, Private void merge(int begin, int mid); private void merge(int begin, int mid); private void merge(int begin, int mid); int end) { int li = 0, le = mid - begin; int ri = mid, For (int I = 0; I < le; I ++) {leftArr[I] = array[begin + I];} While (li < le) {// when ri < re, If (ri < re && CMP (array[ri],leftArr[li]) < 0) {array[ai++] = array[ri++];} else {// note the stability array[ai++] = leftArr[li++]; } } } }</code-pre>Copy the code

7.4 Advantages and Disadvantages of the Algorithm

Complexity analysis

<code-pre class="code-pre" id="pre-kBDcFF" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;" + T (n) = > sort () sort () + the merge () = > T (n) = T (n / 2) + T (n / 2) + O (n) (n) = > T = 2 T (n / 2) + O (n) / / as a result of the sort () is a recursive call, expressed in T, And since T(n/2) is hard to estimate, Now to clarify T (n) to O (n) (1) the relationship between T = O (n)/n (1) T = T (n / 2)/(n / 2) + O (1) / / that S (n) = T (n)/n (S (1) = O (1) S (n) = S (n / 2) + O (1) = S (n / 4) + O (2) = S (n / 8) + O (3) = S (n / 2 ^ (k)) + O (k) = S (1) + O (log ^ n) = O (lon ^ n) T (n) = n * S (n) = O (nlog ^ n) = > merge sort time complexity: O(nlog^n)</code-pre>Copy the code

Common recursion

conclusion

• Because merge sort always splits subsequences equally, the best, the worst, the average time is order nlog to the n.

• Space complexity: O(n/2 + log^n) = O(n), n/2 for temporary storage of the left array, log^n for recursive calls

• It’s stable sort