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

#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);
}

最后

以上就是妩媚溪流为你收集整理的对一个顺序表以首元素为pivot进行partion操作的全部内容，希望文章能够帮你解决对一个顺序表以首元素为pivot进行partion操作所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。