编写以下方法，使用第一个元素对列表进行划分，该元素称为支点。

        public static int partition(int[] list)

        划分后，列表中的元素被重新安排，在支点元素之前的元素都小于或者等于该元素，而之后的元素都大于该元素。方法返回支点元素位于新列表的下标。例如，假设列表是[5，2，9，3，8]，划分后，列表变为[3，2，5，9，8]。最多进行list.length次比较来实现该方法。

        编写一个程序，提示用户输入一个列表，然后显示划分后的列表。注意，输入的第一个数字表示列表中元素的个数。该数字不是列表的一部分。

---

package pack2;

import java.util.Scanner;

public class Partition {

	public static void main(String[] args) {
		try(Scanner input = new Scanner(System.in);) {
			System.out.print("Enter list: ");
			int[] list = new int[input.nextInt()];
			for (int i = 0; i < list.length; i++) 
				list[i] = input.nextInt();
			
			int index = partition(list);
			
			System.out.print("After the partition, the list is");
			for (int i : list) { System.out.print(" "+i); }
			System.out.println("\nThe new index of "+list[index]+" is "+index);
		}
	}

	/**划分列表（快速排序的一次排序）*/
	public static int partition(int[] list) {
		int low = 0, high = list.length - 1;	//最小下标和最大下标
		int temp = list[0];	//首元素
		
		while(low < high) {
			while(low < high && temp <= list[high]) high--;	//找出小于temp的元素
			while(low < high && temp >= list[low]) low++;	//找出大于temp的元素
			
			if(low < high) {	//互换两个元素
				int temp2 = list[low];
				list[low] = list[high];
				list[high] = temp2;
			}
		}
		list[0] = list[low];	//low == high 处的元素
		list[low] = temp;		//与首元素互换
		
		return high;
	}
}

---