欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构——内部排序算法

程序员文章站 2022-03-10 19:55:20
...

实现直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序五种排序算法,并输出排序过程。

假设待排序关键字序列为:{49,38,65,97,76,13,27,49}

main.cpp

#include <malloc.h>
#include <stdio.h> 
#define N 8
#include "Sorting.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
	
	
//	KeyType a[N]={49,38,65,97,76,13,49,27,55,4};
	KeyType a[N]={49,38,65,97,76,13,27,49};
//	KeyType a[N]={1,2,3,4,5,6,7,8};
	
	RecType R[N];
	CreateSort(R,a,N);
	printf("初始关键字:");
	DispSort(R,N);
	
	/****************直接插入排序*************** 
	InsertSort(R,N);
	printf("------------\n"); 
	printf("直接插入排序后结果:");
	DispSort(R,N);
	//*/ 
	
	/****************折半插入排序*************** 
	InsertSort1(R,N);
	printf("------------\n"); 
	printf("折半插入排序后结果:");
	DispSort(R,N);
	//*/ 
	
	/****************希尔排序*************** 
	ShellSort(R,N); 
	printf("------------\n"); 
	printf("希尔排序后结果:");
	DispSort(R,N);
	//*/

	/****************冒泡排序***************	
	BubbleSort(R,N);
	printf("------------\n"); 
	printf("冒泡排序后结果:");
	DispSort(R,N);
	//*/
	
	/**************改进冒泡排序*************	
	BubbleSort1(R,N);
	printf("------------\n"); 
	printf("改进冒泡排序后结果:");
	DispSort(R,N);
	//*/
	
	/****************快速排序*************** 
	QuickSort(R,0,N-1);
	printf("------------\n"); 
	printf("快速排序后结果:");
	DispSort(R,N);
	//*/
	
	//****************简单选择排序***************
	SelectSort(R,N);
	printf("------------\n"); 
	printf("简单选择排序后结果:");
	DispSort(R,N);
	//*/
	
	return 0;
}

Sorting.h

#include <stdio.h> 
//#define  MAXSIZE  20

typedef int KeyType;
typedef char InfoType; 
typedef  struct  {
    KeyType key ;      /*关键字码*/
	InfoType data ;    /*其他域,本例暂存a*/
}RecType; //记录类型

void CreateSort(RecType R[],KeyType a[],int n)
{
	for(int i=0;i<n;i++)
	{
		R[i].key = a[i];
		R[i].data = 'a';	/*其他域,本例暂存a*/
	}
}

void DispSort(RecType R[],int n)
{
	for(int i=0;i<n;i++)
	{
		printf("%3d",R[i].key);
	}
	printf("\n");
} 

