一、排序介绍
1、排序的概念
排序是将多个数据按照指定的顺序进行排列的过程。
2、排序的种类
排序可以分为两大类：内部排序和外部排序。
3、内部排序和外部排序
1）内部排序
内部排序是指数据在内存中进行排序，适用于数据量较小的情况。数据可以完全装入内存。常见的内部排序算法包括：
- 交换排序法：如冒泡排序、快速排序等。
- 选择排序法：如选择排序、堆排序等。
- 插入排序法：如直接插入排序、希尔排序等。
2）外部排序
外部排序是指数据量大到无法完全装入内存，需要借助外部存储器（如磁盘）进行排序。常见的外部排序算法包括：
- 合并排序法：如多路归并排序。
- 分配排序法：如基数排序。
二、冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法。它的工作原理是重复地遍历要排序的序列，一次比较两个元素，如果它们的顺序错误则交换它们的位置。这个过程会将每次遍历中最大的元素“冒泡”到序列的末尾，类似于气泡在水中上升。
1、冒泡排序图解
这里使用 5 个元素的数组作为例子：
第一轮：
第二轮：
第三轮：
第四轮：
我们可以发现，对于元素个数为 n 的数组，使用冒泡排序需要 n - 1 轮，第一轮需要 n - 1 步，后面的每一轮的步骤数依次递减一。
2、冒泡排序代码实现
上面我们对冒泡排序的具体原理进行了详细的分析，下面我们将使用代码对数组的冒泡排序进行实现。
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println("排序后的数组为 " + Arrays.toString(arr));
}
}运行结果：
我们也可以详细看看每一轮执行后排序的结果：
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("\n第一轮\n" + Arrays.toString(arr));
}
System.out.println("\n最终排序好的的数组为\n" + Arrays.toString(arr));
}
}运行结果：
可以发现与我们上面分析的一致。
3、冒泡排序优化
可以使用一个状态变量，如果某一轮进行了交换，则代表未排序的部分是无序的；如果某一轮未进行交换，就代表没有排序的部分已经是有序的了，就不用排序了，则可以退出循环。
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {1, 2, 4, 3, 5};
boolean isSwap = false;
for(int i = 0; i < arr.length - 1; i++) {
isSwap = false;
for(int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSwap = true;
}
}
if(!isSwap) {
break;
}
}
System.out.println("最终排序好的的数组为\n" + Arrays.toString(arr));
}
}这里使用一个 boolean 类型变量，开始初始化为 false，如果进行交换了，则将其赋值为 true，再一轮的最后进行判断是否进行过交换，如果没有进行交换，也就是这个状态变量为 false 则退出外层循环，排序完成。
这种冒泡排序再进行一些部分有序的数组的排序任务中，会比为优化的冒泡排序性能更高些。
上面的代码运行结果：
三、数组元素查找
1、顺序查找
顺序查找是一种简单的查找算法，它从数组的第一个元素开始，逐个比较每个元素，直到找到目标元素或遍历完整个数组。顺序查找不需要数组是有序的。
public class Test {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int searchNum = 3;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == searchNum) {
System.out.println("arr[" + i + "] = " + searchNum);
break;
}
}
}
}运行结果：
