个人任务1.快速排序的应用（使用顺序表ADT和类模板）

谁借莪１个温暖的怀抱￠ 2023-09-28 13:06 3阅读 0赞

## 快速排序的应用 ##

作者: 冯向阳 时间限制: 1S 章节: 课程设计

> **问题描述**：
> 
> 已知线性表（a1 a2 a3 „an）按顺序存于内存，每个元素都是非零整数。在使用顺序表ADT的基础上，试设计基于快速排序的思想把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x,x）变为（-x,-x,-x,x,x,x）。  
> 提示：要求重排n个元素且以顺序存储结构存储的线性表，使得所有值为负数的元素移到正数元素的前面。这可采用快速排序的思想来实现。只是比较的标准是元素是否为负数。因此枢轴元素的值为0(不是线性表中的元素)。基本思路是，先设置好上、下界和枢轴值(0)，然后执行一趟快速排序，即利用震荡交替法分别从线性表的两端查找正数和负数，找到后互相交换，直到上下界相遇。  
> 参考函数原型：  
> template  
> void Rearrange( SqList &A );

> **输入说明：**  
> 第一行：顺序表A的长度  
> 第二行：顺序表A的数据元素（数据元素之间以空格分隔）

> **输出说明：**  
> 第一行：排序前的顺序表遍历结果  
> 空行  
> 第三行：第一组值交换的中间结果  
> …  
> 第n行：最终的输出结果

> **输入范例：**  
> 10  
> 10 -9 8 -7 6 -5 4 -3 2 -1

> **输出范例：**  
> 10 -9 8 -7 6 -5 4 -3 2 -1  
> （空行）  
> \-1 -9 8 -7 6 -5 4 -3 2 10  
> \-1 -9 -3 -7 6 -5 4 8 2 10  
> \-1 -9 -3 -7 -5 6 4 8 2 10

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<stdlib.h>
    #include<stdio.h>
    #include<fstream>
    #include<iomanip>
    #include<utility>
    #define MAXSIZE 20001
    using namespace std;
    int a[10001]={
        0},b[10001]={
        0};
    
    template<class ElemType>
    class SqList{
        
        public:
            ElemType data[MAXSIZE];
            int length=0;
        public:
            SqList(){
        };
            void SqListInit(int i,ElemType x){
        
                data[i]=x; length+=1;
            }
    };
    
    template<class ElemType>
    void Shuchu(SqList<ElemType> &L){
        //输出表
        for(int i=0;i<L.length;++i){
        
            if(i==0)
                cout<<L.data[i];
            else
                cout<<" "<<L.data[i];
        }
        cout<<endl;
    }
    
    template<class ElemType>
    void Rearrange(SqList<ElemType> &L){
        //对表进行排序
        int low=0,high=L.length-1;
        while(low<high){
        
            while(low<high&&L.data[high]>0)//如果右侧的值大于0，则就指针向左继续移
                --high;
            while(low<high&&L.data[low]<0)//如果左侧的值小于0，则就指针向右继续移
                ++low;
            if(low<high&&L.data[low]>0&&L.data[high]<0)//当low<high，且右侧值小于0，左侧值大于0，则交换他们的值
                swap(L.data[low],L.data[high]);
            else//否则继续循环
                continue;
            ++low;
            --high;
            Shuchu(L);
        }
    }
    
    int main(){
        
        SqList<int> L;
        int n,x;
        cin>>n;
        for(int i=0;i<n;++i){
        
            cin>>x;
            L.SqListInit(i,x);
        }
        Shuchu(L);//排序前的顺序表遍历结果
        cout<<endl;
        Rearrange(L);
        return 0;
    }

在判断的过程中一定要加上这个判断  
if(low<high&&L.data\[low\]>0&&L.data\[high\]<0)  
//当low<high，且右侧值小于0，左侧值大于0，则交换他们的值  
**有了这个判断才是保证所以情况都对。**