Sorting algorithm should be the most classic algorithm problems, a wide variety of, we will sort out the most classic several kinds of algorithms;

In this paper, we mainly analyze the selection sort, insertion sort, merge sort, quick sort four kinds of classical sorting algorithm, we default to implement from small to large sorting rules;

1. Selection sort

Select sort is a double for loop, minIndex is the index of the smallest element, and the outer loop finds the index of the smallest element in the remaining element each time, and then swaps I with minIndex to continue the next loop.

The inner loop looks back from the current element. If the value of a subsequent element is less than the value of the minIndex index, the minIndex is updated to the index of that element.

Because it is a nested two-layer for loop, the time complexity is O(n^2), where n represents the number of elements;

Public static void selectionSort(int[] arr) {for (int I = 0; i < arr.length - 1; i++) { int minIndex = i; MinIndex for (int j = I + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } swap(arr, i, minIndex); Private static void swap(int[] arr, int a, int b) {int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }Copy the code

2. Insert sort

The code for insert sort is shown below. Insert sort is also a nested double-layer for loop, so the time complexity is also O(n^2);

The inner for loop indicates that if the current element being compared is smaller than the previous element, the next element will be swapped, and the next element will be compared again.

The outer for loop represents the element currently being compared, so the comparison starts with the second element;

Public static void insertionSort(int[] arr) {for (int I = 1; i < arr.length; For (int j = I - 1; int j = I - 1; int j = I - 1; j >= 0; j--) { if (arr[j] > arr[i]) { swap(arr, i, j); i--; }}}}Copy the code

3. Merge sort

Merge sort splits an array into two halves, merges each half, and merges the two halves. So the time complexity of this binary merge sort is O(nlogn) level;

Actually the main process is that the merge process, first of all, a new auxiliary array, and then the original copy an array by the values to the secondary array, because of the fusion is to merge on both sides, and both sides are sorted subarray, so every time is take on both sides of the first element, the element value small updates to the appropriate location, and then add the index a, Proceed to the next comparison. If one side is at the end of the comparison, the rest of the elements on the other side can be placed directly behind;

Because each comparison requires the comparison of the values of the original array, the update also needs to be updated on the original array, so you need an auxiliary array, copy the values of the original array to the auxiliary array, then you can compare on the auxiliary array, update on the original array; It’s the idea of space for time;

Public static void mergeSort(int[] arr) {mergeSort(arr, 0, arr.leng-1); } private static void mergeSort(int[] arr, int l, int r) {if (l >= r) {return; } // find the midpoint of l and r, and merge the two sides; int mid = l + (r - l) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } // Merge process, Will [l... mid] and [mid + 1... r] two parts fusion private static void merge (int [] arr, int l, int mids, Int r) {// aux = new int[r-l + 1]; for (int i = l; i <= r; i++) { aux[i - l] = arr[i]; } int i = l; int j = mid + 1; for (int k = l; k <= r; k++) { if (i > mid) { arr[k] = aux[j - l]; j++; } else if (j > r) { arr[k] = aux[i - l]; i++; } else if (aux[i - l] < aux[j - l]) { arr[k] = aux[i - l]; i++; } else { arr[k] = aux[j - l]; j++; }}}Copy the code

quicksort

The code for quicksort is shown below. The time complexity of quicksort is also O(nlogn).

The idea of quicksort is as follows: first, partition the original array into two subarrays, and then quicksort the two subarrays, which is also a recursive algorithm;

Partition is a process that first finds the array header, and then iterates the elements behind the array header in sequence. The elements smaller than the array header are placed on the left, and the elements larger than the array header are placed on the right. After iterating, the array header and the boundary point in the middle are exchanged, and the array is divided into two subarrays. The recursive function repeats the process for the subarrays;

Public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int l, int r) {if (l >= r) {return; } int p = partition(arr, l, r); quickSort(arr, l, p - 1); quickSort(arr, p + 1, r); } / / to arr [r] l... the partition process / / return p meet arr... [l] p - 1 < arr [p]. arr[p+1...r] > arr[p] private static int partition(int[] arr, int l, int r) { int aux = arr[l]; //arr[l+1...j]<aux arr[j+1...i-1]>aux int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i] < aux) { swap(arr, j + 1, i); j++; } } swap(arr, l, j); return j; }Copy the code