一、冒泡排序算法Java版数据结构与算法学习笔记推荐：数据结构与算法Gitee 仓库源码：数据结构与算法
冒泡排序算法思路图解
冒泡排序算法代码实现
public void bubbleSort(int[] array) {
int times = array.length - 1;
// 外层循坏共执行 len - 1 次
for (int i = 0; i < times; i++) {
boolean flag = true;
for (int j = 0; j < times - 1 - i; j++) {
// 如果前一个数比后一个数大则交换
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = false;
}
}
// 如果在某趟排序过程中未发生元素交换则说明数组已有序，可提前结束排序
if (flag) {
break;
}
}
}
冒泡排序算法优化和总结
优化：如果在某趟排序过程中未发生元素交换则说明数组已有序，可提前结束排序
选择排序算法思路图解
选择排序算法代码实现
public void selectSort(int[] array) {
int len = array.length;
// 外层循环共执行 len - 1 次
for (int i = 0; i < len - 1; i++) {
// 假设本轮选择排序中最大的数的下标为 i
int maxIndex = i;
for (int j = i + 1; j < len; j++) {
// 从后序的数组元素中查找看是否有比当前 array[maxIndex] 更大的数，有则将其下标赋值给 maxIndex
if (array[j] > array[maxIndex]) {
maxIndex = j;
}
}
if (maxIndex != i) {
int temp = array[i];
array[i] = array[maxIndex];
array[maxIndex] = temp;
}
}
}
- 选择排序算法速度测试
插入排序算法思路图解
基本思想：把 n 各待排序的数据看作是一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含 n - 1 各元素，排序过程中每次从无序表中取出第一个元素，把它与有序表中的元素依次比较，插入到合适的位置使得有序表依然有序
插入排序算法代码实现
public void insertionSort(int[] array) {
int len = array.length;
// 从第二个元素开始依次为每个元素寻找插入位置
for (int rightIndex = 1; rightIndex < len; rightIndex++) {
int waitInsertValue = array[rightIndex];
int leftIndex = rightIndex - 1;
// 从待插入数据的前一个元素向前查找，当左索引大于等于 0 且元素值大于待插入数据时继续向左查找，过程中元素逐次后移
while (leftIndex >= 0 && array[leftIndex] > waitInsertValue) {
// 将大于待插入数据的元素依次后移
array[leftIndex + 1] = array[leftIndex];
--leftIndex;
}
// 查找结束将 waitInsertValue 插入到空位上
array[leftIndex + 1] = waitInsertValue;
}
}
插入排序算法速度测试
希尔排序算法思路图解
插入排序算法存在的问题：当需要插入的数据较小且位于数组较后时，元素后移的次数明显增多，效率低
希尔排序交换式算法实现
public void hillSort(int[] array) {
int len = array.length;
// 依次将数组按 gap 间隔进行分组
for (int gap = len / 2; gap > 0; gap /= 2) {
// 一组一组地进行遍历
for (int i = gap; i < len; i++) {
// 遍历各组元素，并进行简单插入排序
for (int j = i - gap; j >= 0; j -= gap) {
if (array[j] > array[j + gap]) {
int temp = array[j];
array[j] = array[j + gap];
array[j + gap] = temp;
}
}
}
}
}
希尔排序移位式算法实现
public void hillSort(int[] array) {
int len = array.length;
// 按 gap 间隔对数组进行分组
for (int gap = len / 2; gap > 0; gap /= 2) {
// 依次遍历每一组元素
for (int i = gap; i < len; i++) {
int waitInsertValue = array[i];
int curIndex = i;
// 若当前数据比前一个数据小，继续向前寻找插入位置
if (array[curIndex] < array[curIndex - gap]) {
// 当未找到当前组的最左端元素且当前元素依旧比等待插入的元素值大时，继续寻找插入位置并将元素后移
while (curIndex - gap >= 0 && array[curIndex - gap] > waitInsertValue) {
array[curIndex] = array[curIndex - gap];
curIndex -= gap;
}
// while 循环结束为当前等待插入的数据找到了插入位置
array[curIndex] = waitInsertValue;
}
}
}
}
快速排序算法思路图解
快速排序是对冒泡排序的一种改进。其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行
快速排序算法代码实现
public void quickSort(int[] array, int begin, int end) {
if (begin > end) {
return;
}
// 每次快排选取最左边的数作为基准数
int baseNum = array[begin];
int leftIndex = begin;
int rightIndex = end;
// 在 [begin,end] 区间范围内寻找比基准数小和比基准数大的数进行交换直至左索引与右索引相遇
while (leftIndex != rightIndex) {
// 在右半区间寻找比基准数小的数
while (array[rightIndex] >= baseNum && rightIndex > leftIndex) {
rightIndex--;
}
// 在左半区间寻找比基准数大的数
while (array[leftIndex] <= baseNum && leftIndex < rightIndex) {
leftIndex++;
}
// 如果左半区间找到的比基准数大的数比右半区间找到的比基准数小的数还大，则他俩交换其值
if (array[leftIndex] > array[rightIndex]) {
int temp = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = temp;
}
}
// 将本轮基准数移动到 [begin,end] 区间的中间位置
array[begin] = array[leftIndex];
array[leftIndex] = baseNum;
// 对左半部分数据继续进行快排
quickSort(array, begin, leftIndex - 1);
// 对右半本分数据继续进行快排
quickSort(array, rightIndex + 1, end);
}
快速排序算法速度测试
归并排序算法思路图解
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的
归并排序算法代码实现
public void mergeSort(int[] array, int begin, int end, int[] temp) {
if (begin < end) {
int mid = (begin + end) / 2;
// 向左递归分解左部分
mergeSort(array, begin, mid, temp);
// 向右递归分解右部分
mergeSort(array, mid + 1, end, temp);
// 合并
merge(array, begin, end, temp);
}
}
private void merge(int[] array, int begin, int end, int[] temp) {
// i 为左部分有序表的左索引
int i = begin;
// mid 为本次分解后的中间下标
int mid = (begin + end) / 2;
// j 为右部分有序表的左索引
int j = mid + 1;
// t 为临时数组 temp 的左索引
int t = 0;
// 按升序合并左、右两部分有序表直至一方合并完成，借助临时数组
while (i <= mid && j <= end) {
// 拷贝左部分有序表元素到临时数组
if (array[i] <= array[j]) {
temp[t] = array[i];
t++;
i++;
} else {
// 拷贝右部分有序表元素到临时数组
temp[t] = array[j];
t++;
j++;
}
}
// 将左部分有序表剩余元素拷贝到临时数组
while (i <= mid) {
temp[t] = array[i];
t++;
i++;
}
// 将右部分有序表剩余元素拷贝到临时数组
while (j <= end) {
temp[t] = array[j];
t++;
j++;
}
// 最后将左、右部分有序表合并结果拷贝到原数组中
t = 0;
for (; begin <= end; begin++, t++) {
array[begin] = temp[t];
}
}
归并排序算法速度测试
基数排序算法思路图解
基数排序是对桶排序的扩展。其基本思想是将所有待比较的数值统一为同样长度的数位，数位较短的前面补 0。然后，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位的排序完成以后，数列就已然有序
基数排序算法代码实现 1
基数排序算法代码实现 2
public void radixSort(int[] array) {
// 获取数组中数字的最大位数
int maxDigits = getMaxDigits(array);
int len = array.length;
// 定义十个桶，编号依次为 0 ~ 9，每个桶依次记录末尾数字与桶编号相同的元素值
int[][] bucket = new int[10][len];
// 定义一维数组存放每个桶放置的元素个数
int[] digitsInBucket = new int[len];
// 循环 maxDigits 轮，依次将数字归到对应的桶中
for (int k = 0; k < maxDigits; k++) {
for (int num : array) {
int lastNumber = (num / (int) Math.pow(10, k)) % 10;
// 将 num 放到对应的桶编号中
bucket[lastNumber][digitsInBucket[lastNumber]] = num;
digitsInBucket[lastNumber]++;
}
// 遍历十个桶，将其中存放的数据重新赋值给 array
int arrayIndex = 0;
for (int i = 0; i < 10; i++) {
// 判断桶中是否有数据，有则遍历取出
if (digitsInBucket[i] != 0) {
for (int j = 0; j < digitsInBucket[i]; j++) {
array[arrayIndex] = bucket[i][j];
arrayIndex++;
}
// 元素取出后对应桶编号中存放的数据个数置 0
digitsInBucket[i] = 0;
}
}
}
}
private int getMaxDigits(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int maxNum = 0;
for (int num : array) {
if (num > maxNum) {
maxNum = num;
}
}
return (maxNum + "").length();
}
基数排序算法注意事项
基数排序是效率较高的的稳定性排序法排序算法的稳定性是指，在需要进行排序操作的数据中，如果存在值相等的元素，在排序前后，相等元素之间的相对位置不发生变化
大顶堆和小顶堆图解说明
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序也是一种选择排序，它的最坏、最好、平均时间复杂度均为 O(nlog2n)，是不稳定算法大顶堆：每个节点的值都大于或等于其左右孩子节点的值（并未要求左右孩子值的大小关系）小顶堆：每个节点的值都小于或等于其左右孩子节点的值（并未要求左右孩子值的大小关系）对堆中的节点按层从左至右从 0 开始编号映射到数组，有如下规律：array[i] >= array[2 * i + 1] && array[i] >= array[2 * i + 2] 即父节点大于等于左右子节点堆排序时一般升序采用大顶堆，降序采用小顶堆
堆排序的思路图解
堆排序的基本思想：将待排序序列构建成一个大顶堆，此时整个序列的最大值就是此大顶堆的根节点；再将剩余的 n - 1 个元素重新构建成大顶堆，如此往复，最终可实现对序列的升序排列排序过程：从最后一个非叶子节点开始（第一个非叶子节点在数组中的下标：array.length / 2 - 1，从左至右、从下至上进行调整，将最大的元素调整到根节点
堆排序的代码实现 1
将给定数组调整为堆结构
public void adjustToHeap(int[] array, int fatherIndex, int count) {
// 取出当前非叶子节点（父节点）的值
int temp = array[fatherIndex];
// k = fatherIndex * 2 + 1 是以 fatherIndex 下标为父节点的左子节点下标
for (int k = fatherIndex * 2 + 1; k < count; k = k * 2 + 1) {
// 左子节点比右子节点小
if (k + 1 < count && array[k] < array[k + 1]) {
k++;
}
// 如果子节点的值比父节点大，交换子父节点的值
if (array[k] > temp) {
array[fatherIndex] = array[k];
array[k] = temp;
// 将子节点的下标赋给父节点以便从当前子节点再进行判断以完整当前子树的调整
fatherIndex = k;
} else {
break;
}
}
}
堆排序的代码实现 2
public void headSort(int[] array) {
int len = array.length;
// 1. 将无序序列构建成一个堆，升序选择构建大顶堆
// i = len / 2 - 1 为 第一个非叶子节点在数组中的下标
for (int i = len / 2 - 1; i >= 0; i--) {
adjustToHeap(array, i, array.length);
}
// 2. 将堆顶元素与数组末尾元素交换，以将最大元素 “沉” 到数组末端，下轮不再参与构建堆
// 3. 重新调整数组结构使其满足堆的定义，继续下沉
for (int j = len - 1; j > 0; j--) {
int temp = array[j];
array[j] = array[0];
array[0] = temp;
adjustToHeap(array, 0, j);
}
}
- 堆排序的速度测试和小结
桶排序示意图
计数排序示意图
排序算法时间复杂度比较
