通过代码快速上手C语言数据结构-内部排序

太过爱你忘了你带给我的痛 2023-01-16 02:41 121阅读 0赞

# 9.1直接插入排序 #

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    void   InsSort(RecordType  r[],  int length)
    /* 对记录数组r做直接插入排序，length为数组中待排序记录的数目*/
    { 
    	int i,j;
    	for (i=2;  i<=length;  i++) 
    	{
    		r[0]=r[i];      /*将待插入记录存放到监视哨r[0]中*/
    		j=i-1;	         
    		while (r[0].key< r[j].key )     /* 寻找插入位置 */
    		{
    			r[j+1]= r[j]; 
    			j=j-1;
    		}
    		r[j+1]=r[0];		         /*将待插入记录插入到已排序的序列中*/
    	}
    } /*  InsSort  */ 
    
    void main()
    {
    	int i,j;
    	RecordType r[20];
    	int len;
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=1;i<=len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i].key = j;
    	}
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    
    	InsSort(r,len);
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    
    }

# 9.2折半插入排序 #

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    void    BinSort (RecordType  r[],  int length)
    /*对记录数组r进行折半插入排序，length为数组的长度*/
    {
    	int i,j;
    	RecordType x;
    	int low,high,mid;
    	for (  i=2; i<=length ; ++i ) 
    	{
    		x= r[i];
    		low=1;  high=i-1;
    		while (low<=high )                  /* 确定插入位置*/ 
    		{
    			mid=(low+high) / 2;
    			if (  x.key< r[mid].key   )    
    				high=mid-1;
    			else 
    				low=mid+1;
    		}
    		for (  j=i-1 ; j>= low; --j )   r[j+1]= r[j];         /*  记录依次向后移动 */ 
    		r[low]=x;                                                            /* 插入记录 */ 
    	}
    }/*BinSort*/
    
    
    void main()
    {
    	int i,j;
    	RecordType r[20];
    	int len;
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=1;i<=len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i].key = j;
    	}
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    	BinSort(r,len);
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    }

# 9.3希尔排序 #

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    void  ShellInsert(RecordType r[], int length,  int  delta)
    /*对记录数组r做一趟希尔插入排序，length为数组的长度,delta 为增量*/
    {
    	int i,j;
    	for(i=1+delta;i<= length; i++)      /* 1+delta为第一个子序列的第二个元素的下标 */
    		if(r[i].key < r[i-delta].key)
    		{
    			r[0]= r[i];           /*  备份r[i]  (不做监视哨) */
    				for(j=i-delta; j>0 &&r[0].key < r[j].key; j-=delta)
    					r[j+delta]= r[j];
    					r[j+delta]= r[0];
    		}
    }/*ShellInsert*/
    
    void  ShellSort(RecordType r[], int length, int delt[], int n)
    /*对记录数组r做希尔排序，length为数组r的长度，delta 为增量数组，n为delta[]的长度 */
    { 
    	int i;
    	for(i=0 ;  i<=n-1;  ++i)
    		ShellInsert(r, length, delt[i]);
    }
    
    
    void main()
    {
    	int i,j;
    	RecordType r[20];
    	int len;
    	int delta[3]={4,2,1};
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=1;i<=len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i].key = j;
    	}
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    	ShellSort(r,len,delta,3);
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    }

# 9.4冒泡排序法 #

#include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    
    typedef int KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    void  BubbleSort(RecordType r[], int length )
    /*对记录数组r做冒泡排序，length为数组的长度*/
    {
    	int n,i,j;
    	int change;
    	RecordType x;
    	n=length;  
    	change=TRUE;
    		for ( i=1 ; i<= n-1 && change ;++i ) 
    		{
    			change=FALSE;
    				for ( j=1 ; j<= n-i ; ++j) 
    					if (r[j].key > r[j+1].key )  
    					{
    						x= r[j];
    						r[j]= r[j+1];
    						r[j+1]= x;
    						change=TRUE;
    					} 
    		}
    } /*  BubbleSort  */ 
    
    
    void main()
    {
    	int i,j;
    	RecordType r[20];
    	int len;
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=1;i<=len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i].key = j;
    	}
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    	BubbleSort(r,len);
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    }

