一、排序介绍
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;
}
}
}
}
运行结果:
标签:arr,Java,int,冒泡排序,数组,排序,public From: https://blog.csdn.net/stewie6/article/details/139547483