目录
一、排序算法
1.1 基本介绍
排序是将一组数据依指定的顺序进行排列的过程。
1.2 分类
- 内部排序：将需要处理的所有数据都加载到内部存储器中进行排序。
- 插入排序：直接插入排序、希尔排序
- 选择排序：简单选择排序、堆排序
- 交换排序：冒泡排序、快速排序
- 归并排序
- 基数排序
- 外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。
二、时间复杂度与空间复杂度
2.1 基本介绍
一个算法花费的时间与算法中语句的执行次数成正比。一个算法中的语句执行次数被称为语句频度或时间频度，记为T(n)。
一般情况下，算法中基本操作语句的重复执行次数是问题规模n的某个函数（用T(n)表示）。若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
一个算法所耗费的存储空间被称为算法的空间复杂度，空间复杂度是对算法在运行过程中临时占用存储空间大小的度量。
2.2 计算时间复杂度的方法
- 用常数1代替时间频度中的所有加法常数。
- 只保留时间频度的最高阶项。
- 去除最高阶项的系数。
2.3 常见的时间复杂度
- 常数阶O(1)
int i = 1;
int j = 2;
i++;
j++;
int m = i + j;
代码执行时，消耗的时间不随着某个变量的增长而增长。
- 对数阶O(log₂n)
int i = 1;
while(i < n) {
i = i * 2;
}
假设while循环执行x次后退出循环，则2的x次方等于n（x = log₂n）。
- 线性阶O(n)
for(int i = 1; i <= n; i++) {
j = i;
j++;
}
for循环执行n次。
- 线性对数阶O(nlog₂n)
for(int a = 1; a <=n; a++){
int i = 1;
while(i < n){
i = i * 2;
}
}
将时间复杂度为O(log₂n)的代码执行n次。
- 平方阶O(n²)
for(int a = 1; a <=n; a++) {
for(int i = 1; i <=n; i++) {
j = i;
j++;
}
}
将时间复杂度为O(n)的代码执行n次。
- 指数阶O(2ⁿ)
2.4 平均时间复杂度与最坏时间复杂度
算法的平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
最坏情况下的时间复杂度被称为算法的最坏时间复杂度，一般讨论的时间复杂度均是最坏情况下的时间复杂度。
平均时间复杂度和最坏时间复杂度是否一致与算法有关。
三、冒泡排序（BubbleSort）
3.1 基本思想
从前向后依次比较待排序序列相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部。
3.2 冒泡排序算法实现
代码：
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, -1};
sort(arr);
}
public static void sort(int[] arr) {
//定义临时变量
int temp = 0;
//控制循环次数
for (int i = 0; i < arr.length - 1; i++) {
//定义标记，表示一轮排序中是否进行过交换
boolean flag = false;
//控制每次循环的比较次数
for (int j = 0; j < arr.length - 1 - i; j++) {
//若当前元素大于下一个元素，则交换元素
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第" + (i + 1) + "次排序后的数组：");
System.out.println(Arrays.toString(arr));
//在一轮排序中一次交换都没有发生，则提前结束排序
if (!flag) {
break;
}
}
}
}
结果：
冒泡排序的时间复杂度为O(n²)，空间复杂度为O(1)。
四、选择排序（SelectSort）
4.1 基本思想
第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，通过n-1次的交换得到一个从小到大排序的序列。
4.2 选择排序算法实现
代码：
public class SelectSort {
public static void main(String[] args) {
int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, -1};
sort(arr);
}
public static void sort(int[] arr) {
//控制循环次数
for (int i = 0; i < arr.length - 1; i++) {
//定义最小值
int min = arr[i];
//定义最小值的坐标
int minIndex = i;
//控制每次循环的比较次数
for (int j = i + 1; j < arr.length; j++) {
//若当前元素小于假定的最小值，则重置最小值
if (min > arr[j]) {
min = arr[j];
minIndex = j;
}
}
//若最小值发生改变，则交换元素
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
System.out.println("第" + (i + 1) + "次排序选出的最小值为：" + min);
System.out.println("第" + (i + 1) + "次排序后的数组：");
System.out.println(Arrays.toString(arr));
}
}
}
结果：
选择排序比冒泡排序效率高，高在交换次数上，选择排序的每次交换都是有意义的，两种排序比较次数一致。
选择排序的时间复杂度为O(n²)，空间复杂度为O(1)。
五、插入排序（InsertSort）
5.1 基本思想
将n个待排序的元素看成一个有序表和一个无序表，开始时有序表中包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
5.2 插入排序算法实现
代码：
public class InsertSort {
public static void main(String[] args) {
int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, -1};
sort(arr);
}
public static void sort(int[] arr) {
//定义无序表中待比较元素值
int insertVal = 0;
//定义有序表中待比较元素坐标
int insertIndex = 0;
//控制无序表中待比较元素的坐标
for (int i = 1; i < arr.length; i++) {
insertVal = arr[i];
insertIndex = i - 1;
//寻找待插入元素在有序表中的插入坐标
//如果无序表中待比较元素值小于有序表中待比较元素值
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
//有序表中已比较元素后移
arr[insertIndex + 1] = arr[insertIndex];
//待比较元素坐标前移
insertIndex--;
}
//已找到插入坐标，坐标为待比较元素坐标的后一位
//校验是否需要复制
if (insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
System.out.println("第" + i + "次排序选出的待插入元素为：" + insertVal);
System.out.println("第" + i + "次排序后的数组：");
System.out.println(Arrays.toString(arr));
}
}
}
结果：
插入排序的时间复杂度为O(n²)，空间复杂度为O(1)。
六、希尔排序（ShellSort）
6.1 基本介绍
使用直接插入排序时，当需要插入的数是较小的数时，后移的次数明显增多，对效率产生影响。希尔排序是对直接插入排序经过改进后更高效的版本，也称为缩小增量排序。
6.2 基本思想
把序列按下标的一定增量分组，对每组使用直接插入排序算法排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，所有记录被分成一组，算法终止。
6.3 希尔排序算法实现
代码：
public class ShellSort {
//定义排序次数
private static int count;
public static void main(String[] args) {
int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, -1};
sort(arr);
}
public static void sort(int[] arr) {
//控制增量，逐步缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//定义无序表中待比较元素值
int insertVal = 0;
//定义有序表中待比较元素坐标
int insertIndex = 0;
//对每组使用直接插入排序
for (int i = gap; i < arr.length; i++) {
insertVal = arr[i];
insertIndex = i - gap;
//寻找待插入元素在有序表中的插入坐标
//如果无序表中待比较元素值小于有序表中待比较元素值
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
//有序表中已比较元素后移
arr[insertIndex + gap] = arr[insertIndex];
//待比较元素坐标前移
insertIndex -= gap;
}
//已找到插入坐标，坐标为待比较元素坐标的后一位
//校验是否需要复制
if (insertIndex + gap != i) {
arr[insertIndex + gap] = insertVal;
}
}
System.out.println("第" + (++count) + "次排序的增量为：" + gap);
System.out.println("第" + count + "次排序后的数组：");
System.out.println(Arrays.toString(arr));
}
}
}
结果：
希尔排序的时间复杂度为O(nlog₂n)，空间复杂度为O(1)。
七、快速排序（QuickSort）
7.1 基本思想
快速排序是对冒泡排序的一种改进。从待排序的元素中选择一个作为基准值，通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都小于基准值，另外一部分的所有数据都大于基准值，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程递归进行。
7.2 快速排序算法实现
代码：
public class QuickSort {
private static int count;
public static void main(String[] args) {
int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, -1};
sort(arr, 0, arr.length - 1);
}
public static void sort(int[] arr, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
//定义头指针
int start = startIndex;
//定义尾指针
int end = endIndex;
//将待排序数组的头元素作为基准值
int key = arr[start];
System.out.println("基准值：" + key + "，头指针为：" + start + "，尾指针为：" + end);
while (start < end) {
//尾指针前移，找到第一个比基准值小的元素
while (start < end && arr[end] >= key) {
end--;
}
//使用该元素替换头指针对应的值
arr[start] = arr[end];
//头指针后移，找到第一个比基准值大的元素
while (start < end && arr[start] <= key) {
start++;
}
//使用该元素替换尾坐标对应的值
arr[end] = arr[start];
}
//基准值归位
arr[start] = key;
System.out.println("第" + (++count) + "次排序后的数组：");
System.out.println(Arrays.toString(arr));
//对基准值左边的元素进行递归排序
sort(arr, startIndex, start - 1);
//对基准值右边的元素进行递归排序
sort(arr, end + 1, endIndex);
}
}
结果：
快速排序的时间复杂度为O(nlog₂n)，空间复杂度为O(log₂n)。
八、归并排序（MergeSort）
8.1 基本思想
采用分治策略，将问题分成一些小的问题然后递归求解，再将得到的结果集合并到一起。
8.2 归并排序算法实现
代码：
public class MergeSort {
private static int count;
public static void main(String[] args) {
int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, -1};
sort(arr, 0, arr.length - 1, new int[arr.length]);
}
public static void sort(int[] arr, int startIndex, int endIndex, int[] temp) {
if (startIndex < endIndex) {
//定义数组中间元素坐标
int midIndex = (startIndex + endIndex) / 2;
//向左递归分解数组
sort(arr, startIndex, midIndex, temp);
//向右递归分解数组
sort(arr, midIndex + 1, endIndex, temp);
//合并有序子序列
conquer(arr, startIndex, midIndex, endIndex, temp);
}
}
//合并有序子序列
public static void conquer(int[] arr, int startIndex, int midIndex, int endIndex, int[] temp) {
//定义左边有序序列的头指针
int leftStart = startIndex;
//定义左边有序序列的尾指针
int leftEnd = midIndex;
//定义右边有序序列的头指针
int rightStart = midIndex + 1;
//定义右边有序序列的尾指针
int rightEnd = endIndex;
//定义临时数组当前元素位置
int tempCur = 0;
//将两个有序子序列的元素按大小顺序依次存入临时数组
while (leftStart <= leftEnd && rightStart <= rightEnd) {
//比较两个有序子序列的元素大小
if (arr[leftStart] <= arr[rightStart]) {
temp[tempCur] = arr[leftStart];
//左边有序序列的头指针后移
leftStart++;
} else {
temp[tempCur] = arr[rightStart];
//右边有序序列的头指针后移
rightStart++;
}
//临时数组当前元素位置后移
tempCur++;
}
//若左边有序序列有剩余元素，依次存入临时数组
while (leftStart <= leftEnd) {
temp[tempCur] = arr[leftStart];
tempCur++;
leftStart++;
}
//若右边有序序列有剩余元素，依次存入临时数组
while (rightStart <= rightEnd) {
temp[tempCur] = arr[rightStart];
tempCur++;
rightStart++;
}
tempCur = 0;
//定义arr数组当前元素位置
int arrCur = startIndex;
//将临时数组的元素拷贝到arr数组中
while (arrCur <= endIndex) {
arr[arrCur] = temp[tempCur];
//临时数组当前元素位置后移
arrCur++;
//arr数组当前元素位置后移
tempCur++;
}
System.out.println("第" + (++count) + "次合并的数组：");
for (int i = 0; i <= tempCur - 1; i++) {
System.out.print("" + temp[i] + " ");
}
System.out.println();
}
}
结果：
归并排序的时间复杂度为O(nlog₂n)，空间复杂度为O(n)。
九、基数排序（RadixSort）
9.1 基本介绍
基数排序属于分配式排序，又称桶子法，是使用空间换时间的经典算法。
9.2 基本思想
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后从最低位开始到最高位，依次进行排序，使数列变成一个有序序列。
9.3 基数排序算法实现
代码：
public class RadixSort {
public static void main(String[] args) {
int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, -1};
sort(arr);
}
public static void sort(int[] arr) {
//定义数组存放正数
int[] positiveArr = new int[arr.length];
//定义序列中正数个数
int positiveNum = 0;
//定义数组存放负数
int[] negativeArr = new int[arr.length];
//定义序列中负数个数
int negativeNum = 0;
//定义序列中的最大数
int max = positiveArr[0];
//定义序列中最小数的相反数
int min = negativeArr[0];
//将序列分成正负两部分
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= 0) {
positiveArr[positiveNum] = arr[i];
positiveNum++;
} else {
negativeArr[negativeNum] = arr[i];
negativeNum++;
}
//获取正数中的最大值
if (arr[i] > max) {
max = arr[i];
}
}
//将负数数组转换成正数数组
for (int j = 0; j < negativeNum; j++) {
negativeArr[j] = negativeArr[j] * (-1);
//获取负数中最小值的相反数
if (negativeArr[j] > min) {
min = negativeArr[j];
}
}
//定义max和min的位数
int maxLength = (max + "").length();
int minLength = (min + "").length();
//定义二维数组表示桶，行表示0-9这10个数字，列表示桶大小，为防止所有元素存放同一个桶中导致数据溢出，桶大小为arr.length
int[][] bucket = new int[10][arr.length];
//定义数组，表示每个桶的最大容量
int[] capacity = new int[10];
//排序正数
//控制当前排序位数
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
//对元素的对应位数进行排序处理
for (int j = 0; j < positiveNum; j++) {
//定义元素对应位的数值
int digitOfElement = (positiveArr[j] / n) % 10;
//将元素存入对应桶中
bucket[digitOfElement][capacity[digitOfElement]] = positiveArr[j];
capacity[digitOfElement]++;
}
//定义当前元素位置
int cur = 0;
//遍历桶，将桶中数据存入正数数组中
for (int k = 0; k < 10; k++) {
//判断桶中是否有元素
if (capacity[k] != 0) {
for (int l = 0; l < capacity[k]; l++) {
positiveArr[cur] = bucket[k][l];
cur++;
}
}
//将每个桶中存放的数据个数重置为0
capacity[k] = 0;
}
System.out.println("正数数组第" + (i + 1) + "次排序后的数组：");
System.out.println(Arrays.toString(positiveArr));
}
//排序负数
//控制当前排序位数
for (int i = 0, n = 1; i < minLength; i++, n *= 10) {
//对元素的对应位数进行排序处理
for (int j = 0; j < negativeNum; j++) {
//定义元素对应位的数值
int digitOfElement = (negativeArr[j] / n) % 10;
//将元素存入对应桶中
bucket[digitOfElement][capacity[digitOfElement]] = negativeArr[j];
capacity[digitOfElement]++;
}
//定义当前元素位置
int cur = 0;
//遍历桶，将桶中数据存入负数数组中
for (int k = 9; k >= 0; k--) {
//判断桶中是否有元素
if (capacity[k] != 0) {
for (int l = 0; l < capacity[k]; l++) {
negativeArr[cur] = bucket[k][l];
cur++;
}
}
//将每个桶中存放的数据个数重置为0
capacity[k] = 0;
}
System.out.println("负数数组第" + (i + 1) + "次排序后的数组：");
System.out.println(Arrays.toString(negativeArr));
}
//定义当前元素位置
int cur = 0;
//将正负数组中数据存入原序列中
for (int i = 0; i < negativeNum; i++) {
arr[cur] = negativeArr[i] * (-1);
cur++;
}
for (int j = 0; j < positiveNum; j++) {
arr[cur] = positiveArr[j];
cur++;
}
System.out.println("正负数组合并后的数组：");
System.out.println(Arrays.toString(arr));
}
}
结果：
基数排序的时间复杂度为O(n * k)，空间复杂度为O(n + k)，k为桶的个数。
十、堆排序（HeapSort）
10.1 基本介绍
堆是一种具有以下一种性质的完全二叉树：
- 每个结点的值都大于或等于其左右子节点的值，称为大顶堆。
- 每个结点的值都小于或等于其左右子节点的值，称为小顶堆。
将堆中的节点按层进行编号，映射到数组中，则编号为i的非叶子节点具有以下一种性质：
- 大顶堆：arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2]
- 小顶堆：arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2]
堆对节点左右子结点的大小关系没有要求。
大顶堆用于升序排序，小顶堆用于降序排序。
10.2 基本思想
将待排序序列构造成一个堆，将堆顶元素与末尾元素进行交换，调整结构使余下元素重新满足堆的定义，反复执行调整与交换的步骤，直到整个序列有序。
10.3 堆排序算法实现
代码：
public class HeapSort {
public static void main(String[] args) {
int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, -1};
sort(arr);
}
public static void sort(int[] arr) {
//定义临时变量
int temp = 0;
//从最后一个非叶子节点开始调整，从下至上将序列构建成一个堆
for (int cur = (arr.length / 2) - 1; cur >= 0; cur--) {
System.out.println("从非叶子节点" + arr[cur] + "开始调整序列，构建大顶堆：");
adjustHeap(arr, cur, arr.length);
System.out.println(Arrays.toString(arr));
}
//交换堆顶与末尾元素，i表示剩余参与重构的元素个数
for (int i = arr.length - 1; i > 0; i--) {
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
System.out.println("第" + (arr.length - i) + "次交换堆顶与末尾元素：");
System.out.println(Arrays.toString(arr));
//重新调整结构，使其满足堆的定义
adjustHeap(arr, 0, i);
System.out.println("第" + (arr.length - i) + "次将序列从构成大顶堆，" + i + "个元素参与了重构：");
for (int j = 0; j < i; j++){
System.out.print(arr[j] + " ");
}
System.out.println();
}
System.out.println("排序后数组：");
System.out.println(Arrays.toString(arr));
}
//将序列调整成一个大顶堆
public static void adjustHeap(int arr[], int cur, int length) {
//定义当前堆顶元素的值
int curVal = arr[cur];
//调整序列
for (int child = cur * 2 + 1; child < length; child = child * 2 + 1) {
//获取当前元素子节点中值较大的节点，将i指向该节点
if (child + 1 < length && arr[child] < arr[child + 1]) {
//i指向右子节点
child++;
}
//判断子节点是否大于当前节点
if (arr[child] > curVal) {
//将较大子节点的值赋给当前节点
arr[cur] = arr[child];
//当前元素位置指向较大子节点的位置
cur = child;
} else {
break;
}
}
//将堆顶元素的值赋给当前节点
arr[cur] = curVal;
}
}
结果：
堆排序的时间复杂度为O(nlog₂n)，空间复杂度为O(1)。