常用的排序算法

1. 快速排序

1.1 基本思想：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1.2 步骤如下：

选择基准（Pivot）：在数据集之中，选择一个元素作为"基准"（pivot）
分区（Partitioning）：将数组进行分区（partition），将小于基准值的元素移到基准的左边，大于基准值的元素移到基准的右边。分区完成后，基准元素所处的位置就是最终排序后它的位置
递归排序：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序

快速排序在最坏情况下的时间复杂度为O( $n^2$ )，但这种情况非常少见。它的平均时间复杂度为O( $n l o g n$ )，并且由于排序过程是在原地进行分区，所以它不需要额外的存储空间，空间复杂度为O( $l o g n$ )

1.3代码实现：

// 快速排序主方法
public static void quickSort(int[] arr, int low, int high) {if (low < high) {// 分区操作，获取基准元素位置int pivotIndex = partition(arr, low, high);// 递归排序基准左侧子数组quickSort(arr, low, pivotIndex - 1);// 递归排序基准右侧子数组quickSort(arr, pivotIndex + 1, high);}
}// 分区方法
private static int partition(int[] arr, int low, int high) {int pivot = arr[low]; // 选择第一个元素作为基准int i = low;int j = high;while (i < j) {// 从右向左找第一个小于基准的元素while (i < j && arr[j] >= pivot) {j--;}if (i < j) {arr[i++] = arr[j];}// 从左向右找第一个大于基准的元素while (i < j && arr[i] < pivot) {i++;}if (i < j) {arr[j--] = arr[i];}}// 将基准元素放到正确位置arr[i] = pivot;return i;
}

2. 归并排序

2.1 基本思想：

将数组分成若干个小组，先在每个小组内部进行排序，然后将有序的小组合并成更大的有序组，直到整个数组变得有序

2.2 步骤如下：

分解（Divide）：将原始数组切分成较小的数组，直到每个小数组只有一个位置，这时每个小数组都是有序的
合并（Conquer）：将小数组两两合并，保证合并后的数组仍然有序。这一步是通过比较每个小数组中的元素来完成的
重复：重复上述合并操作，直到最终合并成一个有序的数组

归并排序的时间复杂度是 O( $n l o g n$ )，这是因为数组每次都被分成两半（这是一个 $l o g n$ 的过程），并且在合并过程中需要遍历所有元素（这是一个 $n$ 的过程）。此外，归并排序不是原地排序算法，因为它需要额外的存储空间来合并数组。

2.3 代码实现：

// 归并排序主方法（递归实现）
public static void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = (left + right) / 2;// 递归排序左半部分mergeSort(arr, left, mid);// 递归排序右半部分mergeSort(arr, mid + 1, right);// 合并两个有序子数组merge(arr, left, mid, right);}
}// 合并两个有序子数组的方法
private static void merge(int[] arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组存储左右子数组int[] leftArr = new int[n1];int[] rightArr = new int[n2];System.arraycopy(arr, left, leftArr, 0, n1);System.arraycopy(arr, mid + 1, rightArr, 0, n2);// 合并临时数组到原数组int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k++] = leftArr[i++];} else {arr[k++] = rightArr[j++];}}// 复制左子数组剩余元素while (i < n1) {arr[k++] = leftArr[i++];}// 复制右子数组剩余元素while (j < n2) {arr[k++] = rightArr[j++];}
}

3. 插入排序

3.1 基本思想：

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

3.2 步骤如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

插入排序的时间复杂度在最坏情况下是 O( $n^2$ )，平均情况也是 O( $n^2$ )，但在数组几乎排序好的情况下，它可以达到 O( $n$ )

3.3 代码实现：

public static void insertionSort(int[] array) {int n = array.length;for (int i = 1; i < n; i++) {int key = array[i];int j = i - 1;// 将array[i]与已排序好的array[0...i-1]中的元素进行比较，找到合适的位置插入while (j >= 0 && array[j] > key) {array[j + 1] = array[j];j = j - 1;}array[j + 1] = key;}
}

4. 冒泡排序

4.1 基本思想：

重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端

4.2 步骤如下：

比较相邻的元素。如果第一个比第二个大（升序排序），就交换它们两个
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数
针对所有的元素重复以上的步骤，除了最后一个
重复步骤1~3，直到排序完成

冒泡排序的时间复杂度是O( $n^2$ )，因为它需要比较所有相邻的元素对，并且在最坏的情况下需要交换所有的元素

4.3 代码实现：

// 基础冒泡排序实现
public static void bubbleSort(int[] arr) {if (arr == null || arr.length == 0) {return;}int n = arr.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交换元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}// 优化版冒泡排序（带标志位）
public static void optimizedBubbleSort(int[] arr) {if (arr == null || arr.length == 0) {return;}int n = arr.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交换元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}// 如果一轮没有交换，提前结束if (!swapped) {break;}}
}

5. 选择排序

5.1 基本思想：

首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

5.2 步骤如下：

在未排序序列中找到最小（或最大）元素
将其与未排序序列的第一个元素交换位置
在剩余未排序元素中重复上述步骤，直到整个序列排序完成

选择排序的时间复杂度无论是最好、平均还是最坏情况都是 O( $n^2$ )

5.3 代码实现：

// 选择排序主方法
public static void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIndex = i;// 寻找未排序部分的最小元素索引for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换当前元素与找到的最小元素if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}