list.h

基于c++的数据结构源代码。是学习数据结构的很好的demo

#include<iostream.h>
#include<iomanip.h>
#include<math.h>
#include<stdlib.h>
template<class T>
void BubbleSort(T array[],int size)// 1冒泡排序
{
	int i;
	T temp;
	for(int pass=1;pass<size;pass++)
	{
		for(i=0;i<size-pass;i++)
		if(array[i]>array[i+1])
		{
			temp=array[i];
			array[i]=array[i+1];
			array[i+1]=temp;
		}
	}
}
template<class T>
void InsertSort(T array[],int size)// 2插入排序
{
	T inserter;
	int index;
	for(int i=1;i<size;i++)
	{
		inserter=array[i];
		index=i-1;
		while(index>=0&&inserter<array[index])
		{
			array[index+1]=array[index];
			index--;
		}
		array[index]=inserter;
	}
}

template<class T>
void QuickSort(T array[],int left,int right)// 3快速排序
{
	T pivot,temp;
	int l=left;
	int r=right;
	pivot=array[(left+right)/2];//取中作为分界值
	while(l<r)
	{
		while(array[l]<pivot)
			++l;
		while(array[r]>pivot)
			--r;
		if(l>=r)
			break;
		temp=array[l];
		array[l]=array[r];
		array[r]=temp;
		if(l!=pivot)
			--r;
		if(r!=pivot)
			++l;
	}
	if(l==r)
		l++;
	if(left<r)
		QuickSort(array,left,l-1);
	if(l<right)
		QuickSort(array,r+1,right);
}

template<class T>
void SelectSort(T array[],int size)// 4选择排序
{
   int smallIndex;   
   int i, j;
   for (i = 0; i < size-1; i++) 
   {
      smallIndex = i;   
      for (j = i+1; j <size; j++) 
         if (array[j] < array[smallIndex])
            smallIndex = j;
   
      swap(array[i], array[smallIndex]);
   }
}

template<class T>
void ShellSort(T array[],int size)// 5希尔排序
{
	T x;
	int i,j,d;
	for(d=size/2;d>=1;d/=2)
	{
		for(i=d;i<size;i++)
		{
			x=array[i];
			for(j=i-d;j>=0;j-=d)
			{
				if( x<array[j])
					array[j+d]=array[j];
				else
					break;
			}
			array[j+d]=x;
		}
	}
}
template<class T>
void swap(T&a,T&b)
{
	T temp;
	temp=a;
	a=b;
	b=temp;
}