list.h

来自「基于c++的数据结构源代码。是学习数据结构的很好的demo」· C头文件 代码 · 共 120 行

#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;

   // sort A[0]..A[n-2], and A[n-1] is in place
   for (i = 0; i < size-1; i++) 
   {
      smallIndex = i;    //最小元素之下标初值设为i
      // 在元素A[i+1]..A[n-1]中逐个比较显出最小值
      for (j = i+1; j <size; j++) 
         // smallIndex始终记录当前找到的最小值的下标
         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)//以d(i+1)=d(i)/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;//将array[i]的值放入到合适位置
		}
	}
}
template<class T>
void swap(T&a,T&b)
{
	T temp;
	temp=a;
	a=b;
	b=temp;
}