排序初步
排序初步之一:插入排序
排序是最基本的算法,值得认真学习。

为了配合大家学习C语言,我将陆续发一些关于排序的帖子,

尽量通俗易懂。以下的例子均在linux gcc下编译通过。

/* added on 2003-05-24
* by hofman
*/


main()
{
int A[] = {36,25,48,12,65,43,20,58};
void insertSort(int A[],int n);
int n,k;
for( k=0;k<8;k++)
{
printf(
"%d \t",A[k]);
}
printf(
"\n");

n = 8;
printf(
"%d\n",n);
insertSort(A,8);
// show outcome
for( k=0;k<8;k++)
{
printf(
"%d \t",A[k]);
}
printf(
"\n");
}
// end of main


void insertSort(int A[],int n)
{
int x;
int i,j;

for(i=1;i<n;i++)
{
x=A<i>;
for(j=i-1;j>=0;j--)
{
if(A[j]>x)
A[j+1]=A[j];
else break;
}
A[j+1] = x;
}
}



------

回复此文章 |

直接插入排序的特点:

将无序数组A[n](A[0],A[1],A[2]...,A[n-1])

看成由有序数组以及无序数组组成,

最初有序数组仅由A[0]组成,而无序数组由A[1],A[2]...,A[n-1]组成。

直接排序就是不断地由由无序数组中依次取出一个整数,

经过计算(这是关键!)直接插入到有序数组相应的位置中。

直到无序数组长度为0,此时有序数组长度则相应地由最初的1(仅A[0])扩展到n,

也就是说,此时数组全部有序,排序完成。

void insertSort(int A[],int n)
{
int x;
int i,j;

/* 循环n-1遍,将A[1],A[2]...,A[n-1]插入到有序数组中。
* 外循环
*/

for(i=1;i<n;i++)
{
/* 将待插入的A<i>暂存到x中 */
x=A<i>;

/* 内循环
* 在有序表中寻找A<i>的位置
* 有序表的长度在A<i>插入前为i-1,故j=i-1为j的初始值
* A<i>插入后,有序表的长度增加到i。
*/

for(j=i-1;j>=0;j--)
{
/* 在有序表中从后(大)向前(小)查找比A<i>大的数
* 找到了则后移,
* 找到一个后移一个,找到i-1个则后移i-1个(此时A[0]位置被空出来)
* 若一个都没有找到,则不进行移动操作,
* 此时有序表中最末尾一个位置在(就是第i个位置)刚好就是A<i>应该在的位置
*/

if(A[j]>x)
A[j+1]=A[j];
else break;
}
/* 找到了A<i>该呆的位置,从暂存变量x中取出A<i>的值,直接插入到有序表中
* A[j+1]为A[0]-A<i>中的某一个,就是说j+1:[0,i]
*/

A[j+1] = x;
}
}

------
回复此文章 |

main()
{
int A[] = {36,25,48,12,65,43,20,58};
void selectSort(int A[],int n);
int n,k;
for( k=0;k<8;k++)
{
printf(
"%d \t",A[k]);
}
printf(
"\n");
// n = sizeof(A);
n = 8;
printf(
"%d\n",n);
selectSort(A,8);
// show outcome
for( k=0;k<8;k++)
{
printf(
"%d \t",A[k]);
}
printf(
"\n");
}
// end of main


void selectSort0(int A[],int n)
{
int x;
int i,j,k;

for(i=0;i<n;i++)
{
k = i;
for(j=i+1;j<n;j++)
{
if(A[k]>A[j])
{
x=A[k];
A[k]=A[j];
A[j]=x;

}
/* end of if */
}
/* end of inner loop */
}
/* end of outer loop */
}
/* end of func */

void selectSort(int A[],int n)
{
int x;
int i,j,k;

for(i=0;i<n;i++)
{
k = i;
for(j=i+1;j<n;j++)
{
if(A[j]<A[k]) k = j;
}
if(k!=i)
{
x=A<i>;
A<i>=A[k];
A[k]=x;
}
/* end of if */
}
/* end of outer loop */
}
/* end of func */



------
回复此文章 |

这可能是最简单的排序方法了。
循环n-1遍:
第一遍:从无序区间中选出最小值,插入到有序区间作为第一个元素;
第二遍:从无序区间中选出次最小值,插入到有序区间作为第二个元素;
.........

无序区间不断缩小,有序区间不断扩大。

算法关键是找出最小值的算法:
先让无序区间的第一个元素作为最小值的候选元素,
在无序区间中依次向后比较,若找到更小者,则该元素成为新的候选元素,
继续比较,直至无序区间末尾,最终胜出者就作为最小值被插入到有序区间。

void selectSort0(int A[],int n)
{
int x;
int i,j,k;

for(i=0;i<n;i++)
{
k = i;
for(j=i+1;j<n;j++)
{
if(A[k]>A[j])
{
x=A[k];
A[k]=A[j];
A[j]=x;

}
/* end of if */
}
/* end of inner loop */
}
/* end of outer loop */
}
/* end of func */

以上的例子算法是老谭书上的,但是有需要改进的地方。
下面的例子就是改进后的例子。
[/code]
void selectSort(int A[],int n)
{
int x;
int i,j,k;

for(i=0;i<n;i++)
{
k = i;
for(j=i+1;j<n;j++)
{
if(A[j]<A[k]) k = j;
}
if(k!=i)
{
x=A;
A=A[k];
A[k]=x;
} /* end of if */
} /* end of outer loop */
} /* end of func */


[/code]
------
回复此文章 |

main()
{
int A[] = {36,25,48,12,65,43,20,58};
void bubbleSort(int A[],int n);
int n,k;
for( k=0;k<8;k++)
{
printf(
"%d \t",A[k]);
}
printf(
"\n");
n = 8;
printf(
"%d\n",n);
bubbleSort(A,8);
// show outcome
for( k=0;k<8;k++)
{
printf(
"%d \t",A[k]);
}
printf(
"\n");
}
// end of main


void bubbleSort(int A[],int n)
{
int x;
int i,j,flag;

for(i=1;i<n;i++)
{
flag=0;
for(j=n-1;j>=i;j--)
{
if(A[j]<A[j-1])
{
x = A[j-1];
A[j-1] = A[j];
A[j] = x;
flag = 1;
}
/* end of if */
}
/* end of inner loop */
if(flag == 0) return;
}
/* end of outer loop */
}
/* end of func */





回复此文章 |

main()
{
int A[] = {36,25,48,12,65,43,20,58};
void shellSort(int A[],int n);
int n,k;
for( k=0;k<8;k++)
{
printf(
"%d \t",A[k]);
}
printf(
"\n");
n = 8;
printf(
"%d\n",n);
shellSort(A,8);
// show outcome
for( k=0;k<8;k++)
{
printf(
"%d \t",A[k]);
}
printf(
"\n");
}
// end of main


void shellSort(int A[],int n)
{
int x;
int i,j,d;

for(d=n/2;d>=1;d/=2)
{
for(i=d;i<n;i++)


hofman   2005-11-19 22:09:51 评论:0   阅读:1048   引用:0

发表评论>>

署名发表(评论可管理,不必输入下面的姓名)

姓名:

主题:

内容: 最少15个,最长1000个字符

验证码: (如不清楚,请刷新)

Copyright@2004-2010 powered by YuLog