当前位置: 首页 > 工具软件 > Pivot4J > 使用案例 >

对一个顺序表以首元素为pivot进行partion操作

邵宏达
2023-12-01
#include <stdio.h>

/*
题目:天勤40页(5)
将顺序表L中所有小于表头元素的元素放在表的前半部分,大于表头元素的元素放在后半部分
顺序表中没有相同元素
(这是快速排序的partition部分)

算法:
基于两个下标变量,一个对顺序表进行从前往后的遍历,一个对顺序表进行从后往前的遍历,
并在适当是时机进行值交换
*/

#define maxlen 50
#define DATATYPE int

typedef struct{
    DATATYPE arr[maxlen];
    int length;
}Seqlist;

void print_SQ(Seqlist list)
{
    for(int i=0;i<list.length;i++){
        printf("%d ",list.arr[i]);
    }
    printf("\n");
}


int main(void)
{
    Seqlist list = {{6,3,6,6,1,1,10},7};

    int i=0,j=list.length-1;
    //pivot存放枢纽值
    int pivot = list.arr[0];


    while(i < j){
        //j从后往前遍历顺序表,i从前往后遍历顺序表(i与j交替遍历)
        //因为枢纽是表的第一个元素,所以先用j从后往前遍历顺序表
        while(i<j && list.arr[j]>pivot){
            --j;
        }
        //i<j是基于值交换的重要前提,时刻保证此条件的满足性
        if(i<j){
            //list.arr[j]<pivot,把它赋值给list.arr[i]
            list.arr[i] = list.arr[j];
            ++i;
        }

        //再用i从前往后遍历顺序表
        while(i<j && list.arr[i]<pivot){
            ++i;
        }

        if(i<j){
           //list.arr[i]>pivot,把它赋值给list.arr[j]
            list.arr[j] = list.arr[i];
            --j;
        }

    }
    //此时i==j,把枢纽赋进list.arr[i],也即list.arr[j]
    list.arr[i] = pivot;

    print_SQ(list);
}

 

 类似资料: