1. 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； 2. 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用； 3. 了解各种方法的排序过程及其时间复杂度的分析方法。 编程实现如下功能： （1）建立顺序表，输入n个学生的姓名和分数，作为待排序序列。 （2）利用直接插入排序对待排序序列进行排序，并输出排序后的结果。 （3）利用冒泡排序对待排序序列进行排序，并输出排序后的结果。 （4）利用直接选择排序对待排序序列进行选择排序，并输出排序后的结果。 （5）利用快速排序对待排序序列进行排序，并输出排序后的结果。 |
．给出n个学生的考试成绩表，每条信息由姓名和分数组成。分别应用直接插入排序、冒泡排序、直接选择排序和快速排序将学生按分数从高到低排列。 |
#include <iostream> #include<stdlib.h> #define Max_size 100 using namespace std; typedef struct note { string name; int score; }redtype;; typedef struct Vector { redtype *student; int length; }sqlist; void bubbleSor(redtype temp[],int n)//冒泡排序 {//主要思想是通过两两比较来进行排序的 for(int i=0;i<n-1;i++) { for(int j=0;j<n-1-i;j++) { redtype arr; if(temp[j].score<temp[j+1].score) { arr=temp[j]; temp[j]=temp[j+1]; temp[j+1]=arr; } } } for(int i=0;i<n;i++) { cout<<temp[i].name<<" "; cout<<temp[i].score<<endl; } return ; } void selectionSor(redtype temp[],int n) {//选择排序，通过选择一个最大或最小来进行排序 for(int i=0;i<n-1;i++) { int k=i; for(int j=i+1;j<n;j++) { if(temp[i].score<temp[j].score) { k=j; } } if(k!=i) { redtype arr; arr=temp[i]; temp[i]=temp[k]; temp[k]=arr; } } for(int i=0;i<n;i++) { cout<<temp[i].name<<" "; cout<<temp[i].score<<endl; } return ; } void insertionSort(redtype temp[],int n) {//插入排序，通过找到一个值，不断往前面比较找到符合的进行插入 redtype sour; for(int i=1;i<n;i++) { if(temp[i].score>temp[i-1].score) { sour=temp[i]; temp[i]=temp[i-1]; int j; for( j=i-2;j>=0&&sour.score>temp[j].score;j--) temp[j+1]=temp[j]; temp[j+1]=sour; } } for(int i=0;i<n;i++) { cout<<temp[i].name<<" "; cout<<temp[i].score<<endl; } return ; } void reset(redtype temp[],sqlist s) { for(int i=0;i<s.length;i++) { temp[i].name=s.student[i].name; temp[i].score=s.student[i].score; } } int Part(redtype arr[], int low, int high) { int pivot = arr[high].score; // 选取最后一个元素作为基准点 int i = (low - 1); // 记录小于基准点的元素位置 for (int j = low; j <= high - 1; j++) { for (int j = low; j <= high - 1; j++) { if (arr[j].score > pivot) { i++; redtype temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } redtype temp=arr[i + 1]; arr[i + 1]=arr[high]; arr[high]=temp; return (i + 1); } } void quick(redtype arr[], int low, int high) { if (low < high) { int pi = Part(arr, low, high); // 获取分区点 quick(arr, low, pi - 1); // 对分区点左边的子数组进行快速排序 quick(arr, pi + 1, high); // 对分区点右边的子数组进行快速排序 } } int main() { sqlist s; int n; cin>>n; s.student=new redtype[n]; s.length=n; redtype temp[Max_size]; for(int i=0;i<n;i++) { cout<<"输入学生的名字:"; cin>>s.student[i].name; cout<<"输入成绩:"; cin>>s.student[i].score; } reset(temp,s); cout<<"冒泡排序:"<<endl; bubbleSor(temp,n); reset(temp,s); cout<<"选择排序:"<<endl; selectionSor(temp,n); reset(temp,s); cout<<"插入排序:"<<endl; insertionSort(temp,n); reset(temp,s); cout<<"快速排序:"<<endl; quick(temp,0,n-1); for(int i=0;i<n;i++) { cout<<temp[i].name<<" "; cout<<temp[i].score<<endl; } return 0; } |