几种常见的排序算法原理以及代码实现
以下是几种常见的排序算法及其原理和代码实现：
1. 冒泡排序 (Bubble Sort)
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
以下是 Java 代码实现：
```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)
插入排序是一种简单的排序算法，它的思想是将未排序的元素一个一个地插入已排序好的序列中。在插入一个元素时，首先要找到该元素合适的位置，通常是在已排序好的序列的末尾。
以下是 Java 代码实现：
```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)
快速排序是一种常用的排序算法，它采用分治的思想，选取一个基准值，将待排序序列划分为两个子序列，其中一个子序列的所有元素都小于基准值，另一个子序列的所有元素都大于等于基准值，然后对这两个子序列递归地进行快速排序。
以下是 Java 代码实现：
```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)
归并排序是一种分治思想的排序算法，它将待排序序列划分为两个子序列，一个子序列的所有元素都小于等于基准值，另一个子序列的所有元素都大于等于基准值，然后对这两个子序列递归地进行归并排序。
以下是 Java 代码实现：
```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)
快速排序中的原地排序是一种高效的排序算法，它利用递归地将待排序序列划分为子序列，然后对子序列进行排序，最后将排序好的子序列合并。
以下是 Java 代码实现：
```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;
}
}