# 9.5-9.6快速排序 #

*  ### 9.5快速排序 ###
 *  ### 9.6—趟快速排序 ###

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    int   QKPass(RecordType r[],int left,int right)
    /*对记录数组r 中的r[left]至r[right]部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/
    { 
    	RecordType x;
    	int low,high;
    	x= r[left];             /* 选择基准记录*/ 
    	low=left;  
    	high=right;
    	while ( low<high )
    	{
    		while (low< high && r[high].key>=x.key ) 
    			/* high从右到左找小于x.key的记录 */
    			high--;
    		if ( low <high ) 
    		{ 
    			r[low]= r[high];
    			low++;
    		}  
    		/* 找到小于x.key的记录，则进行交换*/
    		while (low<high && r[low].key<x.key  )    /* low从左到右找大于x.key的记录 */
    			low++; 
    		if (  low<high  )
    		{ 
    			r[high]= r[low];
    			high--; 
    		} /* 找到大于x.key的记录，则交换*/
    	}
    	r[low]=x;                     /*将基准记录保存到low=high的位置*/
    	return low;                     /*返回基准记录的位置*/
    } /* QKPass */ 
    
    
    void QKSort(RecordType r[],int low, int high )
    /*对记录数组r[low..high]用快速排序算法进行排序*/
    {
    	int pos;
    	if(low<high)
    	{
    		pos=QKPass(r, low, high);  /*调用一趟快速排序，将枢轴元素为界划分两个子表*/
    		QKSort(r, low, pos-1);     /*对左部子表快速排序*/
    		QKSort(r, pos+1, high); /*对右部子表快速排序*/
    		
    	}
    }
    
    
    void main()
    {
    	int i,j;
    	RecordType r[20];
    	int len;
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=1;i<=len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i].key = j;
    	}
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	QKSort(r,1,len);
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    }

# 9.7简单选择排序 #

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    void  SelectSort(RecordType r[], int length)
    /*对记录数组r做简单选择排序，length为数组的长度*/
    {
    	int i,j,k;
    	int n;
    	RecordType x;
        n=length;
    	for ( i=1 ; i<= n-1; ++i)  
    	{
    		k=i;
    		for ( j=i+1 ; j<= n ; ++j) 
    			if (r[j].key < r[k].key ) 
    				k=j;
    			if ( k!=i) 
    			{ 
    				x= r[i]; 
    				r[i]= r[k];
    				r[k]=x;
    			}
    	}
    	
    } /* SelectSort  */ 
    
    
    void main()
    {
    	int i,j;
    	RecordType r[20];
    	int len;
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=1;i<=len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i].key = j;
    	}
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    	SelectSort(r,len);
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    }

# 9.8-9.10堆排序 #

