二分查找、分块查找、冒泡排序、选择排序、插入排序、快速排序 ...

吴旭华 · 5 天前

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

x

二分查找/折半查找

前提条件：数组中的数据必须是有序的
核心逻辑：每次排除一半的查找范围
优点：进步查找效率
代码
1. public static int binarySearch(int[] arr, int num) {
2. int start = 0;
3. int end = arr.length - 1;
4. while (start <= end) {
5. int mid = (start + end) / 2;
6. if (num == arr[mid]) {
7. // 找到
8. return mid;
9. } else if (num > arr[mid]) {
10. // num在mid索引的右边
11. start = mid + 1;
12. } else {
13. // num在mid索引的左边
14. end = mid - 1;
15. }
16. }
17. return -1;
18. }
复制代码

分块查找

分块的原则
- 前一块中的最大数据，小于后一块中全部的数据（块内无序，块间有序）
- 块数数量一样寻常等于数字个数开根号。好比：16个数字一样寻常分为4块左右
- 核心思路：先确定要查找的元素在哪一块，然后在块内挨个查找
代码
1. package com.gen.test;
3. public class BlockSearchDemo {
4. public static void main(String[] args) {
5. int[] arr = {16, 5, 9, 12, 21, 18,
6. 32, 23, 37, 26, 45, 34,
7. 50, 48, 61, 52, 73, 66};
9. // 创建3个对象
10. Block block1 = new Block(21, 0, 5);
11. Block block2 = new Block(45, 6, 11);
12. Block block3 = new Block(73, 12, 17);
13. // 定义数组管理3个块的对象（索引表）
14. Block[] blockArr = {block1, block2, block3};
15. // 获取索引
16. int index = getIndex(blockArr, arr, 66);
17. System.out.println(index);
18. }
20. /**
21. * 获取索引
22. *
23. * @param blockArr 索引表
24. * @param arr 数组
25. * @param num 要查找的数字
26. * @return 返回数字在arr中的索引，-1表示不存在
27. */
28. private static int getIndex(Block[] blockArr, int[] arr, int num) {
29. // 1.先确定在哪一个块中
30. int indexBlock = findIndexBlock(blockArr, num);
31. // num比所有块的最大值要大，不存在数组中
32. if (indexBlock == -1) {
33. return -1;
34. }
36. // 2.在块中查找num
37. int startIndex = blockArr[indexBlock].getStartIndex();
38. int endIndex = blockArr[indexBlock].getEndIndex();
39. for (int i = startIndex; i <= endIndex; i++) {
40. if (num == arr[i]) {
41. return i;
42. }
43. }
44. return -1;
45. }
47. /**
48. * 查找num在哪一个块中
49. *
50. * @param blockArr
51. * @param num
52. * @return 返回块索引，-1表示不存在
53. */
54. private static int findIndexBlock(Block[] blockArr, int num) {
55. for (int i = 0; i < blockArr.length; i++) {
56. if (num <= blockArr[i].getMax()) {
57. return i;
58. }
59. }
60. return -1;
61. }
63. }
65. class Block {
67. // 最大值
68. private int max;
70. // 起始索引
71. private int startIndex;
73. // 结束索引
74. private int endIndex;
76. public Block() {
77. }
79. public Block(int max, int startIndex, int endIndex) {
80. this.max = max;
81. this.startIndex = startIndex;
82. this.endIndex = endIndex;
83. }
85. public int getMax() {
86. return max;
87. }
89. public void setMax(int max) {
90. this.max = max;
91. }
93. public int getStartIndex() {
94. return startIndex;
95. }
97. public void setStartIndex(int startIndex) {
98. this.startIndex = startIndex;
99. }
101. public int getEndIndex() {
102. return endIndex;
103. }
105. public void setEndIndex(int endIndex) {
106. this.endIndex = endIndex;
107. }
108. }
复制代码

冒泡排序

