首页 > 代码库 > 对数组按照某一基准进行整理

对数组按照某一基准进行整理

题目:给定一个整数数组,把最右端的元素作为基准,对这个数组进行整理,其中大于这个基准的元素放到它的右边,小于这个基准的元素放到它的左边。不得使用临时数组。

思路:先找一个大于基准的元素与基准进行交换位置,此时基准元素已经在数组的中部(不是最右/中间),从基准开始向后扫描,小于基准则交换。

public class ArrayPivot {
	public static void main(String[] args) {
		int[] c = pivot(new int[] { 2, 3, 5, 1, 6, 4 });
		for (int i = 0; i < c.length; i++)
			System.out.print(c[i] + ",");
	}

	public static int[] pivot(int[] a){
		int len = a.length;
		if(len <= 1)
			return a;
		int p = a[len - 1];
		int i = 0,temp = 0;;
		//第一次大于p的时候
		for(i=0;i<len;i++){
			if(a[i] > p){
				temp = a[i];
				a[i] = a[len - 1];
				a[len - 1] = temp;
				break;
			}
		}
		for(;i<len -1;i++){
			if(a[i+1] < a[i] && a[i+1] < p){
				temp = a[i+1];
				a[i+1] = a[i];
				a[i] = temp;
			}
		}
		return a;
	}
}