滴水逆向联盟

标题: 基于visual Studio2013解决C语言竞赛题之1081shell排序 [打印本页]

作者: 大灰狼 时间: 2014-8-7 09:26
标题: 基于visual Studio2013解决C语言竞赛题之1081shell排序
题目

解决代码及点评

<pre code_snippet_id="91880" snippet_file_name="blog_20131202_1_2646179" class="cpp" name="code"></pre><pre code_snippet_id="91880" snippet_file_name="blog_20131202_1_2646179" class="cpp" name="code"><pre code_snippet_id="91880" snippet_file_name="blog_20131202_1_2646179" class="cpp" name="code"><pre code_snippet_id="91880" snippet_file_name="blog_20131202_1_2646179" class="cpp" name="code"><pre code_snippet_id="91880" snippet_file_name="blog_20131202_1_2646179" class="cpp" name="code">/************************************************************************/
/*
81. SHELL排序程序。
该方法的特征是：一个元素与它间隔为J 的元素进行比较或交换，然后逐步缩小这个间隔到1为止。
J缩小的规律可以是 J<=J/2或J<=(J+1)/2，我们取 J<=J/2（取整）编程。具体地说方法如下：
对于N个数据，首先让J<=INT(N/2)，让X[1]与X[J+1]比较（假设数组名X），
X[2]与X(J+2)比较，...，X[N-J]与X[N]比较，若次序颠倒，则互相交换。然后再重新比较一轮，
直到没有交换为止。于是令J<=INT(J/2)，再重复以上操作，直到J=1，而且在这一轮比较中没有交换，才排序完成。
例如 N=9
数据为： 5 7 6 4 9 1 3 2 8 交换次数
J取4（INT(9/2)） 5 1 3 2 8 7 6 4 9 4
再比较一轮不变 0
J取2（INT(4/2)） 3 1 5 2 6 4 8 7 9 3
再比较一轮不变 0
J取1（INT(2/2)） 1 3 2 5 4 6 7 8 9 4
再比较一轮 1 2 3 4 5 6 7 8 9 2
再比较一轮不变
停止
*/
/************************************************************************/
#include <stdio.h>
#include <stdlib.h>
void Shellsort(int * arr,int n)
{
int i,j,increment;
int temp;
for (increment=n/2;increment>0;increment/=2)
{
for (i=increment;i<n;i++)
{
temp=arr;
for (j=i;j>=increment;j-=increment)
{
if (temp<arr[j-increment])
{
arr[j]=arr[j-increment];
}
else
{
break;
}
}
arr[j]=temp;
}
}
}
void main()
{
int arr[10]={1,4,2,6,3,8,9,6,3,12};
for (int i=0;i<10;i++)
{
printf("%5d",arr);
}
printf("\n");
Shellsort(arr,10);
for (int i=0;i<10;i++)
{
printf("%5d",arr);
}
printf("\n");
system("pause");
}</pre><br><br><br></pre></pr

欢迎光临滴水逆向联盟 (http://dtdebug.com/)