O(N^2)算法
冒泡排序
一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位。
两种优化方式：
- 记录当前轮次是否发生过交换，没有发生过交换表示数组已经有序；
- 记录上次发生交换的位置，下一轮排序时只比较到此位置。
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 如果左边的数大于右边的数，则交换，保证右边的数字最大
swap(arr, j, j + 1);
}
}
}
}
选择排序
双重循环遍历数组，每经过一轮比较，找到最小元素的下标，将其交换至首位。
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j; //记录最小值的下标
}
}
swap(arr, i, minIdx);
}
}
二元选择排序
既然每轮遍历时找出了最小值，何不把最大值也顺便找出来呢？这就是二元选择排序的思想。
使用二元选择排序，每轮选择时记录最小值和最大值，可以把数组需要遍历的范围缩小一倍。
public static void selectionSort2(int[] arr) {
int minIndex, maxIndex;
// i 只需要遍历一半
for (int i = 0; i < arr.length / 2; i++) {
minIndex = i;
maxIndex = i;
for (int j = i + 1; j < arr.length - i; j++) {
if (arr[minIndex] > arr[j]) {
// 记录最小值的下标
minIndex = j;
}
if (arr[maxIndex] < arr[j]) {
// 记录最大值的下标
maxIndex = j;
}
}
// 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 arr[i] 相等，此时已经排序完成
if (minIndex == maxIndex) break;
// 将最小元素交换至首位
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
// 如果最大值的下标刚好是 i，由于 arr[i] 和 arr[minIndex] 已经交换了，所以这里要更新 maxIndex 的值。
if (maxIndex == i) maxIndex = minIndex;
// 将最大元素交换至末尾
int lastIndex = arr.length - 1 - i;
temp = arr[lastIndex];
arr[lastIndex] = arr[maxIndex];
arr[maxIndex] = temp;
}
}
插入排序
插入排序有两种写法：
- 交换法：在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置。
- 移动法：在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。
//交换法
public void insertSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j-1);
}
}
}
小结：
- 选择排序是不稳定的，冒泡排序、插入排序是稳定的；
- 在这三个排序算法中，选择排序交换的次数是最少的；
- 在数组几乎有序的情况下，插入排序的时间复杂度接近线性级别。
O(N*logN)算法
希尔排序
希尔排序本质上是对插入排序的一种优化，它利用了插入排序的简单，又克服了插入排序每次只交换相邻两个元素的缺点。它的基本思想是：
- 将待排序数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组
- 逐渐缩小间隔进行下一轮排序
- 最后一轮时，取间隔为 1，也就相当于直接使用插入排序。但这时经过前面的「宏观调控」，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成
public static void shellSort(int[] arr) {
// 增量序列(增量序列的选择会极大地影响希尔排序的效率)
for (int gap = arr.length / 2; gap > 0; gap--) {
//分组
for (int groupStartIdx = 0; groupStartIdx < gap; groupStartIdx++) {
//插入排序
for (int i = groupStartIdx; i < arr.length; i += gap) {
for (int j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
swap(arr, j, j - gap);
}
}
}
}
}
堆排序
堆排序过程如下：
- 用数列构建出一个大顶堆，取出堆顶的数字；
- 调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字；
- 循环往复，完成整个排序。
public static void heapSort(int[] arr) {
// 构建初始大顶堆
buildMaxHeap(arr);
for (int i = arr.length - 1; i > 0; i--) {
// 将最大值交换到数组最后
swap(arr, 0, i);
// 调整剩余数组，使其满足大顶堆
maxHeapify(arr, 0, i);
}
}
// 构建初始大顶堆
private static void buildMaxHeap(int[] arr) {
// 从最后一个非叶子结点开始调整大顶堆，最后一个非叶子结点的下标就是 arr.length / 2-1
for (int i = arr.length / 2 - 1; i >= 0; i--) {
maxHeapify(arr, i, arr.length);
}
}
// 调整大顶堆，第三个参数表示剩余未排序的数字的数量，也就是剩余堆的大小
private static void maxHeapify(int[] arr, int i, int heapSize) {
// 左子结点下标
int l = 2 * i + 1;
// 右子结点下标
int r = 2 * i + 2;
// 记录根结点、左子树结点、右子树结点三者中的最大值下标
int largest = i;
// 与左子树结点比较
if (l < heapSize && arr[l] > arr[largest]) {
largest = l;
}
// 与右子树结点比较
if (r < heapSize && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
// 将最大值交换为根结点
swap(arr, i, largest);
// 再次调整交换数字后的大顶堆
maxHeapify(arr, largest, heapSize);
}
}
快速排序
快速排序算法的基本思想是：
- 从数组中取出一个数，称之为基数（pivot）
- 遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
- 将左右两个区域视为两个数组，重复前两个步骤，直到排序完成
分区算法
双指针分区算法：从 left 开始，遇到比基数大的数，记录其下标；再从 right 往前遍历，找到第一个比基数小的数，记录其下标；然后交换这两个数。继续遍历，直到 left 和 right 相遇。然后就和刚才的算法一样了，交换基数和中间值，并返回中间值的下标。
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
// 如果区域内的数字少于 2 个，退出递归
if (left >= right) return;
int mid = partition(arr, left, right);
quickSort(arr, left, mid - 1);
quickSort(arr, mid + 1, right);
}
//将 arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
private static int partition(int[] arr, int start, int end) {
int pivot = arr[start];
int left = start + 1; //左边界
int right = end; //右边界
while (left < right) {
// 找到第一个大于基数的位置
while (left < right && arr[left] <= pivot) left++;
// 找到第一个小于基数的位置
while (left < right && arr[right] >= pivot) right--;
if (left < right) {
swap(arr, left, right);
left++;
right--;
}
}
// 如果 left 和 right 相等，单独比较 arr[right] 和 pivot
if (left == right && arr[right] > pivot) right--;
// 将基数和中间数交换
swap(arr, start, right);
return right;
}
归并排序
递归将两个有序的列表合并成一个有序的列表
public static void mergeSort(int[] arr) {
if (arr.length == 0) return;
int[] result = mergeSort(arr, 0, arr.length - 1);
// 将结果拷贝到 arr 数组中
for (int i = 0; i < result.length; i++) {
arr[i] = result[i];
}
}
// 对 arr 的 [start, end] 区间归并排序
private static int[] mergeSort(int[] arr, int start, int end) {
// 只剩下一个数字，停止拆分，返回单个数字组成的数组
if (start == end) return new int[]{arr[start]};
int middle = (start + end) / 2;
// 拆分左边区域
int[] left = mergeSort(arr, start, middle);
// 拆分右边区域
int[] right = mergeSort(arr, middle + 1, end);
// 合并左右区域
return merge(left, right);
}
// 将两个有序数组合并为一个有序数组
private static int[] merge(int[] arr1, int[] arr2) {
int len1 = arr1.length, len2 = arr2.length;
int[] result = new int[len1 + len2];
int idx1 = 0, idx2 = 0;
while (idx1 < len1 && idx2 < len2) {
if (arr1[idx1] <= arr2[idx2]) {
result[idx1 + idx2] = arr1[idx1++];
} else {
result[idx1 + idx2] = arr2[idx2++];
}
}
// 将剩余数字补到结果数组之后
while (idx1 < arr1.length)
result[idx1 + idx2] = arr1[idx1++];
while (idx2 < arr2.length)
result[idx1 + idx2] = arr2[idx2++];
return result;
}
O(N)算法
计数排序
伪计数排序
public static void countingSort9(int[] arr) {
// 建立长度为 9 的数组，下标 0~8 对应数字 1~9
int[] counting = new int[9];
// 遍历 arr 中的每个元素
for (int element : arr) {
// 将每个整数出现的次数统计到计数数组中对应下标的位置
counting[element - 1]++;
}
int index = 0;
// 遍历计数数组，将每个元素输出
for (int i = 0; i < 9; i++) {
// 输出的次数就是对应位置记录的次数
while (counting[i] != 0) {
arr[index++] = i + 1;
counting[i]--;
}
}
}
真正的计数排序
举个例子，班上有 1010 名同学：他们的考试成绩分别是：7, 8, 9, 7, 6, 7, 6, 8, 6, 67,8,9,7,6,7,6,8,6,6，他们需要按照成绩从低到高坐到 0～90～9 共 1010 个位置上。
用计数排序完成这一过程需要以下几步：
- 第一步仍然是计数，统计出：44 名同学考了 66 分，33 名同学考了 77 分，22 名同学考了 88 分，1 名同学考了 99 分；
- 然后从头遍历数组：第一名同学考了 77 分，共有 44 个人比他分数低，所以第一名同学坐在 44 号位置（也就是第 55 个位置）；
- 第二名同学考了 88 分，共有 77 个人（44 + 33）比他分数低，所以第二名同学坐在 77 号位置；
- 第三名同学考了 99 分，共有 99 个人（44 + 33 + 22）比他分数低，所以第三名同学坐在 99 号位置；
- 第四名同学考了 77 分，共有 44 个人比他分数低，并且之前已经有一名考了 77 分的同学坐在了 44 号位置，所以第四名同学坐在 55 号位置。
- ...依次完成整个排序
区别就在于计数排序并不是把计数数组的下标直接作为结果输出，而是通过计数的结果，计算出每个元素在排序完成后的位置，然后将元素赋值到对应位置。
public static void countingSort9(int[] arr) {
// 建立长度为 9 的数组，下标 0~8 对应数字 1~9
int[] counting = new int[9];
// 遍历 arr 中的每个元素
for (int element : arr) {
// 将每个整数出现的次数统计到计数数组中对应下标的位置
counting[element - 1]++;
}
// 记录前面比自己小的数字的总数
int preCounts = 0;
for (int i = 0; i < counting.length; i++) {
int temp = counting[i];
// 将 counting 计算成当前数字在结果中的起始下标位置。位置 = 前面比自己小的数字的总数。
counting[i] = preCounts;
// 当前的数字比下一个数字小，累计到 preCounts 中
preCounts += temp;
}
int[] result = new int[arr.length];
for (int element : arr) {
// counting[element - 1] 表示此元素在结果数组中的下标
int index = counting[element - 1];
result[index] = element;
// 更新 counting[element - 1]，指向此元素的下一个下标
counting[element - 1]++;
}
// 将结果赋值回 arr
for (int i = 0; i < arr.length; i++) {
arr[i] = result[i];
}
}
基数排序
将整数按位数切割成不同的数字，然后按每个位数分别比较。
- 找出数组中最大的数字的位数 maxDigitLength
- 获取数组中每个数字的基数
- 遍历 maxDigitLength 轮数组，每轮按照基数对其进行排序
public class RadixSort {
public static void radixSort(int[] arr) {
if (arr == null) return;
// 找出最大值
int max = 0;
for (int value : arr) {
if (value > max) {
max = value;
}
}
// 计算最大数字的长度
int maxDigitLength = 0;
while (max != 0) {
maxDigitLength++;
max /= 10;
}
// 使用计数排序算法对基数进行排序
int[] counting = new int[10];
int[] result = new int[arr.length];
int dev = 1;
for (int i = 0; i < maxDigitLength; i++) {
for (int value : arr) {
int radix = value / dev % 10;
counting[radix]++;
}
for (int j = 1; j < counting.length; j++) {
counting[j] += counting[j - 1];
}
// 使用倒序遍历的方式完成计数排序
for (int j = arr.length - 1; j >= 0; j--) {
int radix = arr[j] / dev % 10;
result[--counting[radix]] = arr[j];
}
// 计数排序完成后，将结果拷贝回 arr 数组
System.arraycopy(result, 0, arr, 0, arr.length);
// 将计数数组重置为 0
Arrays.fill(counting, 0);
dev *= 10;
}
}
}
Comments | 0 条评论