数据结构(五)查找技术

1. 查找技术

1. 顺序查找
   如果线性表为无序表,即表中元素的排列是无序的,则不管线性表采用顺序存储还是链式存储,都必须使用顺序查找,如果线性表有序,但采用链式存储结构,则也必须使用顺序查找(for循环遍历)
2. 二分查找

• 前提条件:数据已经排序

2. 二分查找

每次与中间的树进行比较,每次缩减一半的查找量 image

左闭右开

    @Test
    public void testBinary() {
        int[] array = new int[]{1, 2, 4, 9, 13, 20, 22, 29, 34, 35};
        int key = 20;
        int keyIndex = binarySearch(array, 0, array.length, 20);
    }

    /**
     * 二分查找
     *
     * @param array
     * @param fromIndex
     * @param toIndex
     * @param key
     * @return
     */
    public static int binarySearch(int[] array, int fromIndex, int toIndex, int key) {
        //左闭右开，区间无重复的思想
        int low = fromIndex;
        int hight = toIndex - 1;
        while (low <= hight) {
            //取中间
            int mid = (low + hight) / 2;
            int midVal = array[mid];
            if (key > midVal) {
                low = mid + 1;
            } else if (key < midVal) {
                hight = mid - 1;
            } else {
                return mid;
            }
        }
        return -(low + 1);//找不到时停在了low+1的位置
    }

3. 快速排序

• 应用场景:数据量大并且是线性结构
• 短处:有大量重复数据的时候，性能不好;单向链式结构处理性能不好（一般来说，链式都不使用）

1. 快速排序思路

• 取第一个数,然后与最后一个做对比,最后一个数大就与倒数第二个数比较,如果小,则把比较的数放到第一个数的位置,然后用取出来的第一个数和第二个数比较,如果第二个数大,就把第二个数填充到最后一个数的位置,知道最后low,和heigh重合,此处就是取出的数的位置,这个数左边的都比他小,右边都比他大,俩边重复操作,就完成了排序,O(n)=n*log2N

  
  image

    @Test
    public void testQuickSork() {
        int[] array = new int[]{1, 7, 5, 2, 6, 7, 8, 9};
        quickSort(array, 0, array.length - 1);
        for (int i : array) {
            System.out.println("排序"+i);
        }
    }

    public static void quickSort(int[] array, int begin, int end) {
        if (end - begin <= 0) {
            return;
        } else {
            int x = array[begin];
            int low = begin;
            int high = end;
            //由于会从俩头取数据，需要一个方向
            boolean direction = true;
            L1:
            while (low < high) {
                if (direction) {//从右往左找
                    for (int i = high; i > low; i--) {
                        if (array[i] <= x) {
                            array[low++] = array[i];
                            high = i;
                            direction = !direction;
                            continue L1;
                        }
                    }
                    high = low;//如果上面的if从未进入，让俩个指针重合
                } else {
                    for (int i = low; i < high; i++) {
                        if (array[i] >= x) {
                            array[high--] = array[i];
                            low = i;
                            direction = !direction;
                            continue L1;
                        }
                    }
                    low = high;
                }
            }
            //把最后的值，放到中间
            array[low] = x;
            //开始完成左右俩侧的操作
            quickSort(array, begin, low - 1);
            quickSort(array, low + 1, end);
        }
    }

4.归并排序

• 应用场景:数据量大并且有很多重复数据，链式结构
• 短处:需要空间大
• 思想:将数组按中间分拆,先比较大小,再合并 image

    @Test
    public void testMerge() {
        int[] array = new int[]{3, 2, 5, 9, 3, 4, 1, 11};
//        merge(array, 0, 4, 7);
        mergeSort(array, 0, 7);
        for (int i : array) {
            System.out.println("合并：" + i);
        }
    }


    public static void mergeSort(int array[], int left, int right) {
        if (left == right) {
            return;
        } else {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid + 1, right);
        }
    }

    /**
     * @param array
     * @param left
     * @param mid
     * @param right
     */
    public static void merge(int[] array, int left, int mid, int right) {
        //例如array={1,2,5,9,3,4,10,11} left = 0; mid = 4; right = 7
        int leftSize = mid - left;
        int rightSize = right - mid + 1;
        //生成数组
        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];
        //填充数据
        for (int i = left; i < mid; i++) {
            leftArray[i - left] = array[i];
        }
        for (int i = mid; i <= right; i++) {
            rightArray[i - mid] = array[i];

        }
        //合并
        int i = 0;
        int j = 0;
        int k = left;

        while (i < leftSize && j < rightSize) {
            if (leftArray[i] < rightArray[j]) {
                array[k] = leftArray[i];
                i++;
                k++;
            } else {
                array[k] = rightArray[j];
                j++;
                k++;
            }
        }
        while (i < leftSize) {
            array[k] = leftArray[i];
            k++;
            i++;
        }
        while (j < rightSize) {
            array[k] = rightArray[j];
            k++;
            j++;
        }

    }