Let’s talk about some common sorting algorithms

1. Compare two adjacent elements and swap if the second element is less than the first (descending order is the opposite).

1. Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. When done, the last element will be the largest.

1. Repeat for all elements except the last one.

1. Keep repeating these steps for each smaller and smaller number of elements until the entire array is ordered (that is, there are no pairs of elements to compare).

/** * Bubble Sort * * @author SylvanasSun * */ public class Bubble { // This class should not be instantiated. private Bubble() { } /** * Rearranges the array in ascending order, using the natural order. * * @param a * a the array to be sorted */ public static void sort(Comparable[] a) { for (int i = 0; i < a.length - 1; i++) { for (int j = 0; j < a.length - 1 - i; j++) { if (less(a[j + 1], a[j])) { exch(a, j, j + 1); } } } } /** * Rearranges the array in ascending order, using a comparator. * * @param a * a the arry to be sorted * @param comparator * comparator the comparator specifying the order */ public static void sort(Object[] a, Comparator comparator) { for (int i = 0; i < a.length - 1; i++) { for (int j = 0; j < a.length - 1 - i; j++) { if (less(comparator, a[j + 1], a[j])) { exch(a, j, j + 1); } } } } // a < b ? private static boolean less(Comparable a, Comparable b) { return a.compareTo(b) < 0; } // a < b ? private static boolean less(Comparator comparator, Object a, Object b) { return comparator.compare(a, b) < 0; } // exchange a[i] and a[j] private static void exch(Object[] a, int i, int j) { Object temp = a[i]; a[i] = a[j]; a[j] = temp; } // print array elements to console public static void print(Comparable[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } // test public static void main(String[] args) { String[] s = new Scanner(System.in).nextLine().split("\\s+"); Bubble.sort(s); Bubble.print(s); }}Copy the code

1. First, find the smallest element in the array

1. Second, swap it with the first element of the array (or with itself if the first element is the smallest)

1. Again, find the smallest element among the remaining elements and swap it with the second element in the array. And so on until the array is in order.

Like selection sort, all elements to the left of the current index are ordered, but their final position is not determined. It builds an ordered sequence and, for unordered elements, scans back to front in the ordered sequence to find the appropriate position and insert.

The time required for insertion sort depends on the initial order of elements in the input model. Insertion sort is much more efficient when the input model is a partially ordered array.

So insertion sort is very efficient for partially ordered arrays, but also for small arrays.

1. Starting with the first element, the element can be considered ordered

1. Take the next element and scan back to front in the ordered sequence

1. If the element (sorted) is larger than the new element, move it to the next position (right move)

1. Repeat step 3 until you find a place where the sorted element is less than or equal to the new element

1. After inserting the new element into the location

1. Repeat steps 2 to 5

There’s a lot more you can do to optimize insertion sort, so here are two examples.

• The binary search method is used to reduce the number of comparison operations.

  
                                                                  
  public static void sort(Comparable[] a) {
  	int length = a.length;
  	for (int i = 1; i < length; i++) {
  		// binary search to determine index j at which to insert a[i]
  		Comparable v = a[i];
  		int lo = 0, hi = i;
  		while (lo < hi) {
  			int mid = lo + (hi - lo) / 2;
  			if (less(v, a[mid]))
  				hi = mid;
  			else
  				lo = mid + 1;
  		}
  		// insertion sort with "half exchanges"
  		// (insert a[i] at index j and shift a[j], ..., a[i-1] to right)
  		for (int j = i; j > lo; --j)
  			a[j] = a[j - 1];
  		a[lo] = v;
  	}
  }
  
                                                              Copy the code

• Move larger elements to the right in the inner loop instead of always swapping two elements (the number of array accesses can be halved)

  public static void sort(Comparable[] a) { int length = a.length; // put smallest element in position to serve as sentinel int exchanges = 0; for (int i = length - 1; i > 0; i--) { if (less(a[i], a[i - 1])) { exch(a, i, i - 1); exchanges++; } } if (exchanges == 0) return; // insertion sort with half-exchanges for (int i = 2; i < length; i++) { Comparable v = a[i]; int j = i; while (less(v, a[j - 1])) { a[j] = a[j - 1]; j--; } a[j] = v; }}Copy the code

Merge sort is a typical application of divide-and-conquer algorithm. Merging is the merging of two ordered arrays into a larger ordered array.

One major drawback is that it requires extra space (auxiliary arrays) and the extra space required is proportional to N.

1. Apply for a space that is the sum of two ordered sequences and is used to store the combined sequence

1. Declares two Pointers, starting at the start of two ordered sequences

1. Compares the elements to which the two Pointers point, selects the smaller element into the merge space, and moves the pointer to the next position

1. Repeat step 3 until a pointer reaches the end of the sequence

1. Place all remaining elements of the other sequence directly at the end of the merge sequence

Bottom-up is solving the problem step by step.

The idea is to merge those mini-arrays first, then merge the resulting subarrays in pairs until you merge the entire array together.

You can do pwise merge first (think of each element as an array of size 1), then fwise merge (merge two arrays of size 2 into an array of four elements), then fwise merge eight… . In each round of merge, the second subarray of the last merge may be smaller than the first, if not both arrays should be the same size in all merges.

Public static void sort(Comparable[] a) {int N = a.type; Comparable[] aux = new Comparable[N]; for (int len = 1; len < N; len *= 2) { for (int lo = 0; lo < N - len; lo += len + len) { int mid = lo + len - 1; int hi = Math.min(lo + len + len - 1, N - 1); merge(a, aux, lo, mid, hi); }}}Copy the code

Quicksort is also called partition swap sort, which is also a divide-and-conquer sorting algorithm.

One potential downside of quicksort is that the program can be extremely inefficient when shard is unbalanced, so you need to sort the array randomly before quicksort to avoid this.

It splits an array into two subarrays, sorting the two parts independently. It differs from merge sort in that:

• Merge sort divides an array into two subarrays sorted separately, and finally merges the ordered subarrays so that the entire array is sorted.

• Quicksort sorts an array in such a way that when both subarrays are ordered, the entire array is ordered.

• In merge sort, recursive calls occur before processing the entire array; In quicksort, the recursive call occurs after processing the entire array.

• In merge sort, an array is split equally in half, whereas in quicksort, the location of the split depends on the contents of the array.

1. So let’s pick one of these numbersThe benchmark, can be a[lo], which is identified as the scheduled element.

1. Start at the left end of the array (the left pointer) and scan to the right until you find one greater than or equal toThe benchmarkThe element.

1. Starting at the right end of the array (the right pointer), scan left until it finds one less than or equal toThe benchmarkThe element.

1. These two elements are unscheduled, swapping their positions ensures that neither element to the left of the left pointer I is greater thanThe benchmark, the elements to the right of the right pointer j are not less thanThe benchmark).

1. . When two Pointers meet, theThe benchmarkSwap with the rightmost element of the left subarray (a[j]) and return j.

When there are a large number of repeating elements, the recursion of quicksort causes subarrays of all repeating elements to appear frequently, which has the potential to improve the current performance of quicksort from the linear logarithmic level to the linear level.

A simple idea is to split an array into three parts, corresponding to elements less than, equal to, and greater than the shard element.

In the implementation, maintain a left pointer lt such that elements in A [lo.. l-1] are less than the baseline,a right pointer GT such that elements in a[gt+1..hi] are greater than the baseline,a pointer I such that elements in a[LT..i-1] are equal to the baseline, and elements in a[I.. GT] are undetermined.

1. a[i]Less thanThe benchmarkThat will bea[lt]anda[i]Exchange, lt++ & i++.

1. a[i]Is greater thanThe benchmarkThat will bea[gt]anda[i]Exchange, gt -.

1. a[i]Is equal to theThe benchmark,i++.

All of this keeps the array elements unchanged and shrinks the value of GT-I (so the loop ends). All elements are swapped unless they are equal to the shard element.

                                                        
// quicksort the subarray a[lo .. hi] using 3-way partitioning
	private static void sort(Comparable[] a, int lo, int hi) {
		if (hi <= lo)
			return;
		int lt = lo, i = lo + 1, gt = hi;
		Comparable v = a[lo]; // partition element
		// a[lo..lt-1] < a[lt..gt] < a[gt+1..hi]
		while (i <= gt) {
			int cmp = a[i].compareTo(v);
			if (cmp < 0) {
				exch(a, i++, lt++);
			} else if (cmp > 0) {
				exch(a, i, gt--);
			} else {
				i++;
			}
		}
		sort(a, lo, lt - 1);
		sort(a, gt + 1, hi);
	}

                                                    Copy the code

A priority queue is a data structure that supports deletion of maximum (minimum) elements and insertion of elements. Its interior is ordered, and any priority queue can be turned into a sorting method.

Heap sorting can be divided into two phases.

1. The construction phase of the heap, in which the original arrays are reorganized into a heap. Using the sink() function from right to left, the subheap is constructed. Each position in the array is already the root node of a subheap. We only need to scan half of the array because we can skip the subheap of size 1. Finally, the sink() function is called at position 1 to end the scan.

1. In the sinking sort phase, all elements are fetched from the heap in descending order and the sorting result is obtained. Remove the largest element from the heap and place it in the hollowed out position of the array after the heap has shrunk.

In most practical cases, quicksort is the best choice. If stability is important and space is not an issue, merge sort is probably best. But use of quicksort should be seriously considered in any sort application where running time is critical.

In the JDK, arrays.sort () chooses to use different sorting algorithms based on different parameter types. Three-shard quicksort is used for raw data types, and merge sort is used for reference types.