考研中划分规则
特指以某个元素为标准
把顺序表中元素分为左右两部分
这个标准元素 叫枢轴
共三种策略
① 第一种 顺序表 以第一个元素为枢轴 将顺序表划为左右两部分
左边元素都小于枢轴 右边元素都大于枢轴
并且枢轴要夹在左右两部分元素之间
++i 使 i 后移
当 i 所指元素大于temp（临时元素）时
使 j 所指向的 等于 i 所指向元素
并使 j 前移
重复 i 往右扫描 ， j 往左扫描
直到 i 和 j 相遇
顺序表
temp初值 为数组第一个元素的值
i 和 j 分别指向数组两端的两个元素
内层循环 j 和 i 每次移动的时候 都需要判断一下 i < j
这个大前提条件
if判断 i < j 语句
因为上面那个while循环 有可能是 i >=j 的这种情况结束了循环
因此需要判断条件
②第二种
加了个comp元素 为0
这次以0为标准 进行比较 而不是temp
最后指向的是 枢轴 而不是指向 比较标准 0
再说 顺序表中也没有0这个元素
这种情况告诉我们
即使取得比较的标准 存在于表中
i j 也不会指向它
并且顺序表被划分的左右两部分的分界线的位置
和你取得作为比较标准的 元素 在数组的位置 没有任何关系
分界线的位置 和枢轴的位置 是有关系
取得元素大于枢轴元素时 分界线在枢轴的右边
取得元素小于枢轴元素时 分界线在枢轴的左边
取得元素 恰好等于 数轴元素时 分界线就是枢轴本身
这和我们第一种划分方法 结果统一起来
当我们把comp取为枢轴的值
执行效果和第一种 一样
③第三种
假设我现在想让数组中任何一个位置上的元素来作为枢轴进行划分
只需要把想要作为枢轴的元素交换到第一个位置上
就可以按第一种进行划分
多执行了一个 元素交换操作
这样 就可以取 k位置的元素为枢轴 来对顺序表进行划分
总结 三种划分方法
①以顺序表第一个位置的元素为枢轴 把顺序表以枢轴元素为分界线
划分为了两部分 左边都小于枢轴 右边都大于等于枢轴
②以任意一个值作为比较的标准 把顺序表划分了两部分，假设这个值为Y
左边都小于Y 右边都大于等于Y
③以顺序表任何一个位置的元素为枢轴 把顺序表划分了两部分
左边都小于枢轴 右边都大于等于枢轴
网友评论