//****************直接插入排序*************** 
void InsertSort(RecType R[],int n) 
//对R[0..n-1]按递增有序进行直接插入排序
{	
	int i,j;	
	RecType temp;
	for(i=1;i<n;i++) 
	{
		temp=R[i];
		j=i-1;  //从右向左在有序区R[0..i-1]找R[i]的插入位置
		while(j>=0 && temp.key < R[j].key) 
		{
			R[j+1]=R[j];   //将关键字大于R[i].key的记录后移
			j--;
		}
		R[j+1]=temp;      //在j+1处插入R[i]
		
		//显示各趟排序过程 
		printf("第%d趟直接插入排序:",i); 
		DispSort(R,n);
	}
}
//****************折半插入排序*************** 
void InsertSort1(RecType R[],int n)
{
	int i,j,low,high,mid;
	RecType tmp;
	for(i=1;i<n;i++) 
	{
		tmp=R[i];		   //将R[i]保存到tmp中
		low=0;high=i-1;
		while(low<=high)	   //在R[low..high]中查找插入的位置
		{
			mid=(low+high)/2;		//取中间位置
			if(tmp.key<R[mid].key)
				high=mid-1;			//插入点在左半区
			else
				low=mid+1;			//插入点在右半区
		}
		for(j=i-1;j>=high+1;j--)	//记录后移
			R[j+1]=R[j];
		R[high+1]=tmp;			//插入
		
		//显示各趟排序过程 
		printf("第%d趟折半插入排序:",i); 
		DispSort(R,n);
   }
}
//****************希尔排序******************* 
void ShellSort(RecType R[],int n)	//希尔排序算法
{
	int d=1; 	//排序趟数
	
	int i,j,gap;
	RecType tmp;
	gap=n/2;			  //增量置初值
	while (gap>0)
	{
		for(i=gap;i<n;i++) //对相隔gap位置的元素组直接插入排序
		{
			tmp=R[i];
			j=i-gap;
			while(j>=0 && tmp.key<R[j].key)
			{
				R[j+gap]=R[j];
				j=j-gap;
			}
			R[j+gap]=tmp;
		}
		gap=gap/2;	//减小增量
		
		//显示各趟排序过程 
		printf("第%d趟希尔排序:",d); 
		DispSort(R,n);
		d++; 
	}
}
//****************冒泡排序******************* 
void BubbleSort(RecType R[],int n)
{
	int i,j;
	RecType temp;
	for(i=0;i<n-1;i++) 
	{
		for(j=n-1;j>i;j--)  //比较找本趟最小关键字的记录
			if( R[j].key<R[j-1].key )   
			{
				temp=R[j];    //R[j]与R[j-1]进行交换
				R[j]=R[j-1];
				R[j-1]=temp;
			}
			
		//显示各趟排序过程 
		printf("第%d趟冒泡排序:",i+1); 
		DispSort(R,n);	
	}
} 
//**************改进后的冒泡排序*************
void BubbleSort1(RecType R[],int n)
{	
	int i,j;
	bool exchange;
	RecType temp;
	for(i=0;i<n-1;i++) 
	{
		exchange=false;
		for(j=n-1; j>i; j--)	//比较,找出最小关键字的记录
		if(R[j].key<R[j-1].key)   	
		{
			temp=R[j]; 
			R[j]=R[j-1];
			R[j-1]=temp;
			exchange=true;
		}
		if (exchange==false) return;  //中途结束算法
		
		//显示各趟排序过程 
		printf("第%d趟改进后的冒泡排序:",i+1); 
		DispSort(R,n);
	}
}
//****************快速排序*******************
void QuickSort(RecType R[],int s,int t) 
//对R[s]至R[t]的元素进行快速排序
{
	int i=s,j=t;
	RecType temp;
    if(s<t)         //区间内至少存在2个元素的情况
    {
		temp=R[s];		//用区间的第1个记录作为基准
		while (i!=j)	//从两端交替向中间扫描,直至i=j为止
		{
			while (j>i && R[j].key>=temp.key) j--;  
			R[i]=R[j];
			while (i<j && R[i].key<=temp.key) i++;
			R[j]=R[i];
		}
        R[i]=temp;
        
        //显示各趟排序过程
        printf("以%d为基准,划分[%d-%d]区间:",temp.key,s+1,t+1); 
        DispSort(R,N);
         
        QuickSort(R,s,i-1);    //对左区间递归排序
        QuickSort(R,i+1,t);    //对右区间递归排序
	} 
}

//****************简单选择排序*************** 
void SelectSort(RecType R[], int n)
{
	int i,j,k;
	RecType temp;
	for(i=0;i<n-1;i++)		//做第i趟排序
	{ 
		k=i;
		for(j=i+1; j<n; j++)  //在[i..n-1]中选key最小的R[k] 
			if(R[j].key < R[k].key)
				k=j;           //k记下的最小关键字所在的位置
		if(k!=i)			//交换R[i]和R[k] 
		{
			temp=R[i];
			R[i]=R[k];
			R[k]=temp;
		}
		
		//显示各趟排序过程 
		printf("第%d趟:选择[%d-%d]中最小的记录放到%d:",i+1,i+1,n,i+1); 
		DispSort(R,n);
	}
 }

运行效果:

直接插入排序
数据结构——内部排序算法
希尔排序
数据结构——内部排序算法
冒泡排序
数据结构——内部排序算法
改进冒泡排序
数据结构——内部排序算法
快速排序
数据结构——内部排序算法
简单选择排序
数据结构——内部排序算法

附:各种排序算法的比较

数据结构——内部排序算法

相关标签: 数据结构

上一篇: 第五章 数组

下一篇: 【Mark】栈