C语言实现希尔排序、快速排序和堆排序算法 - 代码示例

以下是C语言实现希尔排序法、快速排序算法和堆排序算法对n个整数进行排序的示例代码：

1. 希尔排序法

void shell_sort(int arr[], int n) {
    int i, j, gap, temp;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            temp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

2. 快速排序算法

void quick_sort(int arr[], int left, int right) {
    int i, j, pivot, temp;
    if (left < right) {
        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);
    }
}

3. 堆排序算法

void heap_sort(int arr[], int n) {
    int i, temp;
    for (i = n / 2 - 1; i >= 0; i--) {
        heap_adjust(arr, i, n);
    }
    for (i = n - 1; i >= 1; i--) {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heap_adjust(arr, 0, i);
    }
}

void heap_adjust(int arr[], int i, int n) {
    int j, temp;
    temp = arr[i];
    j = 2 * i + 1;
    while (j < n) {
        if (j + 1 < n && arr[j + 1] > arr[j]) {
            j++;
        }
        if (arr[j] <= temp) {
            break;
        }
        arr[i] = arr[j];
        i = j;
        j = 2 * i + 1;
    }
    arr[i] = temp;
}

以上三种排序算法的时间复杂度均为O(nlogn)。其中，希尔排序法的平均时间复杂度为O(n^1.3)，快速排序算法的最坏时间复杂度为O(n^2)，但一般情况下为O(nlogn)，堆排序算法的时间复杂度为O(nlogn)。