データ構造_内部ソート_ヒルソート_クイックソート_ヒープのソート_集計ソート_アドレスソート

いくつかの典型的なソートアルゴリズムは、アルゴリズムのソート対象が順序テーブルであり、もう1つの基数ソートアルゴリズムは、異なるストレージ構造を採用しているため、このファイルに追加されていないため、後でコードが貼られます.
"sort.h"

#include<iostream>
#include<ctime>
using namespace std;

typedef int ElemType;

#define LISTLEN 100

typedef struct SqList//   
{
	ElemType *elem;
	int length;
	int listsize;
}SqList;

void InitList(SqList &L)//      
{
	L.elem=new ElemType[LISTLEN+1];
	L.length=0;
	L.listsize=LISTLEN;
}

void InitList(SqList &L,int len)//     
{
	L.elem=new ElemType[len+1];
	L.length=0;
	L.listsize=len;
}

void GetRandomNum(SqList &L)//     
{
	srand((unsigned)time(NULL));
	for(int i=0;i<L.listsize;i++)
		L.elem[i]=rand()%100;
	L.length=L.listsize;
}

void GetRandomNum(SqList &L,int randombase)//     
{
	srand((unsigned)time(NULL));
	for(int i=0;i<L.listsize;i++)
		L.elem[i]=rand()%randombase;
	L.length=L.listsize;
}

void PrintList(SqList &L)//       
{
	for(int i=0;i<L.length;i++)
		cout<<L.elem[i]<<" ";
	cout<<endl;
}

/////////////////////////////////////////////////////////////    

void ShellInsert(SqList&L,int dk)//    dk    
{
	ElemType temp;
	int j;
	for(int i=dk;i<L.length;i++)
	{
		if(L.elem[i]<L.elem[i-dk])
			{
				temp=L.elem[i];
				j=i-dk;
				while(j>=0&&temp<L.elem[j])
				{
					L.elem[j+dk]=L.elem[j];
					L.elem[j]=temp;
					j-=dk;	
				}	
			}
	}
}

void ShellSort(SqList &L,int dlta[],int t)//    
{
	for(int k=0;k<t;k++)
	{
		ShellInsert(L,dlta[k]);
	}
}

/////////////////////////////////////////////////////////////    

int Partition(SqList &L,int low,int high)
{
	ElemType temp;
	temp=L.elem[(low+high)/2];
	while(low<high)
	{
		while(low<high&&L.elem[high]>=temp) high--;
		L.elem[low]=L.elem[high];
		while(low<high&&L.elem[low]<=temp) low++;
		L.elem[high]=L.elem[low];
	}
	L.elem[low]=temp;
	return low;
}

void QuickSort(SqList &L,int low,int high)
{
	if(low<high)
	{
		int pivotkey=Partition(L,low,high);
		QuickSort(L,low,pivotkey-1);
		QuickSort(L,pivotkey+1,high);
	}
}

void Qsort(SqList &L)
{
	QuickSort(L,0,L.length-1);
}

/////////////////////////////////////////////////////////////   

typedef SqList HeapType;

/////////////////////////////////////////////////////////////
//           ，              ，       ...
void ListAdjust(HeapType &H)//                   
{
	for(int i=H.length-1;i>=0;i--)
		H.elem[i+1]=H.elem[i];
}

void ListReAdjust(HeapType &H)//                   
{
	for(int i=0;i<H.length-1;i++)
		H.elem[i]=H.elem[i+1];
}
///////////////////////////////////////////////////////////////

void HeapAdjust(HeapType &H,int s,int m)
//  H.elem[s...m] H.elem[s]        
//     H.elem[s]     H.[s...m]       
{
	ElemType temp=H.elem[s];//     
	for(int i=2*s;i<=m;i*=2)//  
	{
		if(i<m&&(H.elem[i]<H.elem[i+1]))
		//                
			i++;//“  ”      
		if(temp>=H.elem[i])//          
			break;
		H.elem[s]=H.elem[i];//       
		s=i;
	}
	H.elem[s]=temp;
}

void HeapSort(HeapType &H)
{
	ListAdjust(H);//             
	ElemType temp;
	for(int i=H.length/2;i>0;i--)//     
		HeapAdjust(H,i,H.length);
	for(int i=H.length;i>1;i--)//                   
	{
		temp=H.elem[i];
		H.elem[i]=H.elem[1];
		H.elem[1]=temp;
		HeapAdjust(H,1,i-1);//   H.elem[1...i-1]      
	}
	ListReAdjust(H);//                   
}

///////////////////////////////////////////////////////////////    
/*
       N 
            
        
             
*/
void Merge(ElemType *L,ElemType *T,int left,int mid,int right)
//     T[left...mid],T[mid+1...right]      L[left...right]
{
	for(int i=left;i<=right;i++)//    
		T[i]=L[i];
	int i=left,j=mid+1,k=left;
	//  
	while(i<=mid&&j<=right)
	{
		if(T[i]<=T[j])
			L[k++]=T[i++];
		else
			L[k++]=T[j++];
	}
	while(i<=mid)
		L[k++]=T[i++];
	while(j<=right)
		L[k++]=T[j++];
}

void MSort(ElemType *L,ElemType *T,int left,int right)
	// T[left...right]     L[left..right]
{
	if(left<right)
	{
		int mid=(left+right)/2;//  
		MSort(L,T,left,mid);//    
		MSort(L,T,mid+1,right);//    
		Merge(L,T,left,mid,right);//    
	}
}

void MergeSort(SqList &L)
{
	ElemType t[LISTLEN];
	MSort(L.elem,t,0,L.length-1);
}

////////////////////////////////////////////////////////////////    

void ReArrange(SqList &L,int adr[])
//adr     L     ， L.elem[adr[i]]  i    
//    adr  L.elem    
{
	ElemType temp;
	int j,k;
	for(int i=0;i<L.length;i++)
	{
		if(adr[i]!=i)
		{
			temp=L.elem[i];
			j=i;
			while(adr[j]!=i)
			{
				k=adr[j];
				L.elem[j]=L.elem[k];
				adr[j]=j;
				j=k;
			}
			L.elem[j]=temp;
			adr[j]=j;
		}
	}
}

void AdrSort(SqList &L)
//    L         adr[]
{
	int adr[LISTLEN+1];
	int temp;
	for(int i=0;i<L.length;i++)
		adr[i]=i;
	for(int i=0;i<L.length-1;i++)
	{
		for(int j=i+1;j<L.length;j++)
		{
			if(L.elem[adr[i]]>L.elem[adr[j]])
			{
				temp=adr[i];
				adr[i]=adr[j];
				adr[j]=temp;
			}
		}
	}
	ReArrange(L,adr);
}

"main.cpp"

#include"sort.h"

int main()
{
	SqList L;//   
//	InitList(L);//               100
	InitList(L,10);//                      
//	int dlta[10]={5,3,1};//      
	GetRandomNum(L);//              0~99
//	GetRandomNum(L,10);//                       
	PrintList(L);//  
//	Qsort(L);
//	ShellSort(L,dlta,3);//    L      
//	HeapSort(L);
	MergeSort(L);
//	AdrSort(L);
	PrintList(L);//  
	system("pause");
}