C++常用排序算法

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

//选择排序法SelectionSort(int arr[],int n)

template <typename T>

void SelectionSort(T arr[],int n)

{

int smallIndex; //表中最小元素的下标

int pass,j; //用来扫描子表的下标

T temp; //用来交换表元素的临时变量

//pass的范围是0~n-2

for (pass=0;pass<n-1;pass++)

{

//从下标pass开始扫描子表

smallIndex=pass;

//j遍历整个子表arr[pass+1]到arr[n-1]

for(j=pass+1;j<n;j++)

//如果找到更小的元素,则将该位置赋值给smallIndex

if(arr[j]<arr[smallIndex])

smallIndex=j;

//如果smallIndex和pass不在相同的位置

//则将子表中的最小项与arr[pass]交换

if(smallIndex!=pass)

{

temp=arr[pass];

arr[pass]=arr[smallIndex];

arr[smallIndex]=temp;

}

}

}

/************************************************************************

双端选择排序算法:是上面选择排序算法的变种,可以定位每个子表中最小和最大元素

并把它们分别放在子表的开头和结尾.

************************************************************************/

//双端选择排序算法函数deSelSort()的实现

template <typename T>

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<rightPass;i++)

//如果找到更小的元素,则将该位置赋值给smallIndex

if (arr[i]<arr[smallIndex])

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;

if(largeIndex!=rightPass)

{

temp=arr[rightPass];

arr[rightPass]=arr[largeIndex];

arr[largeIndex]=temp;

}

//从两头收缩子表

leftPass++;

rightPass--;

}

}

//自编冒泡法排序算法函数bubbleSort()的实现

template <typename T>

int bubbleSort(T arr[],int n)

{

bool exchanged=false; //是否发生交换

int i,j; //用于遍历子表的下标

T temp; //用于交换元素的临时变量

//开始遍历过程,以下标j构成子表,共有n-1个子表

for (j=n-1;j>=0;j--) //j从后往前收缩n-1~0,以构成子表0~n-1,0~n-2,0~n-3..0~1

{

exchanged=false;

for (i=0;i<j;i++) //遍历子表范围0~j

{

if (arr[i]>arr[i+1])

{

temp=arr[i];

arr[i]=arr[i+1];

arr[i+1]=temp;

exchanged=true;

}

}

if (!exchanged) return n-j-1;//如果在一次遍历中没有发生交换,则表示已经

//排序好,中断遍历过程

}

return n-1-j;

}

//冒泡法排序一般算法函数bubbleSortEx()的实现

template <typename T>

int bubbleSortEx(T arr[],int n)

{

int i,pass; //用于遍历子表的下标

T temp; //用于交换元素的临时变量

//开始遍历过程,以下标j构成子表,共有n-1个子表

for (pass=0;pass<n;pass++) //pass从后往后扩大0~n-1,以构成子表0~n-1,0~n-2,0~n-3..0~1

{

for (i=0;i<n-pass;i++) //遍历子表范围0~n-pass

{

if (arr[i]>arr[i+1])

{

temp=arr[i];

arr[i]=arr[i+1];

arr[i+1]=temp;

}

}

}

return pass;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有  導航