网站空间租用哪家好,驻马店市住房和城乡建设局网站首页,网络营销学校哪个比较好,办网站怎么赚钱希尔排序是插入排序的改进版本#xff0c;适合中等规模数据排序#xff0c;性能优于简单插入排序。 // 希尔排序函数
void shellSort(int arr[], int n) {// 初始间隔#xff08;gap#xff09;为数组长度的一半#xff0c;逐步缩小for (int gap n / 2; gap 0; gap …希尔排序是插入排序的改进版本适合中等规模数据排序性能优于简单插入排序。 // 希尔排序函数
void shellSort(int arr[], int n) {// 初始间隔gap为数组长度的一半逐步缩小for (int gap n / 2; gap 0; gap / 2) {// 对每个间隔进行插入排序for (int i gap; i n; i) {int temp arr[i]; // 当前需要插入的元素int j;// 将比 temp 大的元素向后移动for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp; // 插入 temp 到正确位置}}
}
#include stdio.h
// 打印数组函数
void printArray(int arr[], int n) {for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);
}int main() {int arr[] {12, 34, 54, 2, 3}; // 待排序数组int n sizeof(arr) / sizeof(arr[0]); // 计算数组长度printf(排序前的数组: \n);printArray(arr, n);shellSort(arr, n); // 调用希尔排序函数printf(排序后的数组: \n);printArray(arr, n);return 0;
}
优化建议
1.优化间隔序列使用更高效的间隔序列如 Hibbard 或 Sedgewick 序列可以提升性能。
void shellSortOptimized(int arr[], int n) {int gaps[] {701, 301, 132, 57, 23, 10, 4, 1}; // Sedgewick 序列int gapsSize sizeof(gaps) / sizeof(gaps[0]);for (int k 0; k gapsSize; k) {int gap gaps[k];for (int i gap; i n; i) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}
}
2.结合插入排序当间隔缩小到 1 时希尔排序退化为插入排序适合小规模数据。
3.稳定性希尔排序是不稳定的排序算法相同元素的相对顺序可能改变。
