//选择排序法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;}

评论