幾種常見(jiàn)的排序算法原理以及代碼實(shí)現(xiàn)
以下是幾種常見(jiàn)的排序算法及其原理和代碼實(shí)現(xiàn)：
1. 冒泡排序 (Bubble Sort)
冒泡排序是一種簡(jiǎn)單的排序算法，它重復(fù)地遍歷要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。
以下是 Java 代碼實(shí)現(xiàn)：
```java??
public class BubbleSort {??
? public static void main(String[] args) {??
? ? ? int[] arr = {5, 2, 8, 4, 9, 1};??
? ? ? bubbleSort(arr);??
? ? ? for (int i = 0; i < arr.length; i++) {??
? ? ? ? ? System.out.print(arr[i] + " ");??
? ? ? }??
? }??
? ??
? public static void bubbleSort(int[] arr) {??
? ? ? int n = arr.length;??
? ? ? for (int i = 0; i < n-1; i++) {??
? ? ? ? ? for (int j = 0; j < n-i-1; j++) {??
? ? ? ? ? ? ? if (arr[j] > arr[j+1]) {??
? ? ? ? ? ? ? ? ? int temp = arr[j];??
? ? ? ? ? ? ? ? ? arr[j] = arr[j+1];??
? ? ? ? ? ? ? ? ? arr[j+1] = temp;??
? ? ? ? ? ? ? }??
? ? ? ? ? }??
? ? ? }??
? }??
}
```
2. 插入排序 (Insertion Sort)
插入排序是一種簡(jiǎn)單的排序算法，它的思想是將未排序的元素一個(gè)一個(gè)地插入已排序好的序列中。在插入一個(gè)元素時(shí)，首先要找到該元素合適的位置，通常是在已排序好的序列的末尾。
以下是 Java 代碼實(shí)現(xiàn)：
```java??
public class InsertionSort {??
? public static void main(String[] args) {??
? ? ? int[] arr = {5, 2, 8, 4, 9, 1};??
? ? ? insertionSort(arr);??
? ? ? for (int i = 0; i < arr.length; i++) {??
? ? ? ? ? System.out.print(arr[i] + " ");??
? ? ? }??
? }??
? ??
? public static void insertionSort(int[] arr) {??
? ? ? int n = arr.length;??
? ? ? for (int i = 1; i < n; i++) {??
? ? ? ? ? int key = arr[i];??
? ? ? ? ? int j = i - 1;??
? ? ? ? ? while (j >= 0 && arr[j] > key) {??
? ? ? ? ? ? ? arr[j + 1] = arr[j];??
? ? ? ? ? ? ? j--;??
? ? ? ? ? }??
? ? ? ? ? arr[j + 1] = key;??
? ? ? }??
? }??
}
```
3. 快速排序 (Quick Sort)
快速排序是一種常用的排序算法，它采用分治的思想，選取一個(gè)基準(zhǔn)值，將待排序序列劃分為兩個(gè)子序列，其中一個(gè)子序列的所有元素都小于基準(zhǔn)值，另一個(gè)子序列的所有元素都大于等于基準(zhǔn)值，然后對(duì)這兩個(gè)子序列遞歸地進(jìn)行快速排序。
以下是 Java 代碼實(shí)現(xiàn)：
```java??
public class QuickSort {??
? public static void main(String[] args) {??
? ? ? int[] arr = {5, 2, 8, 4, 9, 1};??
? ? ? quickSort(arr, 0, arr.length - 1);??
? ? ? for (int i = 0; i < arr.length; i++) {??
? ? ? ? ? System.out.print(arr[i] + " ");??
? ? ? }??
? }??
? ??
? public static void quickSort(int[] arr, int left, int right) {??
? ? ? if (left < right) {??
? ? ? ? ? int pivotIndex = partition(arr, left, right);??
? ? ? ? ? quickSort(arr, left, pivotIndex - 1);??
? ? ? ? ? quickSort(arr, pivotIndex + 1, right);??
? ? ? }??
? }??
? ??
? private static int partition(int[] arr, int left, int right) {??
? ? ? int pivot = arr[left];??
? ? ? int i = left + 1;??
? ? ? int j = right;??
? ? ? while (i <= j) {??
? ? ? ? ? while (i <= j && arr[i] < pivot) {??
? ? ? ? ? ? ? i++;??
? ? ? ? ? }??
? ? ? ? ? while (i <= j && arr[j] >= pivot) {??
? ? ? ? ? ? ? j--;??
? ? ? ? ? }??
? ? ? ? ? if (i <= j) {??
? ? ? ? ? ? ? swap(arr, i, j);??
? ? ? ? ? ? ? i++;??
? ? ? ? ? ? ? j--;??
? ? ? ? ? }??
? ? ? }??
? ? ? swap(arr, left, j);??
? ? ? return j;??
? }??
? ??
? private static void swap(int[] arr, int a, int b) {? ??
? ?int temp = arr[a];? ??
? ?arr[a] = arr[b];? ??
? ?arr[b] = temp;? ??
}
```
4. 歸并排序 (Merge Sort)
歸并排序是一種分治思想的排序算法，它將待排序序列劃分為兩個(gè)子序列，一個(gè)子序列的所有元素都小于等于基準(zhǔn)值，另一個(gè)子序列的所有元素都大于等于基準(zhǔn)值，然后對(duì)這兩個(gè)子序列遞歸地進(jìn)行歸并排序。
以下是 Java 代碼實(shí)現(xiàn)：
```java??
public class MergeSort {??
? ?public static void main(String[] args) {??
? ? ? ?int[] arr = {5, 2, 8, 4, 9, 1};??
? ? ? ?mergeSort(arr, 0, arr.length - 1);??
? ? ? ?for (int i = 0; i < arr.length; i++) {??
? ? ? ? ? ?System.out.print(arr[i] + " ");??
? ? ? ?}??
? ?}??
? ? ?
? ?public static void mergeSort(int[] arr, int left, int right) {??
? ? ? ?if (left < right) {??
? ? ? ? ? ?int middle = (left + right) / 2;??
? ? ? ? ? ?mergeSort(arr, left, middle);??
? ? ? ? ? ?mergeSort(arr, middle + 1, right);??
? ? ? ? ? ?merge(arr, left, middle, right);??
? ? ? ?}??
? ?}??
? ? ?
? ?private static void merge(int[] arr, int left, int middle, int right) {??
? ? ? ?int n1 = middle - left + 1;??
? ? ? ?int n2 = right - middle;??
? ? ? ?int[] L = new int[n1];??
? ? ? ?int[] R = new int[n2];??
? ? ? ?for (int i = 0; i < n1; i++) {??
? ? ? ? ? ?L[i] = arr[left + i];??
? ? ? ?}??
? ? ? ?for (int j = 0; j < n2; j++) {??
? ? ? ? ? ?R[j] = arr[middle + 1 + j];??
? ? ? ?}??
? ? ? ?int i = 0;??
? ? ? ?int j = 0;??
? ? ? ?int k = left;??
? ? ? ?while (i < n1 && j < n2) {??
? ? ? ? ? ?if (L[i] <= R[j]) {??
? ? ? ? ? ? ? ?arr[k] = L[i];??
? ? ? ? ? ? ? ?i++;??
? ? ? ? ? ?} else {??
? ? ? ? ? ? ? ?arr[k] = R[j];??
? ? ? ? ? ? ? ?j++;??
? ? ? ? ? ?}??
? ? ? ? ? ?k++;??
? ? ? ?}??
? ? ? ?while (i < n1) {??
? ? ? ? ? ?arr[k] = L[i];??
? ? ? ? ? ?i++;??
? ? ? ? ? ?k++;??
? ? ? ?}??
? ? ? ?while (j < n2) {??
? ? ? ? ? ?arr[k] = R[j];??
? ? ? ? ? ?j++;??
? ? ? ? ? ?k++;??
? ? ? ?}??
? ?}??
}
```
5. 快速排序中的原地排序 (In-place Sort)
快速排序中的原地排序是一種高效的排序算法，它利用遞歸地將待排序序列劃分為子序列，然后對(duì)子序列進(jìn)行排序，最后將排序好的子序列合并。
以下是 Java 代碼實(shí)現(xiàn)：
```java??
public class QuickSortInplace {??
? ?public static void main(String[] args) {??
? ? ? ?int[] arr = {5, 2, 8, 4, 9, 1};??
? ? ? ?quickSort(arr, 0, arr.length - 1, true);??
? ? ? ?for (int i = 0; i < arr.length; i++) {??
? ? ? ? ? ?System.out.print(arr[i] + " ");??
? ? ? ?}??
? ?}??
? ? ?
? ?public static void quickSort(int[] arr, int left, int right, boolean isLst) {??
? ? ? ?if (left < right) {??
? ? ? ? ? ?int pivotIndex = partition(arr, left, right);??
? ? ? ? ? ?quickSort(arr, left, pivotIndex - 1, isLst);??
? ? ? ? ? ?quickSort(arr, pivotIndex + 1, right, isLst);??
? ? ? ?}??
? ?}??
? ? ?
? ?private static int partition(int[] arr, int left, int right) {??
? ? ? ?int pivot = arr[left];??
? ? ? ?int i = left + 1;??
? ? ? ?int j = right;??
? ? ? ?while (i <= j) {??
? ? ? ? ? ?while (i <= j && arr[i] < pivot) {??
? ? ? ? ? ? ? ?i++;??
? ? ? ? ? ?}??
? ? ? ? ? ?while (i <= j && arr[j] >= pivot) {??
? ? ? ? ? ? ? ?j--;??
? ? ? ? ? ?}??
? ? ? ? ? ?if (i <= j) {??
? ? ? ? ? ? ? ?swap(arr, i, j);??
? ? ? ? ? ? ? ?i++;??
? ? ? ? ? ? ? ?j--;??
? ? ? ? ? ?}??
? ? ? ?}??
? ? ? ?swap(
arr, left, j);
return j;
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
