设计一个排序和查找系统。能够实现对给定的一组学生的借书证信息（如：卡号、姓名、系别、班号等）进行排序和查找。

男娘i 2021-07-24 22:06 436阅读 0赞

### 目录 ###

*   *   *  实验目的
         *  实验题目
         *  排序模板
         *  实验源代码
         *  实验结果

### 实验目的 ###

了解各种内部排序方法，掌握Shell排序、快速排序、堆排序,归并排序的排序方法，并将其运用到实际问题中。

### 实验题目 ###

设计一个排序和查找系统。能够实现对给定的一组学生的借书证信息（如：卡号、姓名、系别、班号等）进行排序和查找。

### 排序模板 ###

**1.快速排序**

void quick_sort(Node q[], int l, int r) 
    { 
    	if (l >= r) return;
    	int i = l - 1, j = r + 1, x = q[(l + r) / 2].idCard;
    	while (i < j)
    	{ 
    		do i++; while (q[i].idCard < x);
    		do j--; while (q[j].idCard > x);
    		if (i < j)
    		{ 
    			swap(q[i], q[j]);
    		}
    	}
    	quick_sort(q, l, j); quick_sort(q, j + 1, r);
    }

**2.归并排序**

void merge_sort(Node q[],int l,int r) 
    { 
        if(l>=r)  return;
        int mid=l+r>>1;
        merge_sort(q,l,mid);
        merge_sort(q,mid+1,r);
        int k=l,i=l,j=mid+1;
        while(i<=mid&&j<=r)
        { 
            if(q[i].classId<q[j].classId)  tmp[k++]=q[i++];
            else   tmp[k++]=q[j++];
        }
        while(i<=mid)  tmp[k++]=q[i++];
        while(j<=r)    tmp[k++]=q[j++];
        for(int i=l;i<=r;i++)  q[i]=tmp[i];
    }

**3.希尔排序**

void ShellSort(Node A[],int n)      
    { 
            //前后记录位置的增量 dk
            //增量dk 并逐步减小增量
            for(int dk=n/2;dk>0;dk/=2){ 
                //从第dk个元素，逐个对其所在组进行直接插入排序操作
                for(int i=dk;i<n;++i){ 
                    int j=i;
                    while(j-dk>=0&&A[j].series<A[j-dk].series){ 
                        //插入排序交换法
                        swap(A[j],A[j-dk]);
                        j-=dk;
                    }
                }
            }
    }

**4.堆排序**

void adjust_heap(vector<int>& nums,int x,int n){ 
            int l=x*2+1;
            int r=x*2+2;
            int max=x;
            if(l<n&&nums[l]>nums[max])max=l;
            if(r<n&&nums[r]>nums[max])max=r;
            if(max!=x){ 
                swap(nums[max],nums[x]);
                adjust_heap(nums,max,n);
            }
        }
        void heap_sort(vector<int>& nums){ 
            int n=nums.size();
            for(int i=n/2-1;i>=0;i--){ 
                adjust_heap(nums,i,n);
            }
            for(int i=n-1;i>=0;i--){ 
                swap(nums[i],nums[0]);
                adjust_heap(nums,0,i);
            }
        }