*  ### 9.8调整堆 ###
 *  ### 9.9建初堆 ###
 *  ### 9.10堆排序 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    
    typedef int KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    void   sift(RecordType  r[],  int k, int m)
    /* 假设ｒ[k..m]是以ｒ[k]为根的完全二叉树，且分别以ｒ[2k]和ｒ[2k+1]为根的左、右子树为大根堆，调整r[k]，使整个序列r[k..m]满足堆的性质 */
    {
    	RecordType t;
    	int i,j;
    	int x;
    	int finished;
    	t= r[k];          /* 暂存"根"记录r[k] */ 
    	x=r[k].key;
    	i=k;
    	j=2*i;
    	finished=FALSE;
    		while( j<=m && !finished  ) 
    		{     
    		if (j<m  && r[j].key< r[j+1].key ) 
    		j=j+1;  /* 若存在右子树，且右子树根的关键字大，则沿右分支"筛选" */
    		if ( x>= r[j].key)
    			finished=TRUE;            /*  筛选完毕  */ 
    		else 
    		{
    			r[i] = r[j];
    			i=j;
    			j=2*i;
    		}    /* 继续筛选 */ 
    		}
    		r[i] =t;          /* r[k]填入到恰当的位置 */ 
    }  
    
    void   crt_heap(RecordType r[], int length )
    /*对记录数组r建堆，length为数组的长度*/
    {
    	int i,n;
        n= length;
    	for ( i=n/2; i >= 1; --i)         /* 自第[n/2]个记录开始进行筛选建堆 */ 
    		sift(r,i,n);
    }
    
    void  HeapSort(RecordType  r[],int length)
    /* 对r[1..n]进行堆排序，执行本算法后，r中记录按关键字由大到小有序排列 */ 
    {
    	int i,n;
    	RecordType b;
    	crt_heap(r, length);
    		n= length;
    	for (  i=n ; i>= 2; --i) 
    	{
    		b=r[1];              /* 将堆顶记录和堆中的最后一个记录互换 */ 
    		r[1]= r[i];
    		r[i]=b; 
    		sift(r,1,i-1);  /* 进行调整，使r[1..i-1]变成堆 */ 
    	}
    } /* HeapSort */ 
    
    
    void main()
    {
    	int i,j;
    	RecordType r[20];
    	int len;
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=1;i<=len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i].key = j;
    	}
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    	HeapSort(r,len);
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    }

# 9.11-9.13归并排序 #

*  ### 9.11相邻两个有序子序列的合并 ###
 *  ### 9.12归并排序的递归 ###
 *  ### 9.13归并排序的初始调用过程 ###

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int KeyType;
    typedef int OtherType;
    
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    
    void Merge(RecordType r1[],  int low,   int mid,   int high,  RecordType  r2[])
    /* 已知r1[low..mid]和r1[mid+1..high]分别按关键字有序排列，将它们合并成一个有序序列，存放在r2[low..high] */
    { 
    	int i,j,k;
    	i=low;
    	j=mid+1;
    	k=low;
    	while ( (i<=mid)&&(j<=high)  )
    	{
    		if ( r1[i].key<=r1[j].key )
    		{
    			r2[k]=r1[i];
    			++i;
    		}
    		else 
    		{
    			r2[k]=r1[j];
    			++j;
    		}
    		++k;
    	}
    	while( i<=mid )
    	{
    		r2[k]=r1[i];
    		k++;
    		i++;
    	}
    	while( j<=high)
    	{
    		r2[k]=r1[j];
    		k++;
    		j++;
    	}
    } /* Merge */ 
    
    void   MSort(RecordType  r1[],  int  low,  int  high,  RecordType  r3[])
    /* r1[low..high]经过排序后放在r3[low..high]中，r2[low..high]为辅助空间 */ 
    {
    	int mid;
    	RecordType  r2[20];
    	if ( low==high ) 
    		r3[low]=r1[low];
    	else
    	{
    		mid=(low+high)/2;
            MSort(r1,low, mid, r2);
            MSort(r1,mid+1,high, r2);
            Merge (r2,low,mid,high, r3);
    }
    } /*   MSort  */ 
    
    void   MergeSort ( RecordType  r[],  int  n )
    /* 对记录数组r[1..n]做归并排序 */ 
    {
    	MSort ( r,  1,  n,  r );
    }
    
    
    void main()
    {
    	int i,j;
    	RecordType r[20];
    	int len;
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=1;i<=len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i].key = j;
    	}
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	MergeSort(r,len);
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key);
    	printf("\n");
    	
    }

# 9.14链式基数排序 #

