C语言分别用希尔排序法、快速排序算法、堆排序算法对n个整数进行排序

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=2i+1,r=2i+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); }