黑马程序员技术交流社区

标题: 排序，查找，数组小结 [打印本页]
作者: 李前进    时间: 2014-3-26 01:50
标题: 排序，查找，数组小结
  1. import java.util.*;
  2. class  ArrayTest
  3. {
  4.         public static void main(String[] args)
  5.         {
  6.                 int arr[]={0,1,2,4,6,8,9};

  8.                 //在排序前打印
  9.                 System.out.print("排序前的数组：");
  10.                 printArray(arr);

  12.                 //选择排序
  13.                 //selectSort(arr);

  15.                 //冒泡排序
  16.                 //bubbleSort(arr);

  18.                 //Java自带排序
  19.                 //Arrays.sort(arr);

  21.                 //查找数组中的元素
  22.                 //int index=getIndex(arr,2);
  23.                 //System.out.println("2所在位置下角标为："+index);

  25.                 //折半查找
  26.                 //int index=halfSearch(arr,6);
  27.                 //System.out.println("6所在位置下角标为："+index);

  29.                 //折半查找第二种方式
  30.                 //int index=halfSearch_2(arr,6);
  31.                 //System.out.println("6所在位置下角标为："+index);

  33.                 //在排序后打印
  34.                 //System.out.print("排序后的数组：");
  35.                 //printArray(arr);

  37.          }

  39.         //选择排序
  40.          public static void selectSort(int[] arr)
  41.           {
  42.                         for(int x=0;x<arr.length-1;x++)
  43.                         {
  44.                                 for(int y=x+1;y<arr.length;y++)
  45.                                 {
  46.                                         if(arr[x]>arr[y])
  47.                                         {
  48.                                                 //int temp=arr[x];
  49.                                                 //arr[x]=arr[y];
  50.                                                 //arr[y]=temp;
  51.                                                 swap(arr,x,y);
  52.                                          }
  53.                                  }
  54.                      }
  55.             }


  58.         //冒泡排序
  59.          public static void bubbleSort(int[] arr)
  60.           {
  61.                         for(int x=0;x<arr.length-1;x++)
  62.                         {
  63.                                 for(int y=0;y<arr.length-x-1;y++)//-x:让每一次比较的元素减少。-1，避免角标越界。
  64.                                 {
  65.                                         if(arr[y]>arr[y+1])//大于变小于就是从大到小排序
  66.                                         {
  67.                                                 //int temp=arr[y];
  68.                                                 //arr[y]=arr[y+1];
  69.                                                 //arr[y+1]=temp;
  70.                                                 swap(arr,y,y+1);
  71.                                          }
  72.                                  }
  73.                      }
  74.             }

  76.                 //换位置功能
  77.                 public static void swap(int[] arr,int a,int b)
  78.             {
  79.                         int temp=arr[a];
  80.                         arr[a]=arr[b];
  81.                         arr[b]=temp;
  82.                  }

  84.                  //查找数组中的元素，从头到尾顺序查找
  85.                  public static int getIndex(int[]arr,int key)
  86.              {
  87.                          for(int x=0;x<arr.length;x++)
  88.                          {
  89.                                  if(arr[x]==key)
  90.                                          return x;
  91.                          }
  92.                          return -1;
  93.                   }

  95.                 //折半查找，效率高，但是必须保证数组为有序数组
  96.                 public static int halfSearch(int[] arr,int key)
  97.             {
  98.                         int min=0,max=arr.length-1,mid=(max+min)/2;

  100.                         while(arr[mid]!=key)
  101.                         {
  102.                                 if(key>arr[mid])
  103.                                         min=mid+1;
  104.                                 else if(key<arr[mid])
  105.                                         max=mid-1;

  107.                                 if(min>max)
  108.                                         return -1;
  109.                                 mid=(mid+max)/2;
  110.                         }
  111.                         return mid;
  112.                 }


  115.                 //折半查找第二种方式
  116.                 public static int halfSearch_2(int[] arr,int key)
  117.             {
  118.                         int min=0,max=arr.length-1,mid=(max+min)/2;

  120.                         while(min<=max)
  121.                         {
  122.                                 mid=(max+min)>>1;

  124.                                 if(key>arr[mid])
  125.                                         min=mid+1;
  126.                                 else if(key<arr[mid])
  127.                                         max=mid-1;
  128.                                 else
  129.                                         return mid;
  130.                         }
  131.                         return -1;
  132.                 }

  134.                 //遍历数组，美化打印格式
  135.                 public static void printArray(int[] arr)
  136.                 {
  137.                         System.out.print("[");
  138.                         for(int x=0;x<arr.length;x++)
  139.                         {
  140.                                 if(x!=arr.length-1)
  141.                                         System.out.print(arr[x]+", ");
  142.                                 else
  143.                                         System.out.println(arr[x]+"]");
  144.                         }
  145.                 }

  147. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2