C语言排序算法：希尔排序、快速排序、堆排序

1. 希尔排序法

希尔排序是一种插入排序的改进版本，它通过将数据分组并在每个组内进行插入排序来提高效率。希尔排序的基本思想是，将待排序的数列分成若干个子序列，分别进行插入排序，待整个序列中的记录已经基本有序时，再对全体记录进行一次直接插入排序。

希尔排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

代码实现：

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

2. 快速排序算法

快速排序是一种基于分治思想的排序算法，它的基本思想是从数列中选取一个基准元素，将数列分成两个部分，一部分所有元素都比基准元素小，另一部分所有元素都比基准元素大，然后对这两部分分别进行递归排序。

快速排序的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。

代码实现：

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

3. 堆排序算法

堆排序是一种树形选择排序算法，它的基本思想是将待排序的数列构造成一个完全二叉树，并将其调整为大根堆或小根堆，然后依次将堆顶元素与堆底元素交换，再对剩余的数列进行堆调整，直到整个数列有序。

堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

代码实现：

void heapify(int arr[], int n, int i){
    int largest=i;
    int l=2*i+1,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 heap_sort(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);
    }
}