Shell排序函数没有对数组进行完全排序
Shell排序函数没有对数组进行完全排序
提问于 2017-02-04 13:51:10
我有一个由10个整数组成的数组，我想对它进行排序，但最后一个数组似乎没有完全排序。
// Shell sort Function
void shell_sort(int A[]){
display_array(A);
int k = ARRAY_SIZE / 2;
int x = 0; // index of value that swaps with value k spaces back
int temp = 0;
while (k > 0){
for (int i = ARRAY_SIZE-1; i >= k; i-- ){
x = i;
while( (x - k) >= 0 ){
if ( A[x] < A[x-k] ){
temp = A[x];
A[x] = A[x-k];
A[x-k] = temp;
x -= k ;
}
else{
break;
}
}
}
printf("k=%d\n",k);
display_array(A);
k /= 2;
}
}这是输入和输出：
Input: int A[ARRAY_SIZE] = {15,4,6,2,7,8,44,1,9,3};
Output:
Input
15 4 6 2 7 8 44 1 9 3
k = 5
8 4 1 2 3 15 44 6 9 7
k = 2
1 2 8 4 3 6 9 15 44 7
k = 1
1 2 3 8 4 6 7 9 15 44你能指出我哪里错了吗？
回答 2
Stack Overflow用户
发布于 2017-02-04 14:17:21
我将k /= 2改为k--，我得到了答案，但它需要更多的循环。我不确定这是不是我该怎么做。
下面是输出：
15 4 6 2 7 8 44 1 9 3
k = 5
8 4 1 2 3 15 44 6 9 7
k = 4
3 4 1 2 8 7 44 6 9 15
k = 3
2 4 1 3 6 7 15 8 9 44
k = 2
1 3 2 4 6 7 9 8 15 44
k = 1
1 2 3 4 6 7 8 9 15 44Stack Overflow用户
发布于 2017-02-04 15:52:36
我对你的程序进行了如下重构：
#include <stdio.h>
#define ARRAY_SIZE 10
// Shell sort Function
void display_array(int A[]) {
int i;
for (i =0; i < ARRAY_SIZE; ++i)
printf("%d ", A[i]);
printf ("\n");
}
void shell_sort(int A[]){
display_array(A);
int temp = 0;
int i,j,k;
for (i = ARRAY_SIZE/2; i > 0; i = i/2 ){
for (j = i; j < ARRAY_SIZE; ++j) {
for (k = j -i; k >= 0; k = k - i) {
if(A[k+i]>=A[k])
break;
else
{
temp=A[k];
A[k]=A[k+i];
A[k+i]=temp;
}
printf("k=%d\n",k);
display_array(A);
}
}
}
}
int main(void) {
// your code goes here
int A[ARRAY_SIZE] = {15,4,6,2,7,8,44,1,9,3};
shell_sort(A);
return 0;
}我看到以下输出：
15 4 6 2 7 8 44 1 9 3
k=0
8 4 6 2 7 15 44 1 9 3
k=2
8 4 1 2 7 15 44 6 9 3
k=4
8 4 1 2 3 15 44 6 9 7
k=0
1 4 8 2 3 15 44 6 9 7
k=1
1 2 8 4 3 15 44 6 9 7
k=2
1 2 3 4 8 15 44 6 9 7
k=5
1 2 3 4 8 6 44 15 9 7
k=6
1 2 3 4 8 6 9 15 44 7
k=7
1 2 3 4 8 6 9 7 44 15
k=4
1 2 3 4 6 8 9 7 44 15
k=6
1 2 3 4 6 8 7 9 44 15
k=5
1 2 3 4 6 7 8 9 44 15
k=8
1 2 3 4 6 7 8 9 15 44请注意问题中提到的评论。您应该将数组大小传递给函数。然而，这只是一个粗略的实现。
编辑
进一步重构的代码如下所示：
void shell_sort(int A[]){
display_array(A);
int k = ARRAY_SIZE/2; // This is the offset you want to begin with
int j = 0; // index of value that swaps with value k spaces back
int temp = 0;
int i;
while (k > 0){
// browse through the later half of the array k to ARRAY SIZE
for (i = k; i < ARRAY_SIZE; i++ ) {
j = i;
int temp = A[i];
// As long as j >= k, check if values can be swapped
while( (j - k) >= 0 && A[j-k] > temp ){
A[j] = A[j-k];
j = j -k;
}
// finally insert the correct value at j
A[j] = temp;
}
printf("k=%d\n",k);
display_array(A);
k = k/2;
}
}进行此更改后，我们将看到所需的以下输出：
15 4 6 2 7 8 44 1 9 3
k=5
8 4 1 2 3 15 44 6 9 7
k=2
1 2 3 4 8 6 9 7 44 15
k=1
1 2 3 4 6 7 8 9 15 44希望这能有所帮助。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42036999
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号