java (查找和排序)

1.查找

递归形式：

   public int binarySearch(int key,int arr[],int lo,int ht){
        if (ht<lo){return -1;}

        //获取中间下标
        int middle = lo+(lo+ht)/2;
            //对比key和中间数值
            if (key<arr[middle]){
                // 如果小于，说明key在数组的前半部分
                return binarySearch(key,arr,lo,middle-1);
            }else if(key>arr[middle]){
                // 如果大于，说明key在数组的后半部分
                return binarySearch(key,arr,middle+1,ht);
            }else{
                return middle;
            }

    }

二分查找:

  /**
     * @param arr 数据源
     * @param key 查找的数据
     * @return 在arr里的位置
     */
    private int halfSearch(int[] arr, int key) {
        int min, mid, max;
        min = 0;
        max = arr.length - 1;
        while (min <= max) {
            mid = (min + max) / 2;
            if (key > arr[mid]) {
                min = mid + 1;
            } else if (key < arr[mid]) {
                max = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

2.排序方式

下面这个表格总结了各种排序算法的复杂度与稳定性：

冒泡排序

特点：相邻两个元素进行比较。内循环结束一次，最值出现在最后角标位。

    public static void bubbleSort(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])
                {
                    /*
                    int temp = arr[y];
                    arr[y] = arr[y+1];
                    arr[y+1] = temp;
                    */
                    swap(arr,y,y+1);
                }
            }
        }
    }

选择排序

特点:在内循环第一次结束，最值出现最低角标位。

    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 int[] insertionSort(int [] arr) {
        int len = arr.length;
        int preIndex, current;
        for (int i = 1; i < len; i++) {
            preIndex = i - 1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
        return arr;
    }