#include <stdio.h>
    #include <stdlib.h>
    
    #define RADIX 10
    #define KEY_SIZE 6
    #define LIST_SIZE 20
    
    typedef int KeyType;
    typedef int OtherType;
    
    typedef struct 
    {
    	KeyType key[KEY_SIZE];      /* 子关键字数组 */ 
    	OtherType other_data;        /* 其它数据项 */ 
    	
    	int  next;                   /* 静态链域 */ 
    } RecordType1;
    
    typedef struct 
    {
    	RecordType1  r[LIST_SIZE+1];  /* r[0]为头结点 */
    	int length;
    	int keynum;
    }SLinkList;                  /* 静态链表 */
    
    typedef int PVector[RADIX];
    
    void   Distribute(RecordType1 r[],  int  i,  PVector head,  PVector tail)
    /*  记录数组r中记录已按低位关键字key[i+1]，…，key[d]进行过"低位优先"排序。本算法按第i位关键字key[i]建立RADIX个队列，同一个队列中记录的key[i]相同。head[j]和tail[j]分别指向各队列中第一个和最后一个记录（j=0，1，2，…，RADIX-1）。head[j]=0表示相应队列为空队列*/ 
    {
    	int j;
    	int p;
    	for ( j=0 ; j<=RADIX-1 ; ++j)
    		head[j]=0;                        /*  将RADIX个队列初始化为空队列 */ 
    		p= r[0].next;                    /*  p指向链表中的第一个记录 */ 
    		while( p!=0 ) 
    		{
    			j=r[p].key[i];          /* 用记录中第i位关键字求相应队列号 */
    			if  ( head[j]==0 ) 
    				head[j]=p;    /* 将p所指向的结点加入第j个队列中 */ 
    			else
    				r[tail[j]].next=p;
    			tail[j]=p;
    			p= r[p].next;
    		}
    } /*  Distribute  */ 
    
    void  Collect(RecordType1  r[],  PVector head,  PVector tail)
    /* 本算法从0到RADIX-1 扫描各队列，将所有非空队列首尾相接，重新链接成一个链表 */ 
    {
    	int j;
    	int t;
    	j=0;
    	while (head[j]==0 )                 /* 找第一个非空队列 */ 
    		++j;
    	r[0].next =head[j];
    	t=tail[j];
    	while ( j<RADIX-1 )                 /* 寻找并串接所有非空队列 */
    	{
    		++j;
    		while ( (j<RADIX-1 ) && (head[j]==0 ) )     /* 找下一个非空队列 */ 
    			++j;
    		if ( head[j]!=0 )       /* 链接非空队列 */ 
    		{
    			r[t].next =head[j];
    			t=tail[j];
    		} 
    	}
    	r[t].next =0;             /* t指向最后一个非空队列中的最后一个结点 */ 
    }   /* Collect */ 
    
    void  RadixSort (RecordType1 r[],int length )
    /* length个记录存放在数组r中，执行本算法进行基数排序后，链表中的记录将按关键字从小到大的顺序相链接。 */ 
    {
    	int i,n;
    	int d;
    	PVector head;
    	PVector tail;
        n= length;
    	for ( i=0 ; i<= n-1 ; ++i)  
    		r[i].next=i+1;  /* 构造静态链表 */
    	r[n].next =0;
    	d= 3;
    	for ( i =d-1; i>= 0; --i )       /* 从最低位子关键字开始，进行d趟分配 和 收集*/
    	{ 
    		Distribute(r,i,head,tail);  /* 第i趟分配 */ 
    		Collect(r,head,tail);       /* 第i趟收集 */ 
    	}
    }  /* RadixSort  */
    
    void main()
    {
    	int i,j;
    	RecordType1 r[20];
    	int len;
    	int p;
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=1;i<=len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i].key[0] = j/100;
    		r[i].key[1] = (j-100*r[i].key[0])/10;
    		r[i].key[2] =(j-100*r[i].key[0]-10*r[i].key[1]);
    	}
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key[0]*100+r[i].key[1]*10+r[i].key[2]);
    	printf("\n");
    	
    	RadixSort(r,len);
    	p = r[0].next;
    	while(p!=0)
    	{
    		printf("%d  ",r[p].key[0]*100+r[p].key[1]*10+r[p].key[2]);
    		p = r[p].next;
    	}
    	printf("\n");
    	for(i=1;i<=len;i++)
    		printf("%d  ",r[i].key[0]*100+r[i].key[1]*10+r[i].key[2]);
    	printf("\n");
    	
    }

