分治算法详解：从二分查找、快速排序到归并排序

创作时间:

作者:

@小白创作中心

分治算法详解：从二分查找、快速排序到归并排序

引用

CSDN

https://blog.csdn.net/qq_33373609/article/details/117958094

分治算法是计算机科学中一种重要的算法设计思想，广泛应用于各种算法实现中。本文将详细介绍分治算法的基本概念，并通过二分查找、快速排序和归并排序等经典算法，深入解析分治算法的具体应用。

前言

在常用的五大经典算法中，分治算法、贪心算法、动态规划算法、回溯算法和分支界限算法各自在计算机科学中占据重要地位。本文将重点介绍分治算法的一种实现方式，包括顺序查找、二分查找、快速排序和归并排序等方法。

定义

分治法的字面意思是“分而治之”，即将一个复杂问题分成两个或多个相同或相似的子问题，再将子问题进一步分解，直到可以简单求解。这种思想与递归、归并排序和二分查找等算法密切相关，是这些算法的基础。

顺序查找

顺序查找是最常用的查找方法之一，适用于无序表的查找。无论是顺序存储还是链式存储结构，只要线性表无序，就必须使用顺序查找。例如，在链表结构中查找某个值时，通常采用顺序查找的方式。

二分查找法

二分查找法要求数据已经排序，并且适用于数组的顺序存储结构。其查找速率非常快，时间复杂度为O(logn)。例如，对于8个元素的数组，只需要三次就可以查找到目标值。

二分查找法的核心是设计成左闭右开区间，采用区间无重复的思想。以下是二分查找的代码实现：

public static int binarySearch(int[] array, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = array[mid];
        if (key > midVal) {
            low = mid + 1;
        } else if (key < midVal) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -(low + 1);
}

需要注意的是，二分查找法的关键在于正确处理左闭右开区间，并确保循环跳出的条件。

快速排序（前序排序）

快速排序因其较高的排序效率而在同为O(N*logN)的排序方法中脱颖而出。其核心思想是将数组分为两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后递归地对这两部分数据进行快速排序。

以下是快速排序的代码实现：

public static void quickSort(int[] array, int begin, int end) {
    if (end - begin <= 0) return;
    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;
        } 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);
}

快速排序的另一种实现方式如下：

private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
    if (leftIndex >= rightIndex) {
        return;
    }
    int left = leftIndex;
    int right = rightIndex;
    int key = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= key) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= key) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = key;
    quickSort(arr, leftIndex, left - 1);
    quickSort(arr, left + 1, rightIndex);
}

快速排序的主要优点是排序效率高，但缺点是在处理大量重复数据或链式结构时性能不佳。

归并排序（后序）

归并排序的思想与快速排序类似，都是基于分治法。其主要区别在于，快速排序基于原数组操作，而归并排序需要拆分多个数组。以下是归并排序的代码实现：

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);
    }
}

public static void merge(int[] array, int left, int mid, int right) {
    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];
            k++;
            i++;
        } else {
            array[k] = rightArray[j];
            k++;
            j++;
        }
    }
    while (i < leftSize) {
        array[k] = leftArray[i];
        k++;
        i++;
    }
    while (j < rightSize) {
        array[k] = rightArray[j];
        k++;
        j++;
    }
}

归并排序的主要优点是适用于数据量大且包含大量重复数据的场景，但缺点是需要较大的空间开销。