计算机等级考试二级辅导c 常用排序算法

文章作者 100test 发表时间 2007:03:10 16:50:23
来源 100Test.Com百考试题网

//选择排序法SelectionSort(int arr[],int n)
template
void SelectionSort(T arr[],int n)
{
int smallIndex. //表中最小元素的下标
int pass,j //用来扫描子表的下标
T temp. //用来交换表元素的临时变量

//pass的范围是0~n-2
for (pass=0.pass{
//从下标pass开始扫描子表
smallIndex=pass.

//j遍历整个子表arr[pass 1]到arr[n-1]
for(j=pass 1.j //如果找到更小的元素,则将该位置赋值给smallIndex
if(arr[j] smallIndex=j.
//如果smallIndex和pass不在相同的位置
//则将子表中的最小项与arr[pass]交换
if(smallIndex!=pass)
{
temp=arr[pass].
arr[pass]=arr[smallIndex].
arr[smallIndex]=temp.
}
}
}

/************************************************************************
双端选择排序算法:是上面选择排序算法的变种,可以定位每个子表中最小和最大元素
并把它们分别放在子表的开头和结尾.
************************************************************************/
//双端选择排序算法函数deSelSort()的实现
template
void deSelSort(T arr[],int n)
{
int smallIndex,largeIndex. //表中最小及最大元素的下标
int leftPass=0,rightPass=n-1,i,j.//用来从表左边及右边扫描子表的下标
T temp. //用于交换元素的临时变量

while (leftPass<=rightPass)
{
//从左边及右边开始扫描子表
smallIndex=leftPass.
largeIndex=rightPass.
//j和i遍历整个子表arr[LeftPass]~arr[rightPass]
for (i=leftPass 1.i //如果找到更小的元素,则将该位置赋值给smallIndex
if (arr smallIndex=i.

//如果smallIndex和leftPass不在相同的位置
//则将子表中的最小项与arr[pass]交换
if (smallIndex!=leftPass)
{
temp=arr[leftPass].
arr[leftPass]=arr[smallIndex].
arr[smallIndex]=temp.

}

for (j=rightPass-1.j>leftPass.j--)
if(arr[j]>arr[largeIndex])
largeIndex=j.