• Java——数组排序和查找


     一、排序介绍

    1、排序的概念

    排序是将多个数据按照指定的顺序进行排列的过程。

    2、排序的种类

    排序可以分为两大类:内部排序和外部排序

    3、内部排序和外部排序

    1)内部排序

    内部排序是指数据在内存中进行排序,适用于数据量较小的情况。数据可以完全装入内存。常见的内部排序算法包括:

    • 交换排序法:如冒泡排序、快速排序等。
    • 选择排序法:如选择排序、堆排序等。
    • 插入排序法:如直接插入排序、希尔排序等。

    2)外部排序

    外部排序是指数据量大到无法完全装入内存,需要借助外部存储器(如磁盘)进行排序。常见的外部排序算法包括:

    • 合并排序法:如多路归并排序。
    • 分配排序法:如基数排序。

    二、冒泡排序

    冒泡排序(Bubble Sort)是一种简单的排序算法。它的工作原理是重复地遍历要排序的序列,一次比较两个元素,如果它们的顺序错误则交换它们的位置。这个过程会将每次遍历中最大的元素“冒泡”到序列的末尾,类似于气泡在水中上升。

    1、冒泡排序图解

    这里使用 5 个元素的数组作为例子:

    第一轮:

    第二轮:

    第三轮:

    第四轮:

    我们可以发现,对于元素个数为 n 的数组,使用冒泡排序需要 n - 1 轮,第一轮需要 n - 1 步,后面的每一轮的步骤数依次递减一。

    2、冒泡排序代码实现

    上面我们对冒泡排序的具体原理进行了详细的分析,下面我们将使用代码对数组的冒泡排序进行实现。

    1. import java.util.Arrays;
    2. public class Test {
    3. public static void main(String[] args) {
    4. int[] arr = {5, 4, 3, 2, 1};
    5. for(int i = 0; i < arr.length - 1; i++) {
    6. for(int j = 0; j < arr.length - 1 - i; j++) {
    7. if(arr[j] > arr[j + 1]) {
    8. int temp = arr[j];
    9. arr[j] = arr[j + 1];
    10. arr[j + 1] = temp;
    11. }
    12. }
    13. }
    14. System.out.println("排序后的数组为 " + Arrays.toString(arr));
    15. }
    16. }

    运行结果:

    我们也可以详细看看每一轮执行后排序的结果:

    1. import java.util.Arrays;
    2. public class Test {
    3. public static void main(String[] args) {
    4. int[] arr = {5, 4, 3, 2, 1};
    5. for(int i = 0; i < arr.length - 1; i++) {
    6. for(int j = 0; j < arr.length - 1 - i; j++) {
    7. if(arr[j] > arr[j + 1]) {
    8. int temp = arr[j];
    9. arr[j] = arr[j + 1];
    10. arr[j + 1] = temp;
    11. }
    12. }
    13. System.out.println("\n第一轮\n" + Arrays.toString(arr));
    14. }
    15. System.out.println("\n最终排序好的的数组为\n" + Arrays.toString(arr));
    16. }
    17. }

    运行结果:

    可以发现与我们上面分析的一致。

    3、冒泡排序优化

    可以使用一个状态变量,如果某一轮进行了交换,则代表未排序的部分是无序的;如果某一轮未进行交换,就代表没有排序的部分已经是有序的了,就不用排序了,则可以退出循环。

    1. import java.util.Arrays;
    2. public class Test {
    3. public static void main(String[] args) {
    4. int[] arr = {1, 2, 4, 3, 5};
    5. boolean isSwap = false;
    6. for(int i = 0; i < arr.length - 1; i++) {
    7. isSwap = false;
    8. for(int j = 0; j < arr.length - 1 - i; j++) {
    9. if(arr[j] > arr[j + 1]) {
    10. int temp = arr[j];
    11. arr[j] = arr[j + 1];
    12. arr[j + 1] = temp;
    13. isSwap = true;
    14. }
    15. }
    16. if(!isSwap) {
    17. break;
    18. }
    19. }
    20. System.out.println("最终排序好的的数组为\n" + Arrays.toString(arr));
    21. }
    22. }

    这里使用一个 boolean 类型变量,开始初始化为 false,如果进行交换了,则将其赋值为 true,再一轮的最后进行判断是否进行过交换,如果没有进行交换,也就是这个状态变量为 false 则退出外层循环,排序完成。

    这种冒泡排序再进行一些部分有序的数组的排序任务中,会比为优化的冒泡排序性能更高些。

    上面的代码运行结果:

    三、数组元素查找

    1、顺序查找

    顺序查找是一种简单的查找算法,它从数组的第一个元素开始,逐个比较每个元素,直到找到目标元素或遍历完整个数组。顺序查找不需要数组是有序的。

    1. public class Test {
    2. public static void main(String[] args) {
    3. int[] arr = {1, 2, 3, 4, 5};
    4. int searchNum = 3;
    5. for(int i = 0; i < arr.length; i++) {
    6. if(arr[i] == searchNum) {
    7. System.out.println("arr[" + i + "] = " + searchNum);
    8. break;
    9. }
    10. }
    11. }
    12. }

    运行结果:

  • 相关阅读:
    计算机的基础知识
    多线程基础原理篇
    服务器数据恢复—VMware虚拟化下误操作导致服务器崩溃的数据恢复案例
    如何使用GPT-4o函数调用构建一个实时应用程序?
    C++ YAML使用
    被问到可重入锁条件队列,看这一篇就够了!|原创
    6-pytorch - 网络的保存和提取
    ​LeetCode解法汇总2490. 回环句
    如何使用前端表格控件实现多数据源整合?
    messageBox的入门学习
  • 原文地址:https://blog.csdn.net/stewie6/article/details/139547483