算法学习4

一.荷兰国旗

1.问题一

一个数组，选择其中一个数作为对照，把小于等于对照数的放在数组的左边，大于对照数的放在右边；

思路：
设置小于区间，开始位置在数组开头前一位；
下标从数组第一个元素开始判断，有如下两种情况：
  （1）若当前数小于等于对照数，则将当前数与小于区间
      的下一个数进行交换，并将小于区间向前移一位，
      下标移动到下一位；
  （2）若当前数大于对照数，则直接将下标移动到下一
      位；
直到下标超出数组长度，则结束；

2.问题二（荷兰国旗问题）

一个数组，选择其中一个数作为对照，把小于等于对照数的放在数组的左边，等于对照数的将其放在数组中间，大于对照数的放在右边；

思路：
设置小于区间，开始位置在数组开头前一位；
设置大于区间，开始位置在数组结尾后一个；
下标从数组第一个元素开始判断，有如下三种情况：
  （1）若当前数小于对照数，则将当前数与小于区间
      的下一个数进行交换，并将小于区间向前移一位，
      下标移动到下一位；
  （2）若当前数等于对照数，则直接将下标移动到下一
      位；
  （3）若当前数大于对照数，则将大于区间前一位数与当
      前数进行交换，下标不变，大于区间前进一位；
直到下标与大于区间重叠，或者下标超出数组长度，则结束；

二.快排

1.快排版本1

原理：

1. 选数组最后一个数为对照数；
2. 对其余元素进行荷兰国旗方法排序；
3. 将对照数放置在大于区间的前一个位置；
4. 然后对大于和小于区间进行荷兰国旗方法排序，对照数分别为各自区间的最后一个；
5. 然后不断重复上面2、3、4操作；

快排的时间复杂度都为O（N²）；

1.快排版本2

原理：

1. 随机选数组中的一个将其与数组的最后一个元素交换并将其当作对照数；
2. 对其余元素进行荷兰国旗方法排序；
3. 将对照数放置在大于区间的前一个位置；
4. 然后对大于和小于区间进行荷兰国旗方法排序，对照数分别从各自区间中选取并将其放置在各自区间的最后一个；
5. 然后不断重复上面2、3、4操作；

快排的时间复杂度都为O（N * logN）；

代码：

public void quickSort(int[] arr,int L,int R)
{
	if(L < R){
		//选取随机数当作对照数放置在最后一位
		swap(arr,L + (int)(Math.random() * (R - L + 1)),R);
		int[] p = partition(arr,L,R);
		quickSort(arr,L,p[0] - 1);
		quickSort(arr,p[1] + 1,R);
	}	
}

//返回等于区域（左边界，右边界）
public int[] partition(int[] arr, int L,int R){
	//小于区域右边界
	int less = L - 1;
	//大于区域左边界
	int more = R;
	//L为当前数的位置
	while(L < more){
		if(arr[L] < arr[R]){
			swap(arr,++less,L++);
		}else if(arr[L] > arr[R]){
			swap(arr,--more,L);
		}else{
			L++;
		}
	}
	swap(arr,more,R);
	return new int[] {less + 1,more};
}