bubblesort template.cpp

用vs2005实现了一个冒泡排序的模板

// bubblesort template.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;
template<class T>
void bubblesort(T A[],int n)
{
  int i;
  T temp;
  //一共作n-1趟排序
  for(i=1;i<n;i++)
	  //第i趟比较的次数是n-i
	  for(int j=0;j<n-i;j++)
	  {
		  if(A[j]>A[j+1])
		  {
		    temp=A[j];
			A[j]=A[j+1];
			A[j+1]=temp;
		  }
	  }
}
//冒泡排序改进算法
template<class T>
void quickBubbleSort(T A[],int n)
{
   int i,j,lastExchangeIndex;
   T temp;
   i=n-1;
   //没趟初始，lastExchangeIndex值为0
   //lastExchangeIndex用于记录每趟最后交换元素的元素的索引值，
   //每趟开始时，把lastExchangeIndex的值赋给i
   //以减少不必要的比较次数
   //"8 4 2 7 9 10",则第二趟只需比较到7就可以了
   
   while(i>0)
   {
	   lastExchangeIndex=0;
      for(j=0;j<i;j++)
	   {
	     if(A[j+1]<A[j])
		 {
		     temp=A[j];
			 A[j]=A[j+1];
			 A[j+1]=temp;
			 lastExchangeIndex=j;
		 }
	   }
	   i=lastExchangeIndex;
   }
}
int _tmain(int argc, _TCHAR* argv[])
{
	int A[10];
	int i;
	//数组初始化
	for(i=0;i<10;i++)
		A[i]=10-i;
	//输出原始数组
	for(i=0;i<10;i++)
		cout<<A[i]<<" ";
	cout<<endl;
	quickBubbleSort(A,10);
     //bubblesort(A,10);
	//输出排序后的数组
	for(i=0;i<10;i++)
		cout<<A[i]<<" ";
	cout<<endl;

	return 0;
}