策略模式

策略模式（Strategy Pattern）是一种比较简单的模式，也叫做政策模式（Policy Pattern）。

其定义如下： Define a family of algorithms,encapsulate each one,and make them interchangeable.（定义一组算法，将每个算法都封装起来，并且使它们之间可以互换。）

可以看一下工厂方法模式的实例。

我们进行创建了12种排序方式，实际上使用的是策略模式，因为之前是创建型模式，所以是为了说明怎么去通过工厂创建算法，而策略模式是行为型模式，是针对算法的实现。

package com.cl.factorymethod;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 算法实现的定义接口
 *
 * @author cl
 */
public interface SortAlgorithm {

	int[] sort(int[] array);
}

/**
 * 插入排序 
 * 1、从第一个元素开始，该元素可以认为已经被排序 
 * 2、取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 3、如果该元素（已排序）大于新元素，将该元素移到下一位置 
 * 4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 
 * 5、将新元素插入到该位置后
 * 6、重复步骤2~5
 * 
 * 排序算法复杂度为O(n^2)
 *
 * @author cl
 */
class InsertionSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		if (array.length <= 1) {
			return array;
		}
		for (int i = 1; i < array.length; i++) {
			int value = array[i];
			int j = i - 1;
			for (; j >= 0; --j) {
				if (array[j] > value) {
					array[j + 1] = array[j];
				} else {
					break;
				}
			}
			array[j + 1] = value;
		}
		return array;
	}

}

/**
 * 二分插入排序 
 * 1、从第一个元素开始，该元素可以认为已经被排序 
 * 2、取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置
 * 3、将新元素插入到该位置后 
 * 4、重复上述两步
 * 
 * 空间代价：O(1) 时间代价：插入每个记录需要O(log i)比较，最多移动i+1次，最少2次。最佳情况O(n log n)，最差和平均情况O(n^2)。
 *
 * @author cl
 */
class BinaryInsertSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		int key, left, right, middle;
		for (int i = 1; i < array.length; i++) {
			key = array[i];
			left = 0;
			right = i - 1;
			while (left <= right) {
				middle = (left + right) / 2;
				if (array[middle] > key)
					right = middle - 1;
				else
					left = middle + 1;
			}

			for (int j = i - 1; j >= left; j--) {
				array[j + 1] = array[j];
			}
			array[left] = key;
		}
		return array;
	}
}

/**
 * 希尔排序 
 * 1、先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
 * 2、所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。 
 * 3、取第二个增量d2<d1重复上述的分组和排序，
 * 4、直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
 *
 * 希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n^2)，
 * 而Hibbard增量的希尔排序的时间复杂度为O(N^(5/4))，但是现今仍然没有人能找出希尔排序的精确下界。
 * 
 * @author cl
 */
class ShellSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		for (int gap = array.length / 2; gap > 0; gap /= 2) {
			for (int i = 0; i < gap; i++) {
				for (int j = i + gap; j < array.length; j += gap) { // 每个子序列都从第二个开始
					if (array[j] < array[j - gap]) {
						int temp = array[j];
						int k = j;
						while (k >= gap && array[k - gap] > temp) {
							array[k] = array[k - gap];
							k -= gap;
						}
						array[k] = temp;
					}
				}
			}
		}
		return array;
	}

}

/**
 * 选择排序
 * 1、初始状态：无序区为R[1..n]，有序区为空。
 * 2、第i趟排序(i=1,2,3...n-1)
 *     第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。
 *     该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，
 *     使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
 * 3、前n-1趟结束，数组有序化了
 * 时间复杂度：O(n^2)
 * 
 * @author cl
 *
 */
class SelectionSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		for (int i = 0; i < array.length; i++) {
			int min = array[i];
			int index = i;
			for (int k = i + 1; k < array.length; k++) {
				if (min > array[k]) {
					index = k;
					min = array[k];
				}
			}
			array[index] = array[i];
			array[i] = min;
		}
		return array;
	}
	
}

/**
 * 冒泡排序
 * 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 * 3、针对所有的元素重复以上的步骤，除了最后一个。
 * 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 * 时间复杂度 最好O(n) 最坏情况O(n2)
 * 
 * @author cl
 *
 */
class BubbleSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		int n = array.length;
		for (int i = 0; i < n - 1; i++){
			for (int j = n -1; j > i; j--){
				if (array[j-1] > array[j]){
					int temp = array[j-1];
					array[j-1] = array[j];
					array[j] = temp;
				}
			}
		}
		return array;
	}
	
}

