最近写题目的时候发现一些排序算法我不太熟悉，简单记录一下。
下面所有的算法都会把数组元素按照升序排序。
插入排序
插入排序的核心思想是：遍历未排序的序列，对未排序序列的元素插入到已排序的序列中。
插入排序的步骤：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5。
public void insertionSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return; // 数组为空或只有一个元素时无需排序
}
for (int i = 1; i < arr.length; i++) {
int key = arr[i]; // key是当前需要插入的元素
int j = i - 1;
// 将比key大的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 元素后移
j--;
}
arr[j + 1] = key; // 把key插入到正确的位置
}
}快速排序
快速排序使用了“分治”的思想，每次选择一个元素，以这个元素为基准，将数组分为小于等于基准和大于基准的部分。再递归地对两边进行排序（也就是对左右两个区间再此选择基准进行划分，如此重复）。
快速排序的步骤：
- 选择基准：从数组中选择一个元素作为基准。基准元素的选择可以是随意的。
- 分区：重新排列数组，使得所有小于基准的元素放在基准前面，大于基准的放在后面。分区结束后，基准处于数组的中间位置。
- 递归：递归地将小于基准的子数组和大于基准的子数组排序。
public void quickSort(int[] array) {
if (array == null || array.length <= 1) return;
sort(array, 0, array.length - 1);
}
private static void sort(int[] array, int low, int high) {
if (low >= high) return;
int pivot = array[high]; // 选择最后一个元素作为基准
int i = low - 1; // 较小元素的边界指针
// 分区操作：将小于基准的元素移到左侧
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, high);
int pivotIndex = i + 1;
// 递归排序两边子数组
sort(array, low, pivotIndex - 1);
sort(array, pivotIndex + 1, high);
}
// 交换两个元素的方法
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}归并排序
归并排序也用到了“分治”的思想，先将序列分为若干个有序的小区间，最后将这些区间逐步合并。
归并排序的步骤：
- 分解：将数组从中间分成两部分。
- 解决：递归地对左右两部分进行归并排序。
- 合并：将两个有序的子数组合并成一个有序数组。
public void mergeSort(int[] array) {
if (array == null || array.length <= 1) return;
int n = array.length;
int[] temp = new int[n];
for (int size = 1; size < n; size *= 2) {
// 内层循环处理每个子数组
for (int left = 0; left < n; left += 2 * size) {
int mid = Math.min(left + size - 1, n - 1);
int right = Math.min(left + 2 * size - 1, n - 1);
// 合并操作
int i = left;
int j = mid + 1;
int k = left;
// 比较并合并两个子数组
while (i <= mid && j <= right) {
if (array[i] <= array[j]) {
temp[k++] = array[i++];
} else {
temp[k++] = array[j++];
}
}
// 处理剩余元素
while (i <= mid) temp[k++] = array[i++];
while (j <= right) temp[k++] = array[j++];
}
}
}堆排序
堆排序的步骤：
- 构建初始堆（这里以升序排序为例，构建大顶堆）。
- 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端。
- 重新调整堆结构（使其满足大顶堆性质），然后继续交换堆顶元素与当前末尾元素。
- 反复执行调整+交换步骤，直到整个序列有序。
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
// 1. 构建大顶堆（从最后一个非叶子节点开始）
for (int i = arr.length / 2 - 1; i >= 0; i--) {
// 堆调整逻辑（原heapify方法内容）
for (int root = i; root < arr.length; ) {
int largest = root;
int left = 2 * root + 1;
int right = 2 * root + 2;
// 找出根节点和子节点中的最大值
if (left < arr.length && arr[left] > arr[largest])
largest = left;
if (right < arr.length && arr[right] > arr[largest])
largest = right;
// 如果最大值不是当前根节点，交换并继续调整
if (largest != root) {
int temp = arr[root];
arr[root] = arr[largest];
arr[largest] = temp;
root = largest; // 移动到交换后的位置继续调整
} else {
break; // 当前子树已满足堆性质
}
}
}
// 2. 排序：逐个提取最大值
for (int size = arr.length - 1; size > 0; size--) {
// 将堆顶元素（最大值）与当前末尾元素交换
int temp = arr[0];
arr[0] = arr[size];
arr[size] = temp;
// 调整剩余元素
for (int root = 0; root < size; ) {
int largest = root;
int left = 2 * root + 1;
int right = 2 * root + 2;
// 找出根节点和子节点中的最大值
if (left < size && arr[left] > arr[largest])
largest = left;
if (right < size && arr[right] > arr[largest])
largest = right;
// 如果最大值不是当前根节点，交换并继续调整
if (largest != root) {
int swapTemp = arr[root];
arr[root] = arr[largest];
arr[largest] = swapTemp;
root = largest; // 移动到交换后的位置继续调整
} else {
break;
}
}
}桶排序
这个算法在写题目的时候遇到了，我之前对这个算法不太熟悉，所以重新学一下。
桶排序的思想是，找出序列中的最大值和最小值，然后分配若干个桶（桶的数量约等于序列中的元素个数），将每个元素放置到对应的桶中，对每一个桶中的元素进行排序，最后把所有桶中的元素整合成排序后的序列。
步骤如下
- 找到数组中的最大值和最小值，以确定数据的范围。
- 确定桶的数量，每个桶代表一个区间范围。
- 遍历数组，将每个元素分配到对应的桶中。
- 对每个桶内的元素进行排序（使用Java内置的排序即可）。
- 按顺序将各个桶中的元素合并回原数组。
第三步中，确定桶的位置，我的理解是“相对”位置，即当前元素相对于序列中最小元素“后移”（可能我描述的不是很恰当，但我觉得看代码就能理解了）。
public static void bucketSort(int[] arr) {
if (arr.length == 0) return;
// 1. 找出数组中的最大值和最小值
int min = arr[0];
int max = arr[0];
for (int num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
// 2. 计算桶的数量和范围
int bucketCount = arr.length; // 通常桶的数量等于元素数量
int range = max - min + 1;
// 3. 初始化桶
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
// 4. 将元素分配到各个桶中
for (int num : arr) {
// 计算元素应该放入哪个桶
int bucketIndex = (int) ((long) (num - min) * bucketCount / range);
// 处理最大值的情况，确保它落在最后一个桶中
if (bucketIndex == bucketCount) bucketIndex--;
buckets.get(bucketIndex).add(num);
}
// 5. 对每个桶内部进行排序
int index = 0;
for (ArrayList<Integer> bucket : buckets) {
Collections.sort(bucket);
for (int num : bucket) {
arr[index++] = num;
}
}
}
1 条评论
等我实习的时候回来看看