C++数据结构--快速排序

迈不过友情╰ 2022-01-22 01:49 180阅读 0赞

**\#include<stdio.h>  
typedef int InfoType;  
\#define n 8//假设的文件长度，即待排序的记录数目  
typedef int KeyType;//假设的关键字类型  
typedef struct \{ //记录类型  
KeyType key; //关键字项  
InfoType otherinfo;//其它数据项，类型InfoType依赖于具体应用而定义  
\} RecType;  
typedef RecType SeqList\[n+1\];//SeqList为顺序表类型，表中第0个单元一般用作哨兵  
int Partition(SeqList R,int i,int j);  
  
  
void main()  
\{  
void QuickSort(SeqList R,int low,int high);  
int i;  
SeqList R;  
printf("请输入欲排序的数：");  
for (i=1;i<=n;i++)  
scanf("%d",&R\[i\].key);  
printf("排序前：");  
for (i=1;i<=n;i++)  
printf("%d ",R\[i\].key);  
printf("\\n");  
QuickSort(R,1,n);  
printf("排序后：");  
for (i=1;i<=n;i++)  
printf("%d ",R\[i\].key);  
printf("\\n");  
\}  
  
  
//对R\[low..high\]快速排序  
void QuickSort(SeqList R,int low,int high)  
\{  
int pos=0;  
if(low<high)  
\{  
pos= Partition(R,low,high);//pos为基准下标  
QuickSort(R,low,pos-1);  
QuickSort(R,pos+1,high);  
  
  
  
\}  
\}  
  
  
//调用Partition(R,low,high)时，对R\[low..high\]做划分，并返回基准记录的位置  
int Partition(SeqList R,int i,int j)  
\{  
  
RecType base=R\[i\];  
while(i<j)  
\{  
while(i<j&&R\[j\].key>=base.key)  
j--;  
R\[i\]=R\[j\];  
while(i<j&&R\[i\].key<=base.key)  
i++;  
R\[j\]=R\[i\];  
\}  
R\[i\]=base;  
return i;  
\}  
  
  
  
  
运行结果：  
![20130612183026078][]  
  
  
  
  
  
快速排序简化版本：  
\#include<iostream>  
using namespace std;  
\#define n 6  
int main()  
\{  
void QuickSort(int arr\[\],int i,int j);  
int arr\[n\]=\{12,43,2,76,32,54\};  
QuickSort(arr,0,n-1);  
for(int i=0;i<n;i++)  
cout<<arr\[i\]<<"\\t";  
 cout<<endl;  
\}  
  
  
int division(int arr\[\],int i,int j);  
void QuickSort(int arr\[\],int i,int j)  
\{  
int pos;  
if(i<j)  
\{  
pos=division(arr,i,j);  
 QuickSort(arr,i,pos-1);  
 QuickSort(arr,pos+1,j);  
\}  
  
  
\};  
  
  
int division(int arr\[\],int i,int j)  
\{  
int base=arr\[i\];  
while(i<j)  
\{  
while(i<j&&arr\[j\]>=base)  
j--;  
arr\[i\]=arr\[j\];  
while(i<j&&arr\[i\]<=base)  
i++;  
arr\[j\]=arr\[i\];  
arr\[i\]=base;  
\}  
return i;  
\}**

[20130612183026078]: /images/20220122/68dda6b65ea34e6d9fef0804991c473c.png