程序填空题：快速排序（分治法）
快速排序。
```c++
#include
#define MAXSIZE 1000
using namespace std;
typedef struct
{
int key;
char *otherinfo;
}ElemType;
typedef struct
{
ElemType *r;
int length;
}SqList;
int Partition(SqList &L,int low,int high)
{
int pivotkey;
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(@@[low {
while(@@[low=pivotkey](2)) --high;
L.r[low]=L.r[high];
while(@@[low L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void QSort(SqList &L,int low,int high)
{
int pivotloc;
if(low {
pivotloc=@@[Partition(L,low,high)](2);
@@[QSort(L,low,pivotloc-1)](1);
@@[QSort(L,pivotloc+1,high)](1);
}
}
void QuickSort(SqList &L)
{
QSort(L,1,L.length);
}
void Create_Sq(SqList &L)
{
int i,n;
cin>>n; //输入的值不大于 MAXSIZE
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
if(i==1)
cout< else
cout<<" "<}
int main()
{
SqList L;
L.r=new ElemType[MAXSIZE+1];
L.length=0;
Create_Sq(L);
QuickSort(L);
show(L);
return 0;
}
```
### 输入样例：
第一行输入一个数n(输入的值不大于 MAXSIZE)，接下来输入n个数。
```in
7
24 53 45 45 12 24 90
```
### 输出样例：
输出按升序排序的结果。
```out
12 24 24 45 45 53 90
```
答案：
第1空：low
第2空：low=pivotkey
第3空：low
第4空：Partition(L,low,high)
第5空：QSort(L,low,pivotloc-1)
第6空：QSort(L,pivotloc+1,high)
```c++
#include
#define MAXSIZE 1000
using namespace std;
typedef struct
{
int key;
char *otherinfo;
}ElemType;
typedef struct
{
ElemType *r;
int length;
}SqList;
int Partition(SqList &L,int low,int high)
{
int pivotkey;
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(@@[low
while(@@[low
L.r[low]=L.r[high];
while(@@[low
}
L.r[low]=L.r[0];
return low;
}
void QSort(SqList &L,int low,int high)
{
int pivotloc;
if(low
pivotloc=@@[Partition(L,low,high)](2);
@@[QSort(L,low,pivotloc-1)](1);
@@[QSort(L,pivotloc+1,high)](1);
}
}
void QuickSort(SqList &L)
{
QSort(L,1,L.length);
}
void Create_Sq(SqList &L)
{
int i,n;
cin>>n; //输入的值不大于 MAXSIZE
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
if(i==1)
cout<
cout<<" "<
int main()
{
SqList L;
L.r=new ElemType[MAXSIZE+1];
L.length=0;
Create_Sq(L);
QuickSort(L);
show(L);
return 0;
}
```
### 输入样例：
第一行输入一个数n(输入的值不大于 MAXSIZE)，接下来输入n个数。
```in
7
24 53 45 45 12 24 90
```
### 输出样例：
输出按升序排序的结果。
```out
12 24 24 45 45 53 90
```
答案：
第1空：low
第2空：low
第3空：low
第4空：Partition(L,low,high)
第5空：QSort(L,low,pivotloc-1)
第6空：QSort(L,pivotloc+1,high)
