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;

}