Java 数组常见操作

发表于 | 分类于 | 阅读次数:
  • 今天整理了一些常用的数组操作，如最大值，查找，排序等等

数组最大值

值判断
1
2
3
4
5
6
7
8
public int maxValue(int[] a){
        int max = a[0];
        for(int i=0;i<a.length;i++){
            if(a[i]>max)
                max = a[i];
        }
        return max;
    }
下标判断
1
2
3
4
5
6
7
8
public int maxIndex(int[] a){
        int max = 0;
        for(int i=0; i<a.length;i++){
            if(a[i]>a[max])
                max = i;
        }
        return a[max];
    }

数组操作辅助方法

交换值
1
2
3
4
5
6
public void swap(int[] arr,int a,int b){
        int temp = 0;
        temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
输出链表
1
2
3
4
5
public void printList(int[] arr){
        for(int i = 0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

数组选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
public void chooseSort(int[] arr){                //选择排序
        int temp = 0;
        for(int i=0;i<arr.length-1;i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[j]>arr[i]){
                    //swap(arr,i,j);
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
选择排序改进版
  • 改进版的选择排序，设置了角标值和数组值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public void chooseSort2(int[] arr){
            for(int i=0;i<arr.length-1;i++) {
                int number = arr[i];
                int index = i;
                for (int j = i + 1; j < arr.length; j++) {
                    if (number > arr[j]) {
                        number = arr[j];
                        index = j;
                    }
                }
                if (index!=i)
                    swap(arr,i,index);
            }
        }

数组冒泡排序

  • 冒泡排序，五个数为例，共进行4+3+2+1 10次比较
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public void ppSort(int[] arr){                  //便于理解
            int temp = 0;
            for(int i = 0;i<arr.length-1;i++)
                for (int j=0;j<arr.length-1-i;j++){
                    if(arr[j]>arr[j+1]){
                        //swap(arr,j,j+1);
                        temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] =temp;
                    }
                }
        }
冒泡排序改进版
1
2
3
4
5
6
7
8
9
10
11
12
public void ppsort2(int[] arr){         //改进版冒泡
        int temp = 0;
        for (int i = arr.length-1;i>0;i--)
            for(int j=0;j<i;j++){
                if(arr[j]>arr[j+1]){
                    //swap(arr,j,j+1);
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] =temp;
                }
            }
    }

查找

通过值查找
1
2
3
4
5
6
7
8
public int findByValue(int[] arr,int key){      //通过值查找
        int index = -1;
        for (int i = 0;i<arr.length;i++){
            if(key == arr[i])
                index = i + 1;
        }
        return index;
    }
二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findHalf(int[] arr,int key){                             //二分查找
        list list = new list();
        list.chooseSort2(arr);
        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;
        }
        return -1;
    }
练习题

  • 给定一个有序的数组，如果往该数组中存储一个元素，并保证这个数组还是有序的，那么这个元素的存储的角标该如何获取？

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int getJiaoBiao(int[] arr,int key){         /
                list list = new list();
                list.chooseSort2(arr);
                int min =0;
                int max =arr.length-1;
                int mid;
                while(min<=max){
                    mid = (min+max)>>1;
                    if(key>arr[mid])
                        min = mid + 1;
                    else if (key<arr[mid])
                        max = mid - 1;
                    else
                        return mid;
                }
                return min;
        }

  • 在系统自带的Arrays类中，有这个方法，不过和我这个写的不一样，比我的更好一些，我把源码粘贴上来

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                         int key) {
            int low = fromIndex;
            int high = toIndex - 1;

            while (low <= high) {
                int mid = (low + high) >>> 1;
                int midVal = a[mid];

                if (midVal < key)
                    low = mid + 1;
                else if (midVal > key)
                    high = mid - 1;
                else
                    return mid; // key found
            }
            return -(low + 1);  // key not found.
        }

  • 不同的是返回值 比如我的答案如果是6，那么他的答案就会是-7，为什么那？

  • 因为要插入的这个数是不存在于数组中的，所以给他一个负数的位置，那么-7怎么来的？-6-1，因为还有1个值，就是用我的方法得到0的那个值，取了负数还是0，不好分辨，所以就整体取负后再减一
  • 总结说：存在，返回具体的角标位置，不存在的话 返回 -插入点-1