資料結構程式問題 快速排序法?

/**
* qsort_struct
* @author Wei-Yuan Chen
* 2017/2/21
* MIT License
*/
#include<iostream>
#include<stdlib.h> // use atoi()
#include<fstream> // use fstream
using namespace std;
//-----------------
// max size in file (per line)
#define SIZE 200
#define DEBUG 0
#define SWAP(x,y) { x^=y; y^=x; x^=y; }
//-----------------
// each data
struct info{
// items
string name;
int score;
info(string NAME,int SCORE){
name=NAME;
score=SCORE;
}
void show(void){
cout<<name<<" "<<score<<endl;
}
};
// link data
struct mylist{
// use to link
mylist* head;
mylist* next;
mylist* tail;
// count element
int number;
// each data
info *data;

mylist(){
head=next=tail=NULL;
number=0;
data=new info("",-1);
}
void init(mylist* HEAD){
head=tail=HEAD;
}
// add data
void Push(info* newone){
mylist* mylist_temp=new mylist();

mylist_temp->data=newone;

tail->next=mylist_temp;
tail=mylist_temp;

head->number++;
}
// get and remove the first data
info* Pop(void){

info* info_temp;
if(head->next!=NULL){
mylist* mylist_temp=head->next;
info_temp=new info( mylist_temp->data->name
,mylist_temp->data->score);
head->next=mylist_temp->next;
head->number--;
delete mylist_temp;
if(head->number==0) tail=head;

}
else info_temp=new info("",-1);
return info_temp;
}
// show all datas
void show(void){
mylist* mylist_temp=head->next;
while(mylist_temp!=NULL){
mylist_temp->data->show();
mylist_temp=mylist_temp->next;
}
}
void myfree(void)
{
mylist* mylist_temp=head->next;
while(mylist_temp!=NULL){
head->next=mylist_temp->next;
delete mylist_temp;
mylist_temp=head->next;
}
delete head;
}
~mylist(){
if(head==NULL)
{
delete head;
delete tail;
}
delete data;
}
};
//-----------------
// convert
void my_qsort(mylist*);
// quick sort
void qsort(int*,int,int);
//-----------------
int main(void){
mylist *students=new mylist();
students->init(students);
// get data from file
fstream finput;
char ftemp[SIZE];
finput.open("qsort_input.txt",ios::in);
while(finput.getline(ftemp,sizeof(ftemp))){ // get one line
string stemp=ftemp;
// check the Separator
int sep=stemp.find(' ');
int sep1=stemp.find('\t');
if( sep==-1 || (sep>sep1 && sep1>-1)) sep=sep1;
// create new data
info* info_temp=new info( stemp.substr(0, sep),
atoi( stemp.substr(sep).c_str() ) );
// save in students
students->Push(info_temp);

}
finput.close();
// data from file
cout<<"----data from file----"<<endl;
students->show();
// qsort
my_qsort(students);
// after sort
cout<<"----data after sort----"<<endl;
students->show();
// end
system("pause");
return 0;
}
// convert
void my_qsort(mylist* students){
mylist* mylist_temp=new mylist();
mylist_temp->init(mylist_temp);

int number=students->number; // array size
int Q[number]; // array to sort
for(int i=0;i<number;i++) {
info* info_temp=students->Pop(); // get first data

Q[i]=info_temp->score; // get score to sort
mylist_temp->Push(info_temp); // temp

if(DEBUG) cout<<Q[i]<<",";
}
// now students is empty
if(DEBUG) cout<<endl;
//-----------------------------
// quick sort
qsort(Q,0,number);

if(DEBUG){
for(int i=0;i<number;i++)cout<<Q[i]<<",";
cout<<endl;
}
//-----------------------------
// find the data order by score
for(int i=0;i<number;i++) {
if(i>0 && Q[i]==Q[i-1]) continue;
mylist* index_temp=mylist_temp->next;
while(index_temp!=NULL) {
if(index_temp->data->score==Q[i]) {
info* info_temp=new info(index_temp->data->name,index_temp->data->score);
// save in students
students->Push(info_temp);
}
index_temp=index_temp->next;
}
}
mylist_temp->myfree();

}
//----------------------------
// quick sort (hight to low)
void qsort(int *Q,int L,int R) {
if(DEBUG) cout<<"L="<<L<<",R="<<R<<endl;
int index=L;
for(int i=L+1;i<R;i++) {
if( Q[i] < Q[L] ) { // to right
for(int j=i;j<R;j++) { // find someone to swap
if( Q[j] > Q[L] ) {// to left
SWAP(Q[i],Q[j]);
index++;
break;
}
}
}
else index++; //to left
}
//----------------------------
int temp=Q[L];
for(int i=L;i<index;i++) Q[i]=Q[i+1];
Q[index]=temp;
//----------------------------
// next round
if(L<index) qsort(Q,L,index); // left
if(index+1<R) qsort(Q,index+1,R); // right
}
/*
sample input "qsort_input.txt"

Zoe 30
Anne 45
Steve 13
Jane 97
Jerry 73
Allen 60
James 83
Lee 23
Stella 54

sample output

----data from file----
Zoe 30
Anne 45
Steve 13
Jane 97
Jerry 73
Allen 60
James 83
Lee 23
Stella 54
----data after sort----
Jane 97
James 83
Jerry 73
Allen 60
Stella 54
Anne 45
Zoe 30
Lee 23
Steve 13
請按任意鍵繼續 . . .
*/

(sorry我是學C++而且學的不深>< 因為不會檔案讀寫，所以用標準輸出輸入的方式寫)

方法一：
C++裡面可以用struct
struct namelist {
string name;
int score;
};

int main()
{
namelist students[9];
for (int i=0; i<9; i++)
{
cin >> namelist[i].name >> namelist[i].score;
}
}
去把輸入的資料用自己定義的資料型態儲存起來
(好處是不用透過字串處理把數字分開)

之後就可以用類似 修改運算子"<"的定義 的方式 (專業術語好像叫 運算子超載)
bool operator< (const namelist &a, const namelist &b)
{
return a.score < b.score;
}

再外加C++的sort(C++的sort本身就是用quick sort)
sort(student, student+9);
就可以完成排序了~~
最後輸出就用for
for (int i=0; i<9; i++)
{
cout << student.name[i];
}


方法二：
另一個方式就是分開讀入
string name[9];
int score[9];
for (int i=0; i<9; i++)
{
cin >> name[i] >> score[i];
}

之後再自己手寫quick sort或merge sort之類的
時間複雜度一樣是n*log(n)的演算法
然後稍微修改一下交換的部分
把原本 交換編號a, b兩個位置的值 的動作改成 交換編號a, b兩個位置的值和字串
也可以有一樣的效果！

不過方法二相對來說麻煩很多
還是推薦方法一


希望能幫上忙~

"資料結構"是約30-40年前的觀念....
方法一(不太好): 用暫存string將 score移至字串頭排序 或者轉成int排序