Java 【数据结构】常见排序算法实用详解 冒泡排序/快速排序/归并排序/非基于比较排序
冒泡排序、快速排序、归并排序和堆排序是四种常用的排序算法,以下是它们的Java实现:
冒泡排序:
public 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]) {
// 交换 arr[j+1] 和 arr[j]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
快速排序:
public 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 int partition(int[] arr, int low, int high) {
// 选择一个枢纽元素,这里选择最高位作为枢纽
int pivot = arr[high];
int i = (low - 1);
// 遍历数组,将小于枢纽的元素放到左边,大于枢纽的元素放到右边
for (int j = low; j < high; 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[high];
arr[high] = temp;
return i + 1;
}
归并排序:
public void mergeSort(int[] arr, int low, int high) {
if (low < high) {
// 找到中间索引
int mid = (low + high) / 2;
// 对左边进行递归排序
mergeSort(arr, low, mid);
// 对右边进行递归排序
mergeSort(arr, mid + 1, high);
// 合并两个已排序的子数组
merge(arr, low, mid, high);
}
}
// 合并两个已排序的子数组
private void merge(int[] arr, int low, int mid, int high) {
// 创建一个临时数组
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int k = 0;
// 比较两个子数组,并将较小的元素放入临时数组中
while (i <= mid && j <= high) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++]
评论已关闭