使用插入排序和快速排序
使用插入排序和快速排序
提问于 2013-12-30 16:49:09
为什么大多数人对元素少于n的子数组使用插入排序来优化快速排序？我编写了一个插入排序函数和shell排序函数，并使用一些包含10、50、100个元素的随机数组来调用它们。shell排序似乎更快(我只用clock()来测量时间；我不知道这是不是一个好方法)。如果它比插入排序快，为什么不更多的人使用shell排序呢？我在插入排序函数中有错误吗？
我的代码：
double insertionSort(int *a, int size)
{
clock_t start, end;
int i, temp, pos;
start = clock();
for (i = 1; i < size; i++) {
temp = a[i];
pos = i - 1;
while (pos >= 0 && a[pos] > temp) {
a[pos + 1] = a[pos];
pos--;
}
a[pos + 1] = temp;
}
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC * 1000;
}
double shellSort(int *a, int size)
{
int gaps[8] = {701, 301, 132, 57, 23, 10, 4, 1};
int i, k , temp, pos;
clock_t start, end;
start = clock();
for (i = 0; i < 8; i++)
for (k = gaps[i]; k < size; k++) {
temp = a[k];
pos = k - gaps[i];
while (pos >= 0 && a[pos] > temp) {
a[pos + gaps[i]] = a[pos];
pos -= gaps[i];
}
a[pos + gaps[i]] = temp;
}
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC * 1000;
}5的输出：
Insertion Sort : Sorted in 0.002000 milliseconds
Shell Sort : Sorted in 0.001000 milliseconds10的输出：
Insertion Sort : Sorted in 0.004000 milliseconds
Shell Sort : Sorted in 0.001000 milliseconds50的输出：
Insertion Sort : Sorted in 0.007000 milliseconds
Shell Sort : Sorted in 0.007000 milliseconds100的输出：
Insertion Sort : Sorted in 0.015000 milliseconds
Shell Sort : Sorted in 0.014000 milliseconds200的输出：
Insertion Sort : Sorted in 0.040000 milliseconds
Shell Sort : Sorted in 0.028000 milliseconds回答 1
Stack Overflow用户
发布于 2014-11-03 15:18:52
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20836180
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号