专栏首页阿Q说代码冒泡排序、选择排序和二分查找

冒泡排序、选择排序和二分查找

最近有小伙伴后台留言表示要详细了解一下冒泡排序和选择排序的原理,so阿Q便在这里做一个简单的介绍,希望对小伙伴加深冒泡排序以及选择排序的理解有点小帮助吧。

冒泡排序算法的原理如下:
  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码如下:

public static void bubbleSort(int[] arr) {
    //{24, 69, 57, 13, 80};
    for (int i = 0; i < arr.length - 1; i++) {//外循环只需要比较arr.length-1次就可以了
        for (int j = 0; j < arr.length - 1 - i; j++) {  //-1为了防止索引越界,-i为了提高效率,因为每一次排序最后边排好的已经不用再比较了。
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j+1] = temp;
            }
        }
    }
}
选择排序算法的原理如下:
  1. 从0索引开始,依次和后面元素比较,如果0索引的元素小则不变,反之,交换他们的值。第一次完毕,最小值出现在了0索引处;
  2. 从1索引开始,重复1步骤,第二小的值出现在了1索引处;
  3. 针对所有的元素重复以上的步骤,除了最后一个。

代码如下:

public static void selectSort(int[] arr) {
    //{24, 69, 80, 57, 13};
    for (int i = 0; i < arr.length - 1; i++) {//只需要比较arr.length-1次,i控制第几个索引处的值
        for (int j = i + 1; j < arr.length; j++) {//j控制后边的元素值
            if(arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}
二分法查找:

前提是数组必须是有序的。先设要查找的值为x,中间索引为y,总长度为length。

  1. 判断数组y索引处的值是否与x相等,若相等则得到该索引值,若不相等则进行判断:如果中间值大于x,则去索引值为0—[y-1]区间查找;若中间值小于x,则去[y+1]—[length-1]区间查找,
  2. 去重新确定的区间内重复步骤1操作;
  3. 如果查到最后发现最小索引大于了最大索引,就没有查找的可能性了即查找失败。

代码如下:

//int[] arr = {11,22,33,44,55,66,77};
public static int getIndex(int[] arr, int value) {
    int min = 0;
    int max = arr.length - 1;
    int mid = (min + max) / 2;

    while(arr[mid] != value) {      //当中间值不等于要找的值,就开始循环查找
        if(arr[mid] < value) {      //当中间值小于了要找的值
            min = mid + 1;      //最小的索引改变
        }else if (arr[mid] > value){    //当中间值大于了要找的值
            max = mid - 1;      //最大的索引改变
        }
        mid = (min + max) / 2;      //无论最大还是最小改变,中间索引都会随之改变

        if(min > max) {        //如果最小索引大于了最大索引,就没有查找的可能性了
           return -1;       //返回-1
        }
     }
     return mid;
}

这三块知识就梳理到这边了,想了解更多学习知识,请关注微信公众号“阿Q说”,获取更多学习资料吧!你也可以后台留言说出你的疑惑,阿Q将会在后期的文章中为你解答。每天学习一点点,每天进步一点点。

本文分享自微信公众号 - 阿Q说代码(AQ_Shuo),作者:阿Q

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java基础【冒泡、选择排序、二分查找】

    从第一个开始 与他后面的每个数字进行比较,如果遇见比他小的 这个两个数字进行交换位置,

    梅花
  • 冒泡排序和选择排序

    lop
  • 冒泡排序、二分查找

    唐怀瑟
  • 选择排序,冒泡排序

    我不是费圆
  • 冒泡和选择排序

    #include <stdio.h> #include <stdlib.h> #include <string.h> //冒泡排序 void bubbleSor...

    ternturing
  • Java:冒泡排序 | 二分查找

    32>8? ture: 将32和8调换位置 8, 32*, 128, 2, 64;

    Java编程指南
  • C++ 插入排序,冒泡排序和选择排序

    用户6021899
  • 冒泡排序、选择排序、插入排序

    冒泡排序:每次遍历后选出最大的元素,每当选出一个下次遍历就排除之前已选的最大元素,因为每次遍历都能定位一个最大元素。

    用户6055494
  • 基于python的冒泡排序和选择排序

    装饰器是python的高级用法,初学者需要单独学习1天才能理解并且熟练运用。 读者如果不理解本节内容,不影响后续内容的理解。 此装饰器只是计算函数运行花费的...

    潇洒坤
  • 冒泡排序,选择排序,插入排序算法

    冒泡排序 思路:二二交换,可以让最大的数沉底,在length-1次,就有序了 package day20180315; public class Maopao...

    热心的社会主义接班人
  • 排序算法之选择排序与冒泡排序

    选择排序与冒泡排序都是比较简单的办法,非常容易理解,但时间复杂度也都是O(N2)。

    dejavu1zz
  • 排序算法之冒泡、插入、快排和选择排序

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    海仔
  • 数据结构|冒泡排序与选择排序

    排序算法可以说是算法中使用的比较频繁的,冒泡排序是一种简单的排序,它通过遍历,一次比较两个元素,如果排序错误就交换位置,遍历需要重复进行直到不再需要交换,才算排...

    算法与编程之美
  • 冒泡排序+选择排序+插入排序+图与代码

  • C# 冒泡排序法、插入排序法、选择排序法

    数据 11, 35, 39, 30, 7, 36, 22, 13, 1, 38, 26, 18, 12, 5, 45, 32, 6, 21, 42, 23

    痴者工良
  • java学习之数组元素排序,冒泡排序和选择排序

    吾爱乐享
  • Java中选择排序,冒泡排序等排序方法示例

    用户1696846
  • [算法] 数组排序 - 冒泡排序法与直接选择排序法

    两种算法都很基础,但是思考的方向还是有着些许差异的。 另外想要更快的去解决排序问题的话,可以下功夫去研究一下库里面的 qsort函数,也非常的实用!

    泰坦HW
  • 详解排序算法--插入排序和冒泡排序插入排序和冒泡排序分析

    冒泡排序(英语:Bubble Sort,台湾另外一种译名为:泡沫排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把...

    desperate633

扫码关注云+社区

领取腾讯云代金券