C语言实现三种排序算法：希尔排序、快速排序、堆排序

C语言实现三种排序算法：希尔排序、快速排序、堆排序

本文将使用 C 语言代码实现三种常见的排序算法：希尔排序、快速排序和堆排序，并附带详细的代码注释，方便读者理解和学习。

希尔排序

希尔排序是一种插入排序的改进版本，它先将数组分成多个子数组，对子数组进行插入排序，然后逐渐缩小子数组的间隔，直到最后对整个数组进行插入排序。

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

快速排序

快速排序是一种分治排序算法，它将数组分成两个子数组，分别对子数组进行排序，然后将两个子数组合并。

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

堆排序

堆排序是一种基于堆数据结构的排序算法，它将数组建成一个堆，然后不断取出堆顶元素，直到堆为空。

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

以上代码仅供参考，读者可以根据实际情况进行修改和完善。