您现在的位置是:首页 > 正文

排序

2024-04-01 04:29:26阅读 2
    //插入排序
    public static void insertionSort(int[] arr) {
        for (int j = 1; j < arr.length; j++) {
            int key = arr[j];
            int i = j - 1;
            while (i >= 0 && arr[i] > key) {
                arr[i + 1] = arr[i];
                i = i - 1;
            }
            arr[i + 1] = key;
        }
    }

    //选择排序
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIdx] > arr[j]) {
                    minIdx = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }

    //归并排序
    public static void mergeSort(int[] arr, int low, int high) {
        if ((low + 1) > high) {
            return;
        }
        int mid = (low + high) >> 1;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        int n1 = mid - low + 1;
        int n2 = high - mid;

        int[] left = new int[n1 + 1];
        int[] right = new int[n2 + 1];

        for(int i = 0; i < n1; i++) {
            left[i] = arr[low + i];
        }
        for (int i = 0; i < n2; i++) {
            right[i] = arr[mid + 1 + i];
        }
        left[n1] = Integer.MAX_VALUE;
        right[n2] = Integer.MAX_VALUE;

        int i = 0;
        int j = 0;
        int k = low;
        while (k <= high) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
    }

    //快速排序
    public static void quickSort(int arr[], int low, int high) {
        if (low >= high) {
            return;
        }
        int temp = arr[low];
        int i = low;
        int j = high;
        while (i < j) {
            while (j > i && arr[j] >= temp) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= temp) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;

        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }
    //堆排序
    public static void heapSort(int[] arr) {
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, i, 0);
            maxHeapify(arr, i, 0);
        }
    }


    //建堆
    public static void buildMaxHeap(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            maxHeapify(arr, arr.length, i);
        }
    }

    //维护堆的性质
    public static void maxHeapify(int[] arr, int len, int i) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int largest = i;
        if (l < len && arr[l] > arr[largest]) {
            largest = l;
        }
        if (r < len && arr[r] > arr[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(arr, i, largest);
            maxHeapify(arr, len, largest);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

  

转载于:https://www.cnblogs.com/lmxsj/p/11544149.html

网站文章

  • Linux-编译链接过程及命令

    Linux-编译链接过程及命令

    编译链接过程 【1】预处理 源代码被预编译为一个 .i文件 在Linux下,对于一个已经编写好的main.c源程序,代码 gcc -E mainn.c -o main.i 完成对程序的预处理。 或者:cpp main.c &gt; main.i 预处理主要工作: 1.宏替换,展开所有宏定义 2.处理所有预编译指令,将包含的文件插入到预编译指令处 3.删除所有注释 4.添加行号...

    2024-04-01 04:28:46
  • C语言详细学生成绩管理系统

    C语言详细学生成绩管理系统

    C语言 学生成绩管理系统 简述:该学生管理系统数据结构采用结构体 1、系统需求分析 1.1系统介绍 本学生管理系统是为教师人员提供管理班级成绩的工具,该系统可以实现的对学生的成绩进行增、删、改、查、信...

    2024-04-01 04:28:40
  • 【错误记录】TabLayout 升级支持库版本后报错 ( support:design 支持库升级到 28.0.0 后源码发生变更 )

    【错误记录】TabLayout 升级支持库版本后报错 ( support:design 支持库升级到 28.0.0 后源码发生变更 )

    Caused by: java.lang.NullPointerException: Attempt to invoke virtual method &#39;void java.lang.reflect.Field.setAccessible(boolean)&#39; on a null object reference

    2024-04-01 04:28:33
  • 虚拟机NAT 有线被拔出 eth0卡消失

    宿主机VMware DHCP 和VMware NAT 服务没开

    2024-04-01 04:27:54
  • contains函数

    CONTAINS 函数CONTAINS 是字符串处理函数,它能够处理所有字符串数据类型(BIT、BLOB 和 CHARACTER),并返回布尔值以指示一个字符串是否包含在另一个字符串中。示例: St...

    2024-04-01 04:27:47
  • opc怎么在计算机上测试,Matrikon OPC UA Tunneller使用教程:如何执行回送测试?

    opc怎么在计算机上测试,Matrikon OPC UA Tunneller使用教程:如何执行回送测试?

    Matrikon OPC UA Tunneller使用教程:如何执行回送测试?Matrikon OPC UA Tunneller在未来可以帮助您对基础设施的控制,达到提高 OPC UA的利用率的预期。...

    2024-04-01 04:27:39
  • 一篇文章告诉你如何入门网络安全行业

    一篇文章告诉你如何入门网络安全行业

    Hello!大家好!欢迎来到网络安全情报局,最近收到很多小伙伴的私信,对黑客技术很感兴趣,但是不知道如何着手学习,今天就为大家带来详细的解答。如果觉得对你有用记得点赞分享哦!​话不多说,直接进入正文0...

    2024-04-01 04:26:57
  • java 乱码 spring filter_解决SpringMVC的乱码问题:CharacterEncodingFilter

    在使用 SpringMVC 框架的过程中,如果前台有包含中文的请求,或者后台有包含中文的响应,有可能会出现乱码的情况。在以前的 Servlet 中,我们使用 request.setCharacterE...

    2024-04-01 04:26:50
  • ubuntu18.04安装Anaconda3_2022通用

    ubuntu18.04安装Anaconda3_2022通用

    Anaconda的安装

    2024-04-01 04:26:43
  • RabbitMQ 消息队列之 Exchange Types

    写在前面RabbitMQ遵循AMQP 0-9-1协议 AMQP 0-9-1协议简介消息发布到交换站,这通常被比作邮局或邮箱。然后交换器使用称为绑定的规则将消息副本分发到队列。然后,AMQP代理将消息传递给订阅队列的消费者,或者根据需要从队列中获取消息。发布消息时,发布者可以指定各种消息属性(消息元数据)。这些元数据中的一些可能由代理使用,但是,其他部分对代理完全不透明,仅供接收消息的应用...

    2024-04-01 04:26:36