用Java(C语言也可以看)实现冒泡排序和折半查找(详细过程图)+逆序数组

简介: 用Java(C语言也可以看)实现冒泡排序和折半查找(详细过程图)+逆序数组



一、冒泡排序

冒泡排序是众多排序的一种,无论在C语言或者Java中都很常见,后续在数据结构中也会用到

1.冒泡排序介绍

(1)冒泡排序思想

  • 为两两排序,每次的排序后,最大(或最小的)就会升起到最后
  • 每完成一轮排序,需要比较的数就少一个

(2)冒泡排序场景

  • 多用于对数组内容的排序

2.排序的思路

(1)完成排序需要的内容

  • 有数组
  • 需要求数组长度

(2)排序的过程解析

  • 我们将下面数组排序成升序
int[] arr = {10,9,8,7,6,5,4,3,2,1};
  • 第一趟冒泡排序:10个数需要比较9次,成功把一个数字排好序

  • 第二趟冒泡排序:待排序的数字有9个,所以需要比较的次数是8次

后续的排序趟数是类似的,接下来我们总结一下规律

  • 由上图可知:10个数字一共需要比较的趟数是10-1次,也就是(arr.length-1)
  • 第一趟排序需要比较的次数为9,第二次是8;与趟数有关系,于是得出下面的代码
int i =0;
 for (i = 0; i < arr.length-1; i++) {
     for (int j = 0; j < arr.length-1-i; j++) {
        //可自己设置条件条件
         if(arr[j]>arr[j+1]) {
            //完成两个数字的交换
             int tmp = arr[j+1];
             arr[j+1] = arr[j];
             arr[j] = tmp;
          }
      }
  }
  • 升序的条件是第一个数大于第二个数就要交换;如果是排逆序则是第一个数小于第二个数则需要交换

3.完整代码

import java.util.Arrays;
public class Sort{
public static void main(String[] args) {
        //冒泡排序
        int[] arr = {10,9,8,7,6,5,4,3,2,1};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void bubbleSort(int[] arr) {
        //升序
        int i =0;
        for (i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]) {
                  int tmp = arr[j+1];
                  arr[j+1] = arr[j];
                  arr[j] = tmp;
                }
            }
        }
    }
}

二、折半查找

1.折半查找介绍

(1)折半查找,又称二分查找。

(2)二分查找每次都是从中间位置开始查找,因此称为折半查找(二分查找)

(3)可以进行二分查找的条件

  • 数组内的数据必须是有序的
  • 若是无序的,可以先将其排成有序

2.查找的思路

(1)方法的参数写法

  • 我们规定一下:找到了就返回它的下标位置,否则返回-1
  • 需要将数组和需要查找的数据传给下面的方法
public static int binarySearch(int[] arr,int k) {
       
    }

(2)查找的内部细节

  • 定位下标:定好两头位置,便于找到中间位置

public static int binarySearch(int[] arr,int k) {
        int left = 0;
        int right = arr.length-1;
    }
  • 中间数字表示:
int mid = (left+right)/2;

(3)二分查找的过程解析

  • 先看代码
public static int binarySearch(int[] arr,int k) {
        int left = 0;
        int right = arr.length-1;
        while(left <= right) {
            //从中间位置开始找
            int mid = (left+right)/2;
            if(k < arr[mid]) {//k在左边
                right=mid-1;
            } else if(k > arr[mid]) {
                //在右边
                left=mid+1;
            } else {
                return mid;
            }
        }
        return -1;
    }
  • 查找过程图解 :第一次查找

  • 第二次查找:查找后,right指向10,left和mid都指向8

  • 第三、四次查找:找到了就返回mid位置的下标

3.完整代码

public static void main(String[] args) {
        //1.折半查找,要求数组内容为有序.找到了返回下标
        int[] arr1 = {2,5,7,8,10,11,15,17,20,22};
        int ret = binarySearch(arr1,10);
        System.out.println(ret);
        //2.当数组无序时,使用Array.sort排序后折半查找
        int[] arr2 = {9,8,7,6,5,4,3,2,1,0};
        Arrays.sort(arr2);
        System.out.println(Arrays.toString(arr2));
        int cur = binarySearch(arr2,11);
        System.out.println(cur);
    }
    public static int binarySearch(int[] arr,int k) {
        int left = 0;
        int right = arr.length-1;
        while(left <= right) {
            //从中间位置开始找
            int mid = (left+right)/2;
            if(k < arr[mid]) {//k在左边
                right=mid-1;
            } else if(k > arr[mid]) {
                //在右边
                left=mid+1;
            } else {
                return mid;
            }
        }
        return -1;
    }

三、逆序数组

1.逆序思路

(1)要求将数组内容逆序,不是逆序打印

int[] arr = {10,9,8,7,6,5,4,3,2,1,0};

(2)设置头尾位置

public static void reverse(int[] arr) {
        int left = 0;//头位置
        int right =arr.length-1;//尾位置 
    }

这样是为了从两头开始交换数据

(3)循环交换数据

while(left < right) {//相等的时候就不需要逆序了
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }

内部代码其实就是实现两个数的交换;当left==right的时候,就是只剩下一个数据没有完成交换了,其实也就不需要再交换了(非要交换也行)

2..完整代码

public static void main(String[] args) {
        //逆序数组
        int[] arr = {10,9,8,7,6,5,4,3,2,1,0};
        reverse(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void reverse(int[] arr) {
        int left = 0;
        int right =arr.length-1;
        while(left < right) {//相等的时候就不需要逆序了
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }
相关文章
|
11天前
|
C语言
【C语言】拿捏冒泡排序(图解)
【C语言】拿捏冒泡排序(图解)
|
6天前
|
存储 C语言
C语言初阶④(数组)知识点+编程作业(三子棋,冒泡排序)(下)
C语言初阶④(数组)知识点+编程作业(三子棋,冒泡排序)
14 1
|
6天前
|
存储 C语言
C语言初阶④(数组)知识点+编程作业(三子棋,冒泡排序)(上)
C语言初阶④(数组)知识点+编程作业(三子棋,冒泡排序)
15 0
|
11天前
|
C语言
【C语言/数据结构】排序(选择排序,推排序,冒泡排序)
【C语言/数据结构】排序(选择排序,推排序,冒泡排序)
15 0
|
11天前
|
C语言
C语言的冒泡排序
C语言的冒泡排序
18 0
|
11天前
|
存储 算法 Java
wtf?java的冒泡排序还可以这样写
wtf?java的冒泡排序还可以这样写
9 1
|
11天前
|
搜索推荐 算法 C语言
【排序算法】C语言实现选择排序与冒泡排序
【排序算法】C语言实现选择排序与冒泡排序
|
11天前
|
Java 索引
Java练习题-用冒泡排序法实现数组排序
Java练习题-用冒泡排序法实现数组排序
15 2
|
11天前
|
算法 C语言
C语言之冒泡排序、快速排序法、希尔排序法
C语言之冒泡排序、快速排序法、希尔排序法
|
搜索推荐 C语言
【C语言】使用回调函数通过冒泡排序模拟实现qsort函数
【C语言】使用回调函数通过冒泡排序模拟实现qsort函数
【C语言】使用回调函数通过冒泡排序模拟实现qsort函数