Detailed explanation of commonly used Java sorting algorithms-javaTutorial-php.cn

1. Selection Sort (SelectSort)

Basic principle: For a given set of records, after the first round of comparison, the smallest record is obtained, and then the record is compared with the position of the first record. Exchange; then perform a second comparison on records other than the first record to obtain the smallest record and exchange positions with the second record; repeat this process until there is only one record to compare.

public class SelectSort {
 public static void selectSort(int[] array) {
 int i;
 int j;
 int temp;
 int flag;
 for (i = 0; i < array.length; i++) {
 temp = array[i];
 flag = i;
 for (j = i + 1; j < array.length; j++) {
 if (array[j] < temp) {
  temp = array[j];
  flag = j;
 }
 }
 if (flag != i) {
 array[flag] = array[i];
 array[i] = temp;
 }
 }
 }
 public static void main(String[] args) {
 int[] a = { 5, 1, 9, 6, 7, 2, 8, 4, 3 };
 selectSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

Copy after login

2. Insertion Sort (InsertSort)

Basic principle: For a given set of data, initially assume that the first record It forms an ordered sequence by itself, and the remaining records are unordered sequences. Then starting from the second record, the currently processed record is inserted into the ordered sequence before it in order according to the size of the record, until the last record is inserted into the ordered sequence.

public class InsertSort {
 public static void insertSort(int[] a) {
 if (a != null) {
 for (int i = 1; i < a.length; i++) {
 int temp = a[i];
 int j = i;
 if (a[j - 1] > temp) {
  while (j >= 1 && a[j - 1] > temp) {
  a[j] = a[j - 1];
  j--;
  }
 }
 a[j] = temp;
 }
 }
 }
 public static void main(String[] args) {
 int[] a = { 5, 1, 7, 2, 8, 4, 3, 9, 6 };
 // int[] a =null;
 insertSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

Copy after login

3. Bubble Sort (BubbleSort)

Basic principle: For a given n records, start from the first record Compare two adjacent records in turn. When the previous record is larger than the following record, swap positions. After a round of comparison and transposition, the largest record among n records will be located at the nth position; then compare the previous ( n-1) records for the second round of comparison; repeat this process until only one record remains for comparison.

public class BubbleSort {
 public static void bubbleSort(int array[]) {
 int temp = 0;
 int n = array.length;
 for (int i = n - 1; i >= 0; i--) {
 for (int j = 0; j < i; j++) {
 if (array[j] > array[j + 1]) {
  temp = array[j];
  array[j] = array[j + 1];
  array[j + 1] = temp;
 }
 }
 }
 }
 public static void main(String[] args) {
 int a[] = { 45, 1, 21, 17, 69, 99, 32 };
 bubbleSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

Copy after login

4. MergeSort(MergeSort)

Basic principle: Use recursion and divide-and-conquer technology to divide the data sequence into smaller and smaller ones half sub-table, then sort the half-sub-table, and finally use recursive method to merge the sorted half-sub-table into an increasingly larger ordered sequence. For a given set of records (assuming a total of n records), first merge every two adjacent subsequences of length 1 to obtain n/2 (rounded up) ordered subsequences of length 2 or 1. subsequences, and then merge them two by two, and repeat this process until an ordered sequence is obtained.

public class MergeSort {
 public static void merge(int array[], int p, int q, int r) {
 int i, j, k, n1, n2;
 n1 = q - p + 1;
 n2 = r - q;
 int[] L = new int[n1];
 int[] R = new int[n2];
 for (i = 0, k = p; i < n1; i++, k++)
 L[i] = array[k];
 for (i = 0, k = q + 1; i < n2; i++, k++)
 R[i] = array[k];
 for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) {
 if (L[i] > R[j]) {
 array[k] = L[i];
 i++;
 } else {
 array[k] = R[j];
 j++;
 }
 }
 if (i < n1) {
 for (j = i; j < n1; j++, k++)
 array[k] = L[j];
 }
 if (j < n2) {
 for (i = j; i < n2; i++, k++) {
 array[k] = R[i];
 }
 }
 }
 public static void mergeSort(int array[], int p, int r) {
 if (p < r) {
 int q = (p + r) / 2;
 mergeSort(array, p, q);
 mergeSort(array, q + 1, r);
 merge(array, p, q, r);
 }
 }
 public static void main(String[] args) {
 int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
 mergeSort(a, 0, a.length - 1);
 for (int j = 0; j < a.length; j++) {
 System.out.print(a[j] + " ");
 }
 }
}

Copy after login

5. Quick Sort (QuickSort)

Basic principle: For a given set of records, after one sorting, The original sequence is divided into two parts, where all the records in the former part are smaller than all the records in the latter part, and then the records in the two parts before and after are quickly sorted, and the process is recursive until all records in the sequence are in order.

public class QuickSort {
 public static void sort(int array[], int low, int high) {
 int i, j;
 int index;
 if (low >= high)
 return;
 i = low;
 j = high;
 index = array[i];
 while (i < j) {
 while (i < j && index <= array[j])
 j--;
 if (i < j)
 array[i++] = array[j];
 while (i < j && index > array[i])
 i++;
 if (i < j)
 array[j--] = array[i];
 }
 array[i] = index;
 sort(array, low, i - 1);
 sort(array, i + 1, high);
 }
 public static void quickSort(int array[]) {
 sort(array, 0, array.length - 1);
 }
 public static void main(String[] args) {
 int a[] = { 5, 8, 4, 6, 7, 1, 3, 9, 2 };
 quickSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

Copy after login

6. Shell Sort (ShellSort)

Basic principle: First divide the array elements to be sorted into multiple subsequences, so that each The number of elements in the subsequence is relatively reduced, and then direct insertion sorting is performed on each subsequence. After the entire sequence to be sorted is "basically in order", all elements are finally subjected to direct insertion sorting.

public class ShellSort {
 public static void shellSort(int[] a) {
 int len = a.length;
 int i, j;
 int h;
 int temp;
 for (h = len / 2; h > 0; h = h / 2) {
 for (i = h; i < len; i++) {
 temp = a[i];
 for (j = i - h; j >= 0; j -= h) {
  if (temp < a[j]) {
  a[j + h] = a[j];
  } else
  break;
 }
 a[j + h] = temp;
 }
 }
 }
 public static void main(String[] args) {
 int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
 shellSort(a);
 for (int j = 0; j < a.length; j++) {
 System.out.print(a[j] + " ");
 }
 }
}

Copy after login

7. Minimum Heap Sort (MinHeapSort)

Basic principle: For a given n records, initially look at these records Make a sequentially stored binary tree, then adjust it into a small top heap, and then exchange the last element of the heap with the top element of the heap. The last element of the heap is the minimum record; then (n-1 ) elements are re-adjusted into a small top heap, and then the top element of the heap is exchanged with the last element of the current heap to obtain the next smallest record. Repeat this process until there is only one element left in the adjusted heap, which element is is the maximum record, and an ordered sequence can be obtained at this time.

public class MinHeapSort {
 public static void adjustMinHeap(int[] a, int pos, int len) {
 int temp;
 int child;
 for (temp = a[pos]; 2 * pos + 1 <= len; pos = child) {
 child = 2 * pos + 1;
 if (child < len && a[child] > a[child + 1])
 child++;
 if (a[child] < temp)
 a[pos] = a[child];
 else
 break;
 }
 a[pos] = temp;
 }
 public static void myMinHeapSort(int[] array) {
 int i;
 int len = array.length;
 for (i = len / 2 - 1; i >= 0; i--) {
 adjustMinHeap(array, i, len - 1);
 }
 for (i = len - 1; i >= 0; i--) {
 int tmp = array[0];
 array[0] = array[i];
 array[i] = tmp;
 adjustMinHeap(array, 0, i - 1);
 }
 }
 public static void main(String[] args) {
 int[] a = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
 myMinHeapSort(a);
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i] + " ");
 }
 }
}

Copy after login

The above is the entire content of this article. I hope that the content of this article can bring some help to everyone's study or work. I also hope to support PHP Chinese. net!

For more detailed explanations of commonly used Java sorting algorithms, please pay attention to the PHP Chinese website!