编写以下方法,使用第一个元素对列表进行划分,该元素称为支点。
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; } }