/**
 * 鸡尾酒排序/双向冒泡排序
 * 1、依次比较相邻的两个数，将小数放在前面，大数放在后面；
 * 2、第一趟可得到：将最大数放到最后一位。
 * 3、第二趟可得到：将第二大的数放到倒数第二位。
 * 4、如此下去，重复以上过程，直至最终完成排序。
 * 最差时间复杂度 	O(n^2)
 * 最优时间复杂度	O(n)
 * 平均时间复杂度	O(n^2)
 * 
 * @author cl
 *
 */
class CocktailSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		int tail = array.length - 1;
		for (int i = 0; i < tail; tail--) {
			for (int j = tail; j > i; --j) // 第一轮，先将最小的数据排到前面
			{
				if (array[j] < array[j - 1]) {
					int temp = array[j];
					array[j] = array[j - 1];
					array[j - 1] = temp;
				}
			}
			++i; // 原来i处数据已排好序，加1
			for (int j = i; j < tail; ++j) // 第二轮，将最大的数据排到后面
			{
				if (array[j] > array[j + 1]) {
					int temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;
				}
			}
		}
		return array;
	}

}

/**
 * 快速排序
 * 1、从数列中挑出一个元素，称为 "基准"（pivot）
 * 2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 * 		在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
 * 3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 * 
 * 最差时间复杂度		O(n^2)
 * 最优时间复杂度		O(n log n)
 * 平均时间复杂度		O(n log n)
 * 最差空间复杂度		根据实现的方式不同而不同
 *
 * @author cl
 */
class QuickSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		quickSort(array, 0, array.length);
		return array;
	}
	
	private static void quickSort(int[] array, int low, int high) {
		if (low >= high) {
			return ;
		}
		int i = low;
		int j = high;
		int temp = array[i];
		while (i < j) {
			while (i < j && array[j] >= temp) {
				j--;
			}
			if (i < j) {
				array[i++] = array[j];
			}
			while (i < j && array[i] < temp) {
				i++;
			}
			if (i < j) {
				array[j--] = array[i];
			}
		}
		array[i] = temp;
		quickSort(array, low, i - 1);
		quickSort(array, i + 1, high);
	}
	
}

/**
 * 堆排序
 * 1、在对应的数组元素A[i], 左孩子A[LEFT(i)], 和右孩子A[RIGHT(i)]中找到最大的那一个，将其下标存储在largest中。
 * 2、如果A[i]已经就是最大的元素，则程序直接结束。
 * 3、否则，i的某个子结点为最大的元素，将A[largest]与A[i]交换。
 * 4、再从交换的子节点开始，重复1,2,3步，直至叶子节点，算完成一次堆调整。
 * 最差时间复杂度		O(n log n)
 * 最优时间复杂度		O(n log n)
 * 平均时间复杂度		O(n log n)
 * 最差空间复杂度		O(n)
 *
 * @author cl
 */
class HeapSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		int i;
		int n = array.length;
		for (i = n / 2 - 1; i >= 0; i--) { // 从最后一个非终端节点开始，逐个向上遍历
			maxHeapDown(array, i, n - 1);
		}
		for (i = n - 1; i > 0; i--) {
			int tmp = array[0];
			array[0] = array[i];
			array[i] = tmp;
			maxHeapDown(array, 0, i - 1);
		}
		return array;
	}

	private void maxHeapDown(int[] array, int start, int end) {
		int father = start;
		int child = 2 * father + 1; // 左孩子
		while (child <= end) {
			if (child < end && array[child] < array[child + 1]) {
				child++; // 如果右孩子大，将左孩子变为右孩子
			}
			if (array[father] >= array[child]) {
				break;
			} else {
				int tmp = array[father];
				array[father] = array[child];
				array[child] = tmp;
			}
			father = child;
			child = 2 * father + 1;
		}
	}

}

/**
 * 归并排序
 * 1、Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。
 * 2、Conquer: 对这两个子序列分别采用归并排序。
 * 3、Combine: 将两个排序好的子序列合并成一个最终的排序序列。
 * 
 * 时间复杂度		O(n*logn)
 *
 * @author cl
 */
class MergeSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		mergeSort(array, 0, array.length - 1);
		return array;
	}

	private void mergeSort(int[] array, int start, int end) {
		if (start < end) {
			int median = (start + end) / 2;
			mergeSort(array, start, median);
			mergeSort(array, median + 1, end);
			merge(array, start, median, end);
		}
	}

	private void merge(int[] array, int startIndex, int middleIndex, int endIndex) {
		int[] temp = new int[endIndex - startIndex + 1];
		int i = startIndex;
		int p = middleIndex + 1;
		int index = 0;
		while (i <= middleIndex && p <= endIndex) {
			if (array[i] <= array[p]) {
				temp[index++] = array[i++];
			} else {
				temp[index++] = array[p++];
			}
		}

		int start = i;
		int end = middleIndex;
		if (p <= end) {
			start = p;
			end = endIndex;
		}

		// 将剩余的数据拷贝到临时数组tmp
		while (start <= end) {
			temp[index++] = array[start++];
		}
		// 将tmp中的数组拷贝回a[p...r]
		for (i = 0; i <= endIndex - startIndex; ++i) {
			array[startIndex + i] = temp[i];
		}
	}

}

/**
 * 桶排序
 *
 * @author cl
 */
@Deprecated
class bucketSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < array.length; i++) {
			max = Math.max(max, array[i]);
			min = Math.min(min, array[i]);
		}

		// 桶数
		int bucketNum = (max - min) / array.length + 1;
		ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
		for (int i = 0; i < bucketNum; i++) {
			bucketArr.add(new ArrayList<Integer>());
		}

		// 将每个元素放入桶
		for (int i = 0; i < array.length; i++) {
			int num = (array[i] - min) / (array.length);
			bucketArr.get(num).add(array[i]);
		}

		// 对每个桶进行排序
		for (int i = 0; i < bucketArr.size(); i++) {
			Collections.sort(bucketArr.get(i));
		}
		return array;
	}
	
	
}

/**
 * 计数排序
 * 1、找出待排序的数组中最大和最小的元素
 * 2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项
 * 3、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加
 * 4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
 *
 * @author cl
 */
class CountSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		if (array == null || array.length == 0)
			return array;
		int max = array[0];
		int min = array[0];
		int[] newArr = null;
		for (int i = 0; i < array.length; i++) {
			if (array[i] < min)
				min = array[i];
			if (array[i] > max)
				max = array[i];
		}
		newArr = new int[max - min + 1];
		for (int i = 0; i < array.length; i++) {
			newArr[array[i] - min]++;
		}
		int count = 0;
		for (int i = 0; i < newArr.length; i++) {
			for (int j = 0; j < newArr[i]; j++) {
				array[count++] = i + min;
			}
		}
		return array;
	}
	
}

/**
 * 基数排序
 * 1、将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
 * 2、从最低位开始，依次进行一次排序。
 * 3、这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
 * 时间复杂度是 O(k?n)，其中n是排序元素个数，k是数字位数。
 *
 * @author cl
 */
class RadixSort implements SortAlgorithm {

	@Override
	public int[] sort(int[] array) {
		if (array == null || array.length == 0)
			return array;
		int max = getMax(array);

		// 从最低位开始对数组进行排序
		for (int i = 1; max / i > 0; i *= 10) {
			sort(array, i);
		}
		return array;
	}

	private int getMax(int[] array) {
		int max = array[0];
		for (int i = 1; i < array.length; i++) {
			if (array[i] > max)
				max = array[i];
		}
		return max;
	}

	// 对数组不同的位排序，比如分别对个位、十位、百位排序
	private void sort(int[] arr, int exp) {
		// 存储临时的排序数组
		int[] temp = new int[arr.length];
		int[] buckets = new int[10];

		// 将各个位出现的次数存放在桶中
		for (int i = 0; i < arr.length; i++) {
			buckets[(arr[i] / exp) % 10]++;
		}

		// 找到桶与临时temp的关系
		for (int i = 1; i < 10; i++) {
			buckets[i] += buckets[i - 1];
		}

		// 将数据存储到临时数组temp[]中
		for (int i = arr.length - 1; i >= 0; i--) {
			temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
			buckets[(arr[i] / exp) % 10]--;
		}

		// 将排序好的数据赋值给arr[]
		for (int i = 0; i < arr.length; i++) {
			arr[i] = temp[i];
		}

	}
	
}

至于使用哪种排序方式，可以通过判定数据长度来使用。怎么使用就不在此赘述。

Last Updated:
Contributors: clcheng