黑马程序员技术交流社区

标题: 数组常见操作，选择冒泡插入位置角标等 [打印本页]

---

作者: Neverlandxu    时间: 2015-10-15 22:59
标题: 数组常见操作，选择冒泡插入位置角标等

白天上课写的代码，java基础所要学习的内容基本都在这里了包括，选择排序，冒泡排序，和一个有关排序效率的问题(当要处理的数据量比较大的时候)
以及判断一个数是否在数组当中，如果不在，假设要插入的话应该在哪个位置，获取该位置的角标



import java.util.*;

class SortDemo
{
        public static void main(String[] args)
        {
                int[] arr = {31,4,34,12,23,99,12,42,25,33,6,55,78,21};
                printArray(arr);
                //bubbleSort_2(arr);
                //selectSort(arr);
                selectSort_2(arr);
               
                //Arrays.sort(arr);
                printArray(arr);
                //selectSort(arr);
                //printArray(arr);
                //System.out.println("请输入要查找的数...");
                //Scanner sc = new Scanner(System.in);
                //int x = sc.nextInt();
                 
                int index = insertValue(arr,43);
                System.out.println(index);

                int index1 = Arrays.binarySearch(arr,43);//若存在返回角标位置，不存在返回-插入点-1
                System.out.println(index1);
               

               
        }
        public static void swap(int[] arr,int a,int b)
        {
                arr[a] = arr[a] ^ arr[b];
                arr[b] = arr[a] ^ arr[b];
                arr[a] = arr[a] ^ arr[b];
                //int temp = arr[a];
                //arr[a] = arr[b];
                //arr[b] = temp;

        }
        public static void printArray(int[] arr){

                System.out.print("[");
               
                for (int x=0; x<arr.length; x++)
                {
                        if(x!=arr.length-1)
                                System.out.print(arr[x]+", ");
                        else
                                System.out.println(arr[x]+"]");
                               
                }
                System.out.println();
        }
        public static void selectSort(int[] arr)
        {
                for(int x=0; x<arr.length-1; x++)
                {
                        for(int y=x+1; y<arr.length; y++)
                        {
                                if(arr[x]>arr[y])
                                {
                                        //int temp = arr[x];
                                        //arr[x] = arr[y];
                                        //arr[y] = temp;
                                        swap(arr,x,y);
                                }
                        }
                }
        }
        //更加高效，先比较，直到找出最小值时再进行换位
        public static void selectSort_2(int[] arr)
        {
                for(int x=0; x<arr.length-1; x++)
                {
                        int value = arr[x];
                        int index = x;
                        for(int y=x+1; y<arr.length; y++)
                        {
                                if(value>arr[y])
                                {
                                        value = arr[y];
                                        index = y;
                                        //int temp = arr[x];
                                        //arr[x] = arr[y];
                                        //arr[y] = temp;
                                        //swap(arr,x,y);
                                }
                        }
                        if(index != x)
                                swap(arr,index,x);
                }
        }
        public static void bubbleSort_1(int[] arr)
        {
                for(int x=0; x<arr.length-1; x++)
                {
                        for (int y=0; y<arr.length-x-1; y++)
                        {
                                if(arr[y]>arr[y+1])
                                {
                                        swap(arr,y,y+1);
                                }
                        }
                }
        }
        public static void bubbleSort_2(int[] arr)
        {
                for(int x=arr.length-1; x>0; x--)
                {
                        for (int y=0; y<x; y++)
                        {
                                if(arr[y]>arr[y+1])
                                {
                                        swap(arr,y,y+1);
                                }
                        }
                }
        }
        public static int getIndex(int[] arr,int key)
        {
                for (int x=0; x<arr.length; x++)
                {
                        if(arr[x]==key)
                                return x;
                }
                return -1;
        }
        public static int halfSearch(int[] arr,int key)
        {
                int max = arr.length-1;
                int min = 0;
                int mid = (max + min)/2;
                while(arr[mid] != key)
                {
                        if(key>arr[mid])
                        {
                                min = mid + 1;
                        }
                        else
                        {
                                max = mid - 1;
                        }
                        if(max<min)
                        {
                                return -1;
                        }
                        mid = (min + max)/2;
                }
                return mid;
        }

        public static int halfSearch_2(int[] arr,int key)
        {
                int max = arr.length-1;
                int min = 0;
                int mid;
                while(min<=max)
                {
                        mid = (max + min)>>1;
                        if(key>arr[mid])
                        {
                                min = mid + 1;
                        }
                        else if(key<arr[mid])
                        {
                                max = mid - 1;
                        }
                        else
                        {
                                return mid;
                        }
                        //mid = (max + min)>>1;
                }
                return -1;
        }
/*如果要插入一个数，求应该放入的位置*/
        public static int insertValue(int[] arr,int key)
        {
                int max = arr.length-1;
                int min = 0;
                int mid;
                while(min<=max)
                {
                        mid = (max + min)>>1;
                        if(key>arr[mid])
                        {
                                min = mid + 1;
                        }
                        else if(key<arr[mid])
                        {
                                max = mid - 1;
                        }
                        else
                        {
                                return mid;
                        }
                        //mid = (max + min)>>1;
                }
                return min;
        }
}

---

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

黑马程序员IT技术论坛 X3.2