数据结构—快速排序模型

我会带着你远行 2022-08-21 13:41 176阅读 0赞

题目:

有一个线性表L，假设元素类型ElemType为整型。设计一个程序，将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。

/*
    思路一：
    用pivot存放基准即L->data[0]，用i和j分别指向顺序表L的第一个元素(i=0)和最后一个元素(j=L->length-1),当i<j时循环：
    从右向左扫描，找一个关键字小于等于pivot的data[j],再从左向右扫描，找一个关键字大于pivot的记录data[i],将两者进行交换。
    当循环结束后将data[0]和data[j]交换。
    思路二：
    用i从左向右查找，j从右向左查找。以元素data[0]为基准（将其先放在pivot中）。当i不等于j时循环：
    从右向左扫描，找一个关键字小于等于pivot的data[j],找到后用data[j]覆盖data[i]，再从左向右扫描，找一个关键字大于pivot的记录data[i],
    用data[i]覆盖data[j],最后让data[i]=pivot。
    */
    #include <iostream>
    #include <malloc.h>
    #define MaxSize 100
    using namespace std;
    typedef int ElemType;
    typedef struct
    {
        ElemType data[MaxSize];
        int length;
    } SqList;
    
    void move1(SqList *&L)
    {
        int i=0,j=L->length-1;
        ElemType pivot=L->data[0];   //以第一个元素为基准
        ElemType tmp;
        while(i<j)                 //从区间两端交替向中间扫描，直至i=j为止
        {
            while(i<j&&L->data[j]>pivot)  //找一个小于pivot的元素
                j--;
            while(i<j&&L->data[i]<=pivot) //找一个大于pivot的元素
                i++;
            if(i<j)                   //交换两值
            {
                tmp=L->data[i];
                L->data[i]=L->data[j];
                L->data[j]=tmp;
            }
        }
        tmp=L->data[0];            //交换pivot和data[j]的值
        L->data[0]=L->data[j];
        L->data[j]=tmp;
        cout<<"i="<<i<<endl;
    }
    
    void move2(SqList *&L)
    {
        int i=0,j=L->length-1;
        ElemType pivot=L->data[0];   //以第一个元素为基准
        while(i<j)                     
        {
            while(i<j&&L->data[j]>pivot)//找一个小于pivot的元素
                j--;
            L->data[i]=L->data[j];     //找到这样的data[j]放入data[i]处
            i++;
            while(i<j&&L->data[i]<=pivot)  //找一个大于pivot的元素
                i++;
            L->data[j]=L->data[i];         //找到这样的data[i]放入data[j]处
            j--;
        }
        L->data[i]=pivot;
        cout<<"i="<<i<<endl;
    }
    int main()
    {
        SqList *L1,*L2;
        ElemType a[10]= {3,8,2,7,1,5,2,4,6,7};
        L1=(SqList *)malloc(sizeof(SqList));
        for(int i=0; i<10; i++)
            L1->data[i]=a[i];
        L1->length=10;
        move1(L1);
         for(int i=0; i<L1->length; i++)
            cout<<L1->data[i]<<" ";
        cout<<endl;
        L2=(SqList *)malloc(sizeof(SqList));
        for(int i=0; i<10; i++)
            L2->data[i]=a[i];
        L2->length=10;
        move2(L2);
         for(int i=0; i<L2->length; i++)
            cout<<L2->data[i]<<" ";
        cout<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220724/1d95087a78fc432488d849b16203c076.png