草庐IT

Java数组算法(二分、冒泡、选择、快排)

鐡道 2023-04-17 原文

查找

二分查找

时间复杂度：O (logN)

说明：取数组中间的值和查找值进行比较、如果 中间的值大于要查找的值、则高位索引往中间索引-1、小于则是低位索引往上提、即中间索引+1、一直循环直至找到值、最后没有找到则返回-1

/**
  * 二分查找法
  * @return 返回查找的索引、没有则返回-1
  */
public static int binarySearch(int[] arrs, int key) {
    // 定义了低位索引和高位索引
    int lowIndex = 0, highIndex = arrs.length - 1;
    // 一直循环、直至低位索引和高位索引值一致
    while (lowIndex <= highIndex) {
        // 取中间索引、即低位索引+高位索引的和除以2、正数右移n位相当于除以2的n次方
        int midIndex = (lowIndex + highIndex) >>> 1,
        midValue = arrs[midIndex];
        if (midValue > key)
            highIndex = midIndex - 1;
        else if (midValue < key)
            lowIndex = midIndex + 1;
        else
            return midIndex;
    }
    return -1;
}

排序

冒泡排序

时间复杂度：O (n)

/**
  * 冒泡排序
  */
public static void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                arr[j] = arr[j] ^ arr[j + 1];
                arr[j + 1] = arr[j] ^ arr[j + 1];
                arr[j] = arr[j] ^ arr[j + 1];
            }
        }
    }
}

选择排序

时间复杂度：O（n²）

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

/**
  * 选择排序
  */
public static void sort(int[] arr) {
    // 总共要经过 N-1 轮比较
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;

        // 每轮需要比较的次数 N-i
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                // 记录目前能找到的最小值元素的下标
                min = j;
            }
        }

        // 将找到的最小值和i位置所在的值进行交换
        if (i != min) {
            arr[i] = arr[i] ^ arr[min];
            arr[min] = arr[i] ^ arr[min];
            arr[i] = arr[i] ^ arr[min];
        }
    }
}

快速排序

时间复杂度：O(nlogn) 速度最快

/**
  * 快速排序
  * @param src 数组
  * @param begin 起始索引
  * @param end 尾部索引
  */
public static void sort(int[] src, int begin, int end) {
    if (begin < end) {
        int key = src[begin];
        int i = begin;
        int j = end;
        while (i < j) {
            while (i < j && src[j] > key) {
                j--;
            }
            if (i < j) {
                src[i] = src[j];
                i++;
            }
            while (i < j && src[i] < key) {
                i++;
            }
            if (i < j) {
                src[j] = src[i];
                j--;
            }
        }
        src[i] = key;
        sort(src, begin, i - 1);
        sort(src, i + 1, end);
    }
}
二分Javaarrintsrc

有关Java数组算法(二分、冒泡、选择、快排)的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  3. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  4. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  5. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  6. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  7. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  8. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

    我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？ 最佳答案 我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作

  9. ruby - 如何在 Grape 中定义哈希数组？ - 2

    我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

  10. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

随机推荐