### 实验源代码 ###

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<cmath>
    using namespace std;
    const int N = 10000 + 10;
    int n;  //学生数量
    struct Node
    { 
    	int idCard;    //卡号
    	string name;   //姓名
    	int classId;   //班号
    	int series;    //系别
    }students[N];
    Node tmp[N];
    void quick_sort(Node q[], int l, int r)  //使用快速排序，按照卡号从小到大排序
    { 
    	if (l >= r) return;
    	int i = l - 1, j = r + 1, x = q[(l + r) / 2].idCard;
    	while (i < j)
    	{ 
    		do i++; while (q[i].idCard < x);
    		do j--; while (q[j].idCard > x);
    		if (i < j)
    		{ 
    			swap(q[i], q[j]);
    		}
    	}
    	quick_sort(q, l, j); quick_sort(q, j + 1, r);
    }
    void merge_sort(Node q[],int l,int r)    //使用归并排序，按照班号从小到大排序
    { 
        if(l>=r)  return;
        int mid=l+r>>1;
        merge_sort(q,l,mid);
        merge_sort(q,mid+1,r);
        int k=l,i=l,j=mid+1;
        while(i<=mid&&j<=r)
        { 
            if(q[i].classId<q[j].classId)  tmp[k++]=q[i++];
            else   tmp[k++]=q[j++];
        }
        while(i<=mid)  tmp[k++]=q[i++];
        while(j<=r)    tmp[k++]=q[j++];
        for(int i=l;i<=r;i++)  q[i]=tmp[i];
    } 
    void ShellSort(Node A[],int n)        //使用希尔排序,按照系别从小到大排序
    { 
            //前后记录位置的增量 dk
            //增量dk 并逐步减小增量
            for(int dk=n/2;dk>0;dk/=2){ 
                //从第dk个元素，逐个对其所在组进行直接插入排序操作
                for(int i=dk;i<n;++i){ 
                    int j=i;
                    while(j-dk>=0&&A[j].series<A[j-dk].series){ 
                        //插入排序交换法
                        swap(A[j],A[j-dk]);
                        j-=dk;
                    }
                }
            }
    }
    void find_name(string name1)  //根据姓名查找一个学生的信息
    { 
    	int flag=0;
    	for(int i=0;i<n;i++)
    	{ 
    		if(students[i].name==name1)
    		{ 
    			cout<<"姓名： "<<students[i].name<<endl;
    			cout<<"卡号： "<<students[i].idCard<<endl;
    			cout<<"班号： "<<students[i].classId<<endl;
    			cout<<"系别： "<<students[i].series<<endl;
    		    flag=1;
    			break; 
    		}
    	}
    	if(flag==0) cout<<"没有该学生的信息 ！！！"<<endl; 
    }
    int main()
    { 
    	printf("实验题目\n");
    	printf("设计一个排序和查找系统。能够实现对给定的一组学生的借书证信息\n");
    	printf("（如：卡号、姓名、系别、班号等）进行排序和查找。\n"); 
    	printf("\n");
    	printf("--------请输入学生的卡号，姓名,班号，系别-------\n");
    	cin >> n;
    	for (int i = 0; i < n; i++)
    	{ 
    	   cin>>students[i].idCard>>students[i].name>>students[i].classId>>students[i].series;
    	}
    	printf("--------使用归并排序对卡号从小到大排序--------\n");
    	quick_sort(students, 0, n-1);
    	for (int i = 0; i < n; i++)
    	{ 
    		cout << students[i].idCard << ' ' << students[i].name << ' ' << students[i].classId << ' ' << students[i].series << endl;
    	}
    	printf("--------使用快速排序对班号从小到大排序--------\n");
    	merge_sort(students,0,n-1);
    	for (int i = 0; i <n; i++)
    	{ 
    		cout << students[i].idCard << ' ' << students[i].name << ' ' << students[i].classId << ' ' << students[i].series << endl;
    	}
    	ShellSort(students,n); 
    	printf("--------使用希尔排序对系别从小到大排序--------\n");
    	for (int i = 0; i < n; i++)
    	{ 
    		cout << students[i].idCard << ' ' << students[i].name << ' ' << students[i].classId << ' ' << students[i].series << endl;
    	}
    	printf("请输入要查找的学生的姓名：\n");
    	string str;
    	while(cin>>str) 
    	{ 
    		find_name(str);
    	}
    	return 0;
    }
    /* 4 688410003 lisi 190142 7 668410002 zhangsan 190143 6 668410001 wangwu 190141 5 668410004 zhangwei 190144 4 */

### 实验结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/65e2dddece55427a8769423cf3bf737c.png