设有一元素为整数的线性表l=(a1,a2,a3,...,an)，存放在一维数组a[n]中，设计一个算法，以表中an作为参考元素，将表分为左、右两部分，其中左半部分每个元素小于等于an，右半部分每个元素

题目要求设计一个算法，将一个元素为整数的线性表l=(a1,a2,a3,...,an)存放在一维数组a[n]中。然后根据第n个元素作为参考元素，将表分为左、右两部分，其中左半部分分每个元素小于等于n，右半部分分每个元素大于等于n。

相关问题

设有一元素为整数的线性表l=(a1,a2,a3,…,an),存放在一维数组a[n]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都

题意：有一个元素为整数的线性表l=(a1,a2,a3,…,an)，存放在一维数组a[n]中，设计一个算法，以表中第an作为参考元素，将该表分为左、右两部分，其中左半部分分每个元素小于等于an，右半部分分每个元素都大于等于an。

解题思路：可以把参考元素an放在最后一个位置，然后设定两个指针left和right分别指向表头和表尾，然后进行如下操作：

1. 从左向右扫描，找到第一个大于等于an的元素a[i]，记录下i；
2. 从右向左扫描，找到第一个小于等于an的元素a[j]，记录下j；
3. 如果i<j，则交换a[i]和a[j]；
4. 重复1-3步，直到left>=right；
5. 将an与left所指的元素交换。

最后，表l就被划分成了左、右两部分，其中左半部分每个元素小于等于an，右半部分每个元素都大于等于an。