冒泡排序 (Bubble Sort)
基本思想：
冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
算法步骤：
- 从第一个元素开始，比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码实现
public class BubbleSort {
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;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
选择排序 (Selection Sort)
基本思想：
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
算法步骤：
- 在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
- 以此类推，直到所有元素均排序完毕。
代码实现：
public class SelectionSort {
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; // 更新最小元素的索引
}
}
// 将找到的最小元素与第一个未排序位置上的元素交换
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
selectionSort(arr);
System.out.println("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
插入排序 (Insertion Sort)
基本思想：
插入排序的工作方式是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5。
代码实现：
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) { // 从第二个元素开始遍历
int key = arr[i]; // 取出当前元素作为key
int j = i - 1; // 从已排序序列的最后一个元素开始比较
// 将比key大的元素后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // 找到合适的位置插入key
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
insertionSort(arr);
System.out.println("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
希尔排序 (Shell Sort)
基本思想：
希尔排序是插入排序的一种更高效的改进版本，也称为缩小增量排序。希尔排序是非稳定排序算法。该算法的基本思想是：先将整个待排序的记录序列分割成为若干子序列（由相隔某个“增量”的记录组成）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
算法步骤：
- 选择一个增量序列 t1，t2，…，tk，其中 ti > tj，tk = 1。
- 按增量序列个数 k，对序列进行 k 趟排序。
- 每趟排序，根据对应的增量 ti，将待排序列分割成 m = n/ti（n 为序列的长度）个长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
- 重复第2步，直到增量 ti = 1。
代码实现：
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
int gap = n / 2; // 初始增量
// 动态定义增量序列
while (gap > 0) {
// 对每个子序列进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
// 插入排序
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap /= 2; // 缩小增量
}
}
public static void main(String[] args) {
int[] arr = {9, 8, 3, 7, 5, 6, 4, 1};
shellSort(arr);
System.out.println("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
归并排序 (Merge Sort)
基本思想：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法步骤：
- 分解：将数组分解成两个较小的子数组，直到子数组的大小为1。
- 递归进行排序并合并：递归地对子数组进行排序，并将已排序的子数组合并成一个大的有序数组，直到合并为1个完整的数组。
代码实现：
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 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[] temp = new int[right - left + 1]; // 创建临时数组存放合并结果
int i = left; // 左半部分索引
int j = mid + 1; // 右半部分索引
int k = 0; // 临时数组索引
// 合并操作
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 将剩余的元素拷贝到临时数组中
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组中的元素拷贝回原数组
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}
public static void main(String[] args) {
int[] arr = {9, 8, 3, 7, 5, 6, 4, 1};
mergeSort(arr);
System.out.println("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
快速排序 (Quick Sort)
基本思想：
快速排序使用分治法的策略来把一个序列分为两个子序列，其中左边的子序列元素都不大于右边的子序列元素，然后再按此方法对子序列进行快速排序，整个序列有序。
算法步骤：
- 选择一个基准元素（pivot）。
- 通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可对这两部分记录分别继续进行排序，以达到整个序列有序。
代码实现：
public class QuickSort {
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[right]; // 选择最右边的元素作为基准
int i = left - 1; // 小于基准的元素的索引
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准元素放到正确的位置
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {9, 8, 3, 7, 5, 6, 4, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
堆排序 (Heap Sort)
基本思想：
堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆排序的基本思想是将待排序的序列构造成一个大顶堆或小顶堆，此时整个序列的最大值（或最小值）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个序列重新构造成一个堆，这样会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。
算法步骤：
- 建堆：将无序序列构造成一个大顶堆（或小顶堆）。
- 堆调整排序：
- 将堆顶元素与末尾元素进行交换，此时末尾就为最大值。
- 将剩余n-1个序列重新构造成一个堆。
- 重复上述步骤，直到整个序列有序。
代码实现：
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// 建堆
for (int i = n / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, n);
}
// 堆调整排序
for (int i = n - 1; i > 0; i--) {
// 交换堆顶元素和当前未排序序列的最后一个元素
swap(arr, 0, i);
// 重新调整堆
adjustHeap(arr, 0, i);
}
}
private static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
heapSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
计数排序 (Counting Sort)
基本思想：
计数排序是一种非基于比较的排序算法，适用于一定范围内的整数排序。通过统计每个元素出现的次数，将元素放到正确的位置上。
算法步骤：
- 找出待排序的数组中最大和最小的元素。
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项。
- 对C进行累加操作，使C[i]现在包含实际小于或等于i的元素的数量。
- 反向遍历原始数组，将每个元素arr[i]放到输出数组的第C[arr[i]]项，每放一个元素就将C[arr[i]]减1。
代码实现：
public class CountingSort {
public static void countingSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// 找到数组中的最大值和最小值
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
// 初始化计数数组
int[] count = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
// 累加计数数组
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 排序
int[] sortedArr = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
sortedArr[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
// 将排序后的数组拷贝回原数组
System.arraycopy(sortedArr, 0, arr, 0, arr.length);
}
public static void main(String[] args) {
int[] arr = {4, 2, 2, 8, 3, 3, 1};
countingSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
桶排序 (Bucket Sort)
基本思想：
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
- 首先要使得数据分散得尽可能均匀；
- 对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
算法步骤：
- 设置一个定量的数组当作空桶子。
- 寻访序列，并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
代码实现：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// 找到数组中的最大值和最小值
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
} else if (arr[i] > max) {
max = arr[i];
}
}
// 计算桶的数量
int bucketSize = (max - min) / arr.length + 1;
List<List<Integer>> buckets = new ArrayList<>(arr.length);
for (int i = 0; i < arr.length; i++) {
buckets.add(new ArrayList<>());
}
// 将元素放入桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) ((arr[i] - min) / bucketSize);
buckets.get(index).add(arr[i]);
}
// 对每个桶中的元素进行排序
int k = 0;
for (List<Integer> bucket : buckets) {
if (!bucket.isEmpty()) {
Collections.sort(bucket);
for (int num : bucket) {
arr[k++] = num;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bucketSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
基数排序（Radix Sort）
基本思想
一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。这里，我们假设要排序的整数都是非负整数。基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
算法步骤：
- 找到最大数：首先找到待排序数组中的最大数，确定位数。
- 从最低位开始排序：对每一位使用稳定的排序算法进行排序，例如计数排序。
- 依次进行更高位的排序：从最低位开始，依次对每一位进行排序，直到最高位。
- 收集排序结果：每次排序后，根据排序的键值收集排序结果。
代码实现：
public class RadixSort {
// 获取最大数的位数
private static int getMaxDigit(int[] arr) {
int max = arr[0];
for (int num : arr) {
max = Math.max(max, num);
}
int digit = 0;
while (max != 0) {
max /= 10;
digit++;
}
return digit;
}
// 基数排序函数
public static void radixSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// 获取最大位数
int maxDigit = getMaxDigit(arr);
// 初始化桶
int[] bucket = new int[arr.length];
int[] count = new int[10]; // 假设我们排序的是十进制数
// 从最低位开始排序
for (int i = 0; i < maxDigit; i++) {
// 计数排序
for (int j = 0; j < arr.length; j++) {
int digit = (arr[j] / (int) Math.pow(10, i)) % 10;
count[digit]++;
}
// 计算前缀和
for (int j = 1; j < count.length; j++) {
count[j] += count[j - 1];
}
// 收集结果
for (int j = arr.length - 1; j >= 0; j--) {
int digit = (arr[j] / (int) Math.pow(10, i)) % 10;
bucket[count[digit] - 1] = arr[j];
count[digit]--;
}
// 复制回原数组
for (int j = 0; j < arr.length; j++) {
arr[j] = bucket[j];
}
// 重置count数组
for (int j = 0; j < count.length; j++) {
count[j] = 0;
}
}
}
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}