# 9.15荷兰国旗问题 #

#include <stdio.h>
    #include <stdlib.h>
    
    
    /*
    void Sort (int L[],  int n)
    / * 条块颜色依次存放在L[0..n-1]中，本算法利用简单选择排序思想，将整个序列按红、白、蓝进行排序。* /
    {
    	int  i, j, x;
    	i=0; 	/ * i指向第一个红色条块应该放的位置 * /
    	for (j=i;  j<n;  j++)         / * j扫描所有尚未放置好的条块，寻找红色条块 * /
    	{	if (L[j]==1)               / * 找到一个红色条块* /
    		{
    			if (j!=i)             / * 找到的红色条块不在下一个红色条块应该放的位置则换位* /
    			{
    				x=L[j];
    				L[j]=L[i];
    				L[i]=x;
    			}
    			i++;               / * i指向下一个红色条块应该放的位置 * /
    		}
    	}
    	/ * 退出前面循环后，i指向第一个白色条块应该放的位置 * /
    	for(j=i;  j<n;  j++)        / * j扫描所有尚未放置好的条块，寻找白色条块 * /
    		if (L[j]==2)              / * 找到一个白色条块* /
    		{
    			if (j!=i)             / * 找到的白色条块不在下一个白色条块应该放的位置则换位* /
    			{
    				x= L[j];
    				L[j]= L[i];
    				L[i]=x;
    			}
    			i++;                  / * i指向下一个白色条块应该放的位置 * /
    		}
    }*/
    
    
    
    void Sort (int L[],  int n)
    /* 条块颜色依次存放在L[0..n-1]中，本算法利用快速排序思想，将整个序列按红、白、蓝进行排序。*/
    {
    	int  x;
    	int  r;          /* r指向红色条块区的下一个单元（同时也是白色条块区的第一个单元）*/
    	int  w;        /* w指向白色条块区的下一个单元（同时也相当于快速排序中的low指针）*/
    	int  b;         /* b指向蓝色条块区的前一个单元（同时也相当于快速排序中的high指针）*/
    	r=w=0;                           /* 相当于low=0 */
    	b=n-1;                           /* 相当于high=n-1 */
    	while (w<=b)
    	{
    		x=L[w];
    		if (x==1)           /*  L[w]是红色条块，并且在白色条块区的下一个单元 */
    		{
    			L[w]= L[r];         /*  L[r]是第一个白色条块，将其移到白色条块区最后 */
    			w++;                /*  w指向白色条块区的下一个单元*/
    			L[r]=x;             /*  将红色条块x放到红色条块区的下一个单元*/
    			r++;               /* r指向红色条块区的下一个单元*/
    		}
    		else
    			if (x==2)     /*  L[w]是白色条块，并且恰好在白色条块区的下一个单元 */
    				w++;              /*  w指向白色条块区的下一个单元*/
    			else
    			{              /*  L[w]是蓝色条块*/
    				L[w]= L[b];    /*  b指向蓝色条块区的前一个单元，将L[b]与L[w]交换 */
    				L[b]=x;
    				b--;                /* b指向蓝色条块区的前一个单元*/
    			}
    	}
    }
    
    
    void main()
    {
    	int i,j;
    	int r[20];
    	int len;
    	printf("请输入待排序记录的长度:");
    	scanf("%d",&len);
    	for(i=0;i<len;i++)
    	{
    		printf("请输入第%d个记录元素:",i);
    		fflush(stdin);
    		scanf("%d",&j);
    		r[i] = j;
    	}
    	for(i=0;i<len;i++)
    		printf("%d  ",r[i]);
    	printf("\n");
    	
    	Sort(r,len);
    	for(i=0;i<len;i++)
    		printf("%d  ",r[i]);
    	printf("\n");
    	
    }