通俗易懂的C语言快速排序和归并排序的时间复杂度分析

前言

快速排序和归并排序是常用的排序算法，它们不仅简单易懂，而且时间复杂度也相对较低。本文将从时间复杂度的角度出发，详细讲解C语言快速排序和归并排序的实现原理以及分析其时间复杂度。

注：本文中所涉及的代码示例是基于C语言实现的，若您对C语言不太熟悉，建议先学习一下。

快速排序

快速排序是一种分治算法，用于对于给定的数据集合（数组），通过一次次的划分（partition）操作，将其分为两个子集，其中一个子集中的所有元素都比另一个子集中的元素小。然后递归地对两个子集进行排序，最终得到一个有序的序列。

下面是快速排序的C语言代码实现：

void quick_sort(int arr[], int left, int right) {
    if (left < right) {
        int i = left, j = right, pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot)
                j--;
            if (i < j)
                arr[i++] = arr[j];
            while (i < j && arr[i] < pivot)
                i++;
            if (i < j)
                arr[j--] = arr[i];
        }
        arr[i] = pivot;
        quick_sort(arr, left, i - 1);
        quick_sort(arr, i + 1, right);
    }
}

快速排序的时间复杂度为O(nlogn)，其中n为数组的长度。

下面对时间复杂度进行详细解释：

快速排序的核心操作是划分（partition），其时间复杂度为O(n)。

每次划分操作将数组划分为左右两个子集，其中一个子集的大小为原数组的一半，另一个子集的大小为原数组的一半减去1或2。

因此对于长度为n的数组，其划分次数为O(logn)。

对于每一次划分，需要遍历数组一遍，对数组中元素进行位置交换。

因此对于长度为n的数组，其交换操作次数的上限为O(nlogn)。

综上所述，快速排序的时间复杂度为O(nlogn)，其中n为数组的长度。

下面通过一个实例，说明快速排序的时间复杂度：

对于一个长度为8的无序数组{3, 8, 2, 1, 5, 4, 6, 7}，其通过快速排序后的有序数组为{1, 2, 3, 4, 5, 6, 7, 8}。

快速排序的划分过程如下图所示：

划分过程共进行了三次，数组的长度分别为8，4，2。

因此其时间复杂度为O(nlogn)，其中n=8。

归并排序

归并排序是一种分治算法，用于对于给定的数据集合（数组），通过一次次的归并（merge）操作，将其分成若干个子序列，然后递归地将子序列排序，最终将其合并为一个有序的序列。

下面是归并排序的C语言代码实现：

void merge(int arr[], int left, int mid, int right) {
    int i = 0, j = left, k = mid + 1;
    int temp[right - left + 1];
    while (j <= mid && k <= right) {
        if (arr[j] < arr[k])
            temp[i++] = arr[j++];
        else
            temp[i++] = arr[k++];
    }
    while (j <= mid)
        temp[i++] = arr[j++];
    while (k <= right)
        temp[i++] = arr[k++];
    for (i = 0, j = left; j <= right; i++, j++)
        arr[j] = temp[i];
}

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

归并排序的时间复杂度为O(nlogn)，其中n为数组的长度。

下面对时间复杂度进行详细解释：

归并排序的核心操作是归并（merge），其时间复杂度为O(n)。

对于长度为n的数组，初始状态下，其已经被分成n个子序列，每个子序列的长度为1。

每次归并操作需要遍历所有的子序列，在每个子序列中，需要访问其中的所有元素。

因此对于长度为n的数组，其归并操作次数为O(logn)。

对于每一次归并，需要使用一个长度为n的临时数组来存储归并后的结果。

因此对于长度为n的数组，其临时数组的空间复杂度为O(n)。

综上所述，归并排序的时间复杂度为O(nlogn)，其中n为数组的长度。

下面通过一个实例，说明归并排序的时间复杂度：

对于一个长度为8的无序数组{3, 8, 2, 1, 5, 4, 6, 7}，其通过快速排序后的有序数组为{1, 2, 3, 4, 5, 6, 7, 8}。

归并排序的归并过程如下图所示：

归并过程共进行了三次，数组的长度分别为2，4，8。

因此其时间复杂度为O(nlogn)，其中n=8。