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

为了配合大家学习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++)