提高效率的本质：少做事情（效率＝产出／所做的事情）【 面试题】
提高效率的本质：少做事情（效率＝产出／所做的事情）【 面试题】
引言
衡量算法的标准-算法复杂度：https://blog.csdn.net/z929118967/article/details/131809460
二叉树的应用（树形选择排序)【面试题】:https://blog.csdn.net/z929118967/article/details/115935678
效率＝产出／所做的事情
提高效率的本质：让计算机少做事情
在边界内做事情：从数学上可以证明N个任意随机数的排序，复杂度不可能比N乘以log（N）更低，这是数学给出的极限（边界）。
I 提高效率的本质：少做事情
1.1 归并排序
归并排序利用了少做事情的思想，减少数据之间的相互比较，对冒泡排序进行改进。
原理：自顶向下细分，再自底向上合并。
将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列间有序地合并成一个有序序列。
将一个复杂问题分解成很多简单的问题，一个个解决，最后比直接解决复杂问题要省很多时间。
- 冒泡排序的时间复杂度为
O(n^2)。 - 归并排序的时间复杂度为
O(nlogn)。
1.2 快速排序
通常情况下最好的排序算法是"快速排序（Quicksort）"算法，它是基于比较的排序算法，其时间复杂度平均情况下是 O(nlogn)，最坏情况下是 O(n^2)，工程师们会想一些方法防止极端糟糕情况的发生。
最好的计算机算法总是有附加条件，没有绝对的最好。 常情况下复杂度是N乘以log（N），和归并排序相同。根据计算机科学的标准，它们同样好。
在工程上，快速排序算法一般情况下比归并排序快两倍。
原理：快速排序还是强调少做事情
- 对于一大堆无序的数字，从中随机挑选一个，这个被随机选上的数字被称为
枢值，接下来，将所有要排序的数字分成两部分，第一部分是大于等于枢值的，第二部分是小于枢值的。 - 从上面得到的两堆数字，分别采用第一步的方法各自再找一个枢值。接下来，再把两堆数字各自分成大于等于相应枢值的数字序列，以及小于枢值的数字序列。
- 用同样的方法，四堆变八堆，八堆变十六堆，很快所有的数字就排好序了。
应用：
- 快速挑选学生尖子：划出几个分数线，根据个人成绩的高低把学生分到十所学校去，第一所学校里的学生成绩最好，第十所最差，很容易地找出学习尖子。
当一个学校的学生水平都比较接近，老师教起来就容易，因此按照成绩对学生作一个初步的划分是有道理的，尤其在资源不足的情况下。
- 高效率的社会管理办法：对每一个人作一些区分。
私营公司行政的层级如同快速排序事先划定的枢值，有了三六九等，公司才有效率可言。 刻意追求所有人一律平等，不作区分，是效率最低的办法。
- 给女朋友送礼物，送她一个体积不大，但能够记住一辈子的礼物（比如爱马仕的丝巾）。不要送她一堆廉价的化妆品，或者没用的小东西，诸如各种智能硬件。
1.3 有效的方法找到数组的中值（面试题）
题目：假如有一个巨大的数组，如何用最有效的方法找到它的中值？
中值的含义：如果有三个数1，2，10，那么中值是2。在很多场合，中值比平均值更有意义。比如考察一个国家个人的收入。 “最有效”的含义：指时间上最快，而非最节省空间。 处理海量的数据，所使用的方法必须是最优化的，否则很轻易地就浪费掉上百倍资源。
糟糕的回答：先排序，再找到中间那个数字的方法。
为了找到一个数而排序，做了太多的无用功。 只要求找到中值，只需把数组整理成大于中值部分和小于中值部分。至于那些大于中值的数字彼此的关系是什么，小于中值的数字相对的次序是什么，不用关心。
有经验的面试者：能否给点提示？
在工作中，请求帮助永远比自己闷头做不出来要好。
思路：让小的数字都到左边，大的数字都到右边。
步骤：从数组中随便找一个数字，让它和数组中每一个数字去比较大小。如果比它小，就放在左边，如果比它大就放在右边。这个过程被称为划分（Partition）。
这种方法复杂度非常低，通常相当于把整个数组扫描了三四遍而已。
- 第一次划分的结果肯定一边多一些，一边少一些。
- 中值一定是在大的一边，因此第二次我们只要在大的一边随机选取一个数字，再做一次划分，看看是否平衡就可以了。
1.4 小结
少做事是提高效率的关键：寻找数组中值的方法和快速排序类似，都是用一个随机的数值对数组进行划分。
寻找数组中值的面试题，可以不断追问下去。
- 证明为什么上述方法的计算复杂度只相当于把数组扫描几遍，最好的情况和最坏的情况会是什么样，什么时候会发生。
- 当数组特别特别大，以至于一台服务器都存不下了，应该怎么处理？
II 排序
概念：让数据有序的存储
分类：选择，冒泡，插入，归并，快速和堆
通常情况下最好的排序算法是"快速排序（Quicksort）"算法，它是基于比较的排序算法，其时间复杂度平均情况下是 O(nlogn)，最坏情况下是 O(n^2)。
最好的计算机算法总是有附加条件，没有绝对的最好。
排序的应用场景：
- 给学生成绩排序，评奖学金或者推研
- 电商对销售根据一些选项排序来改进自己的业务
2.1 选择排序
时间复杂度为O(n^2)。
思路：每次找到未排序部分中的最小值，然后将其放到已排序部分的最后一个位置。
固定一个位置，与其他位置作比较，满足条件交换位置。
具体实现：使用两个嵌套的循环，外层循环用来控制已排序部分的长度，内层循环用来找到未排序部分中的最小值，并将其和已排序部分的最后一个位置进行交换。
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {//控制已排序部分的长度
int minIndex = i;
for (int j = i + 1; j < n; j++) {//找到未排序部分中的最小值，
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
//将最小值和已排序部分的最后一个位置进行交换。
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
使用i表示第一个数据：0~arr.length-2
使用j表示后面部分的数据：i+1~arr.length-1;(j<arr.length,j++;i>j交换)
2.2 冒泡排序
冒泡排序算法的复杂度是O（N平方），插入排序也是O（N平方），属于同一个量级。
思想：从前往后比较相邻的两个元素，如果前一个元素比后一个元素大，则交换这两个元素，这样每一轮比较都会将当前未排序序列中的最大值放到序列末尾。
总是相邻的两个位置作比较，如果满足条件，交换位置。每一次选出一个最好的，如同从水里冒出的气泡。
案例：成绩排序
第一次挑出成绩最高的同学，第二次挑出成绩次高的，如此重复。
Java 实现冒泡排序的代码：
外层循环控制排序轮数，内层循环用于比较相邻元素并交换位置。
public class BubbleSort {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 5, 2, 4};
bubbleSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
2.3 插入排序
基本思想：将待排序的数据分成两部分，已排序部分和未排序部分。每次从未排序部分取出一个元素，将其插入到已排序部分中的合适位置，直到所有元素都被插入到已排序部分中。
每一次要找到合适的位置插入。
案例：成绩排序
先将成绩单上第一个同学的名字和成绩写到旁边一张白纸的中央， 如果第二个同学成绩比他高，就写到第一个同学的上方，如果比他低，就写到下方。看到第三个同学的成绩后，根据他的成绩与前两个同学成绩的比较，插入到相应的位置。比如他的成绩正好在两个同学之间，就在旁边那张排序的纸上，把他的名字插入到前两个人之间。
代码示例：Java 实现插入排序
- i代表需要插入的元素的位置：
1~arr.lenght-1 - j代表前一部分每一个元素的位置：
0~i-1
//该方法接受一个整型数组作为参数，对其进行插入排序。
//在方法中，变量 n 存储数组的长度。
//接着使用一个循环，从数组的第二个元素开始遍历，将其插入到已排序部分中。
//变量 key 存储当前要插入的元素，变量 j 存储已排序部分中最后一个元素的下标。使用一个 while 循环，将已排序部分中大于 key 的元素后移一位，直到找到 key 的插入位置。最后将 key 插入到数组中。
public static void insertionSort(int[] arr) {
int n = arr.length;//存储数组的长度
for (int i = 1; i < n; i++) {//从数组的第二个元素开始遍历，将其插入到已排序部分中
int key = arr[i];// 存储当前要插入的元素
int j = i - 1;//存储已排序部分中最后一个元素的下标
while (j >= 0 && arr[j] > key) {//将已排序部分中大于 key 的元素后移一位，直到找到 key 的插入位置
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;//将 key 插入到数组中
}
}
2.4 归并排序
归并排序利用了少做事情的思想，对冒泡排序进行改进，时间复杂度为 O(nlogn)。
思想：将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列间有序地合并成一个有序序列。
具体实现分为两步：分割序列+合并序列
分割序列：将待排序序列不断分割成两个子序列，直到每个子序列只有一个元素为止。合并序列：将相邻的两个子序列有序地合并成一个有序序列，直到最终序列有序为止。
代码实现归并排序
//mergeSort 方法对序列进行分割，merge 方法对分割后的序列进行合并。其中，temp 数组用于存储合并后的序列，i 和 j 分别表示左右子序列的起始位置，k 表示 temp 数组的当前位置。
public class MergeSort {
//对序列进行分割
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// 分割序列
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并序列
merge(arr, left, mid, right);
}
}
//对分割后的序列进行合并
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];//temp 数组用于存储合并后的序列
int i = left, j = mid + 1, k = 0;//i 和 j 分别表示左右子序列的起始位置，k 表示 temp 数组的当前位置。
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 6, 4};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
2.5 快速排序（常用的排序算法）
基于比较的排序算法，其时间复杂度为平均情况下的 O(nlogn)，最坏情况下的 O(n^2)。
Java 实现快速排序的代码：
sort是快速排序的主要函数，它调用了quickSort函数来实现排序。quickSort函数使用了一个pivot元素来将数组分为两个子数组，并递归对它们进行排序。 在每一次递归中，首先选择一个pivot元素，然后从数组两端开始扫描，找到两个元素，一个在左边，一个在右边，它们本来应该在pivot的左边和右边，但由于位置不正确，需要交换它们。一直重复这个过程，直到最后子数组只有一个元素为止。
public class QuickSort {
public static void sort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[(left + right) / 2];//用了 `pivot` 元素来将数组分为两个子数组，并递归对它们进行排序
int i = left;
int j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
swap(arr, i, j);
i++;
j--;
}
}
quickSort(arr, left, j);
quickSort(arr, i, right);
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2.6 Java 堆排序
思想：基于二叉堆的排序算法，它利用了堆的性质来进行排序。
堆排序分为两个主要步骤：建堆和排序。
- 建堆的过程是将待排序的数组构建成一个二叉堆，通常使用最大堆（大顶堆）来进行排序。
- 排序的过程是不断地从堆顶取出最大值（根节点），将其与堆中最后一个元素交换，然后重新调整堆，使得剩余元素仍满足堆的性质。
//定义了一个 heapSort 方法，它接受一个整数数组作为参数，然后对数组进行堆排序。
//在排序过程中，首先通过 heapify 方法建立一个最大堆。
//然后，从数组末尾开始，将最大值（根节点）与当前位置的元素交换，接着调整堆，使得交换后的剩余元素仍满足堆的性质。
//最终，通过不断重复这个过程，得到一个有序的数组。
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// 建堆（构造最大堆）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 排序
for (int i = n - 1; i > 0; i--) {
// 将当前最大值（根节点）与最后一个元素交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整堆，使剩余元素仍满足最大堆性质
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值为当前节点
int left = 2 * i + 1; // 左子节点索引
int right = 2 * i + 2; // 右子节点索引
// 如果左子节点大于最大值节点，更新最大值节点
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点大于最大值节点，更新最大值节点
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值节点不是当前节点，交换节点并递归调整堆
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {3, 1, 5, 2, 4};
heapSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
腾讯云开发者
