您的位置: 首页  >  文章  >  Java基础之数组，排序，二分折半查找

Java基础之数组，排序，二分折半查找

分类: 文章 • 2024-11-14 13:54:04
数组概述：用于将相同数据类型存储在内存中
声明格式：元素类型[] 数组名称 = new 元素类型[长度];
创建数组： int arr[] = new int[5];
数组特点：一旦建立，必须明确长度

内存图
     Java基础之数组，排序，二分折半查找

常见数组异常
     ArrayIndexOutOfBoundsException     数组角标越界
     NullPointerException     引用型变量没有指向任何实体的时候，就会发生空指针异常     int[] arr = null
     [[email protected]     int[] arr = new int[3]; sop(arr);

遍历：
核心思想：就是对角标的操作，只要拿到角标，操作数组就易如反掌
用到的属性：length
正向遍历
for(int x=0; x<=arr.length; x++){}
反向遍历
for(int x=arr.length-1; x>=0; x--){}

最值：
int[] arr = new int[5];
int max = 0;   如果值为负数，和0比，0就是最大的了，因此要在"内部"比较
for(int x=0; x<arr.length; x++)
{
     if(arr[x] > max)
     {
          max = arr[x];
     }
}//错误的比较方法

元素的比较
int[] arr = new int[5];
int max = arr[0];
for(int x=1; x<arr.length; x++)
{
     if(arr[x] > max)
     {
          max = arr[x];
     }
}
角标的比较
        int[] arr = new int[5];
        int maxIndex = 0;
for(int x=0; x<arr.length; x++)
{
    if(arr[x] > arr[maxIndex])
    {
          maxIndex = x;
    }
}
arr[maxIndex]就是最大值
 Java基础之数组，排序，二分折半查找    
Java基础之数组，排序，二分折半查找Java基础之数组，排序，二分折半查找

for (int x=0; x<arr.length ; x++)
{
      int index = x;
      int num = arr[x];  
      for( int y=x+1; y<arr. length; y++)
     {
           if(arr[y] > num)
          {
              index = y;
              num = arr[y];
          }
     }
      if(index != x)
     {
           int temp = arr[index];
          arr[index] = arr[x];
          arr[x] = temp;
     }
}
封装交换方法
public static void swap(int[] arr, int x, int y)
{
     int temp = arr[x];
     arr[x] = arr[y];
     arr[y] = temp;
}

数组-查找
      /*
        查找指定的数值出现的位置
        明确一：该功能的最终结果是 int
        明确二：该功能在实现的过程中是否需要未知内容参与运算  数组和要找的值   
      */
       public static int getIndex(int[] arr,  int key)
      {
             for(int x=0; x<arr.length; x++)
            {
                   if(arr[x] == key)
                         return x;
            }
             return -1;
      } 

高效率查找-折半（二分）
Java基础之数组，排序，二分折半查找

            int min = 0;
             int max = arr.length -1;
             int mid = (min + max) / 2;
             while(arr[mid] != key)
            {
                   if(arr[mid] > key)
                        max = mid - 1;
                   else if (arr[mid] < key)
                        min = mid + 1;
                  
                  mid = (min + max) / 2;
                  
                   if(min > max)
                         return -1;  
            }
             return mid;

折半查找，第二种写法
          int max,min,mid;
          min = 0;
          max = arr.length-1;
          while(max > min)
          {
               mid = (max + min) >> 1;
               if(key > arr[mid])
               {
                    min = mid + 1;
               }
               else if(key < arr[mid])
               {
                    max = mid - 1;
               }
               else
               {
                    return mid;
               }
          }
          return -1;

二维数组
          格式：
               int[][] arr = new int[3][2];
               int[][] arr = new int[3][];
               int[][] arr = {{1,2,3},{4,5},{6,7,8,9}};
          遍历：
          for(int x = 0; x < arr.length; x++)
          {
               for(int y = 0; y < arr[x].length; y++)
               {
                    System.out.print(arr[x][y]);
               }
          }
               求和：
          int sum = 0;
          for(int x = 0; x < arr.length; x++)
          {
               for(int y = 0; y < arr[x].length; y++)
               {
                    sum += arr[x][y];
               }
          }
          System.out.print(sum);
    

相关推荐