排序逻辑
- 相邻的元素两两比较，大的放右边，小的放左边
- 第一轮循环结束，最大值已经找到，在数组的最右边
- 第二轮循环只要在剩余的元素找最大值就可以了
- 第二轮循环结束，次大值已经确定，第三轮循环继承在剩余数据中循环
核心
- 相邻的元素两两比较，大的放右边，小的放左边
- 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，反面以此类推
- 如果数组中有n个数据，总共我们只要实行n-1轮的代码即可
代码
1. public static void bubbleSort(int[] arr) {
2. for (int i = 0; i < arr.length - 1; i++) {
3. for (int j = 0; j < arr.length - 1 - i; j++) {
4. if (arr[j] > arr[j + 1]) {
5. // 左边数据比右边大，交换位置
6. int temp = arr[j];
7. arr[j] = arr[j + 1];
8. arr[j + 1] = temp;
9. }
10. }
11. }
12. }
复制代码

选择排序

从0索引开始，拿着每一个索引上的元素跟反面的元素依次比较，小的放前面，大的放反面，以此类推
代码
1. public static void selectSort(int[] arr) {
2. for (int i = 0; i < arr.length - 1; i++) {
3. for (int j = i + 1; j < arr.length; j++) {
4. if (arr[i] > arr[j]) {
5. // 左边数据比右边大，交换位置
6. int temp = arr[i];
7. arr[i] = arr[j];
8. arr[j] = temp;
9. }
10. }
11. }
12. }
复制代码

插入排序

将0索引的元素到N索引的元素看作是有序的，把N+1索引的元素到末了一个当成是无序的
遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如碰到雷同数据，插在反面
N的范围：0~最大索引
1. package com.gen.test;
3. public class InsertSortDemo {
4. public static void main(String[] args) {
5. int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
7. // 1.找到无序索引起始位置
8. int startIndex = -1;
9. for (int i = 0; i < arr.length - 1; i++) {
10. if (arr[i] > arr[i + 1]) {
11. startIndex = i + 1;
12. break;
13. }
14. }
16. // 2.遍历无序元素，依次插入到有序元素中
17. for (int i = startIndex; i < arr.length; i++) {
18. // 记录当前要插入数据的索引
19. int j = i;
20. while (j > 0 && arr[j] < arr[j - 1]) {
21. // 交换位置
22. int temp = arr[j];
23. arr[j] = arr[j - 1];
24. arr[j - 1] = temp;
25. j--;
26. }
27. }
28. }
29. }
复制代码

快速排序

第一轮：把0索引的数字作为基准数，确定基准数在数组中精确的位置。比基准数小的全部在左边，比基准数大的全部在右边

/**
* 快速排序
*
* @param arr 要排序的数组
* @param i 开始索引
* @param j 结束索引
*/
public static void quickSort(int[] arr, int i, int j) {
// 递归出口
if (i >= j) {
return;
}
int start = i;
int end = j;
// 记录基准数
int baseNum = arr[i];
while (start != end) {
// 从后往前找，找到比基准数小的元素
while (true) {
if (start >= end || arr[end] < baseNum) {
break;
}
end--;
}
// 从前往后找，找到比基准数大的元素
while (true) {
if (start >= end || arr[start] > baseNum) {
break;
}
start++;
}
// 把start和end元素进行交换
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
// 基准数归位
arr[i] = arr[start];
arr[start] = baseNum;
// 递归排序左边的数
quickSort(arr, i, start - 1);
// 递归排序右边的数
quickSort(arr, start + 1, j);
}

复制代码

排序总结

冒泡排序
- 相邻的元素两两比较，小的放前面，大的放反面
选择排序
- 从0索引开始，拿着每一个索引上的元素跟反面的元素依次比较，小的放前面，大的放反面，以此类推
插入排序
- 将数组分为有序和无序两组，遍历无序数据，将元素插入有序序列中即可
快速排序
- 将排序范围中的第一个数字作为基准数，再定义两个变量start、end
- start从前去后找比基准数大的，end从后往前找比基准数小的
- 找到之后交换start和end指向的元素，并循环这一过程，直到start和end处于同一个位置，该位置是基准数在数组中应存入的位置，再让基准数归位
- 归位后的效果：基准数左边的，比基准数小，基准数右边的，比基准数大

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

二分查找、分块查找、冒泡排序、选择排序、插入排序、快速排序 ...

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

0 个回复

快速回复

楼主热帖

标签云

浏览过的版块