welcome to xlongwei.com

欢迎大家一起学习、交流、分享


QQ:9167702333 邮箱:admin@xlongwei.com

Java排序算法学习


分类 Algorithm   关键字 分享   标签 java   algorithm   发布 hongwei  1427285933666
注意 转载须保留原文链接,译文链接,作者译者等信息。  
public static class SortUtil {
	/**
	 * 冒泡排序,O(n^2)
	 */
	public static <E extends Comparable<? super E>> E[] bubbleSort(E[] arr) {
		// 外层从后向前,每次最大的都浮到最后面
		for (int out = arr.length - 1; out > 1; out--) {
			for (int in = 0; in < out; in++) {
				if (arr[in].compareTo(arr[in + 1]) > 0) {
					swap(arr, in, in + 1);
				}
			}
		}
		return arr;
	}

	/**
	 * 冒泡排序,O(n^2)
	 */
	public static <E> E[] bubbleSort(E[] arr, Comparator<? super E> comp) {
		// 外层从后向前,每次最大的都浮到最后面
		for (int out = arr.length - 1; out > 1; out--) {
			for (int in = 0; in < out; in++) {
				if (comp.compare(arr[in], arr[in + 1]) > 0) {
					swap(arr, in, in + 1);
				}
			}
		}
		return arr;
	}

	/**
	 * 插入排序,O(n^2),复制的次数太多
	 */
	public static <E extends Comparable<? super E>> E[] insertSort(E[] arr) {
		insertSort(arr, 0, arr.length - 1);
		return arr;
	}

	/**
	 * 插入排序,O(n^2),复制的次数太多
	 */
	public static <E> E[] insertSort(E[] arr, Comparator<? super E> comp) {
		insertSort(arr, 0, arr.length - 1, comp);
		return arr;
	}

	/**
	 * 归并排序,O(n*log(n)),需要额外的一倍空间
	 * 
	 * @param arr
	 *            需要排序的数组
	 * @return 排好序的数组
	 */
	public static <E extends Comparable<? super E>> E[] mergeSort(E[] arr) {
		E[] temp = arr.clone();
		recMergeSort(arr, temp, 0, arr.length - 1);
		return arr;
	}

	/**
	 * 归并排序,O(n*log(n)),需要额外的一倍空间
	 * 
	 * @param arr
	 *            需要排序的数组
	 * @param comp
	 *            比较器
	 * @return 排好序的数组
	 */
	public static <E> E[] mergeSort(E[] arr, Comparator<? super E> comp) {
		E[] temp = arr.clone();
		recMergeSort(arr, temp, 0, arr.length - 1, comp);
		return arr;
	}

	/**
	 * 划分是快速排序的根本机制,1962年由C.A.R. Hoare发现,O(n*log(n))
	 */
	public static <E extends Comparable<? super E>> E[] quickSort(E[] arr) {
		recQuickSort(arr, 0, arr.length - 1);
		return arr;
	}

	/**
	 * 划分是快速排序的根本机制,1962年由C.A.R. Hoare发现,O(n*log(n))
	 */
	public static <E> E[] quickSort(E[] arr, Comparator<? super E> comp) {
		recQuickSort(arr, 0, arr.length - 1, comp);
		return arr;
	}

	/**
	 * 反转数组
	 */
	public static <E> E[] reverse(E[] arr) {
		// 前arr.length/2个元素与后面交换位置
		for (int i = 0; i < arr.length / 2; i++) {
			swap(arr, i, arr.length - 1 - i);
		}
		return arr;
	}

	/**
	 * 选择排序,O(n^2)
	 */
	public static <E extends Comparable<? super E>> E[] selectSort(E[] arr) {
		for (int out = arr.length - 1; out > 0; out--) {
			int max = -1;
			// 选择最大的
			for (int in = 0; in <= out; in++) {
				if (max == -1) {
					max = in;
				} else if (arr[in].compareTo(arr[max]) > 0) {
					max = in;
				}
			}
			if (max != out) {
				swap(arr, max, out);
			}
		}
		return arr;
	}

	/**
	 * 选择排序,O(n^2)
	 */
	public static <E> E[] selectSort(E[] arr, Comparator<? super E> comp) {
		for (int out = arr.length - 1; out > 0; out--) {
			int max = -1;
			// 选择最大的
			for (int in = 0; in <= out; in++) {
				if (max == -1) {
					max = in;
				} else if (comp.compare(arr[in], arr[max]) > 0) {
					max = in;
				}
			}
			if (max != out) {
				swap(arr, max, out);
			}
		}
		return arr;
	}

	/**
	 * 希尔排序,1959年由Donald
	 * L.Shell发现,基于插入排序,但时间复杂度为O(n*log(n)^2),n-增量排序,间隔序列由Knuth提出,计算式为h=3*h+1
	 */
	public static <E extends Comparable<? super E>> E[] shellSort(E[] arr) {
		int inner, outer;
		E temp;
		int h = 1, len = arr.length;
		while (h <= len / 3) {
			h = 3 * h + 1;
		}
		while (h > 0) {
			for (outer = h; outer < len; outer++) {
				temp = arr[outer];
				inner = outer;
				while ((inner > h - 1)
						&& (arr[inner - h].compareTo(temp) >= 0)) {
					arr[inner] = arr[inner - h];
					inner -= h;
				}
				arr[inner] = temp;
			}
			h = (h - 1) / 3;
		}
		return arr;
	}

	/**
	 * 希尔排序,1959年由Donald
	 * L.Shell发现,基于插入排序,但时间复杂度为O(n*log(n)^2),n-增量排序,间隔序列由Knuth提出,计算式为h=3*h+1
	 */
	public static <E> E[] shellSort(E[] arr, Comparator<? super E> comp) {
		int inner, outer;
		E temp;
		int h = 1, len = arr.length;
		while (h <= len / 3) {
			h = 3 * h + 1;
		}
		while (h > 0) {
			for (outer = h; outer < len; outer++) {
				temp = arr[outer];
				inner = outer;
				while ((inner > h - 1)
						&& (comp.compare(arr[inner - h], temp) >= 0)) {
					arr[inner] = arr[inner - h];
					inner -= h;
				}
				arr[inner] = temp;
			}
			h = (h - 1) / 3;
		}
		return arr;
	}

	/**
	 * 交换数组元素
	 */
	public static <E> void swap(E[] arr, int i, int j) {
		E t = arr[i];
		arr[i] = arr[j];
		arr[j] = t;
	}

	private static <E extends Comparable<? super E>> void insertSort(
			E[] arr, int left, int right) {
		int in, out;
		for (out = left + 1; out <= right; out++) {
			E t = arr[out];
			in = out;
			// 把比arr[out]大的都向后挪一个位置
			while ((in > left) && (arr[in - 1].compareTo(t) > 0)) {
				arr[in] = arr[in - 1];
				in--;
			}
			arr[in] = t;
		}
	}

	private static <E> void insertSort(E[] arr, int left, int right,
			Comparator<? super E> comp) {
		int in, out;
		for (out = left + 1; out <= right; out++) {
			E t = arr[out];
			in = out;
			// 把比arr[out]大的都向后挪一个位置
			while ((in > left) && (comp.compare(arr[in - 1], t) > 0)) {
				arr[in] = arr[in - 1];
				in--;
			}
			arr[in] = t;
		}
	}

	/**
	 * 快速函数辅助:三数据项取中法
	 */
	private static <E extends Comparable<? super E>> E medianOfThree(
			E[] arr, int left, int right) {
		int center = (left + right) / 2;
		if (arr[left].compareTo(arr[center]) > 0) {
			swap(arr, left, center);
		}
		if (arr[left].compareTo(arr[right]) > 0) {
			swap(arr, left, right);
		}
		if (arr[center].compareTo(arr[right]) > 0) {
			swap(arr, center, right);
		}
		swap(arr, center, right - 1);
		return arr[right - 1];
	}

	/**
	 * 快速函数辅助:三数据项取中法
	 */
	private static <E> E medianOfThree(E[] arr, int left, int right,
			Comparator<? super E> comp) {
		int center = (left + right) / 2;
		if (comp.compare(arr[left], arr[center]) > 0) {
			swap(arr, left, center);
		}
		if (comp.compare(arr[left], arr[right]) > 0) {
			swap(arr, left, right);
		}
		if (comp.compare(arr[center], arr[right]) > 0) {
			swap(arr, center, right);
		}
		swap(arr, center, right - 1);
		return arr[right - 1];
	}

	/**
	 * 归并辅助函数:合并两个片段
	 */
	private static <E extends Comparable<? super E>> void merge(E[] arr,
			E[] temp, int lowerPtr, int highPtr, int upperBound) {
		int j = 0;
		int lowerBound = lowerPtr;
		int mid = highPtr - 1;
		int n = upperBound - lowerBound + 1;
		while ((lowerPtr <= mid) && (highPtr <= upperBound)) {
			if (arr[lowerPtr].compareTo(arr[highPtr]) < 0) {
				temp[j++] = arr[lowerPtr++];
			} else {
				temp[j++] = arr[highPtr++];
			}
		}
		while (lowerPtr <= mid) {
			temp[j++] = arr[lowerPtr++];
		}
		while (highPtr <= upperBound) {
			temp[j++] = arr[highPtr++];
		}
		for (j = 0; j < n; j++) {
			arr[lowerBound + j] = temp[j];
		}
	}

	/**
	 * 归并辅助函数:合并两个片段
	 */
	private static <E> void merge(E[] arr, E[] temp, int lowerPtr,
			int highPtr, int upperBound, Comparator<? super E> comp) {
		int j = 0;
		int lowerBound = lowerPtr;
		int mid = highPtr - 1;
		int n = upperBound - lowerBound + 1;
		while ((lowerPtr <= mid) && (highPtr <= upperBound)) {
			if (comp.compare(arr[lowerPtr], arr[highPtr]) < 0) {
				temp[j++] = arr[lowerPtr++];
			} else {
				temp[j++] = arr[highPtr++];
			}
		}
		while (lowerPtr <= mid) {
			temp[j++] = arr[lowerPtr++];
		}
		while (highPtr <= upperBound) {
			temp[j++] = arr[highPtr++];
		}
		for (j = 0; j < n; j++) {
			arr[lowerBound + j] = temp[j];
		}
	}

	/**
	 * 快速排序基础,划分并初步排序
	 */
	private static <E extends Comparable<? super E>> int partitionIt(
			E[] arr, int left, int right, E pivot) {
		int leftPtr = left;
		int rightPtr = right - 1;
		while (true) {
			while (arr[++leftPtr].compareTo(pivot) < 0) {
				;
			}
			while (arr[--rightPtr].compareTo(pivot) > 0) {
				;
			}
			if (leftPtr >= rightPtr) {
				break;
			} else {
				swap(arr, leftPtr, rightPtr);
			}
		}
		swap(arr, leftPtr, right - 1);// 交换leftPtr和pivot
		return leftPtr;
	}

	/**
	 * 快速排序基础,划分并初步排序
	 */
	private static <E> int partitionIt(E[] arr, int left, int right,
			E pivot, Comparator<? super E> comp) {
		int leftPtr = left;
		int rightPtr = right - 1;
		while (true) {
			while (comp.compare(arr[++leftPtr], pivot) < 0) {
				;
			}
			while (comp.compare(arr[--rightPtr], pivot) > 0) {
				;
			}
			if (leftPtr >= rightPtr) {
				break;
			} else {
				swap(arr, leftPtr, rightPtr);
			}
		}
		swap(arr, leftPtr, right - 1);
		return leftPtr;
	}

	/**
	 * 归并辅助函数:分治递归然后合并
	 */
	private static <E extends Comparable<? super E>> void recMergeSort(
			E[] arr, E[] temp, int lowerBound, int upperBound) {
		if (lowerBound == upperBound) {
			return;
		} else {
			int mid = (lowerBound + upperBound) / 2;
			recMergeSort(arr, temp, lowerBound, mid);
			recMergeSort(arr, temp, mid + 1, upperBound);
			merge(arr, temp, lowerBound, mid + 1, upperBound);
		}
	}

	/**
	 * 归并辅助函数:分治递归然后合并
	 */
	private static <E> void recMergeSort(E[] arr, E[] temp, int lowerBound,
			int upperBound, Comparator<? super E> comp) {
		if (lowerBound == upperBound) {
			return;
		} else {
			int mid = (lowerBound + upperBound) / 2;
			recMergeSort(arr, temp, lowerBound, mid, comp);
			recMergeSort(arr, temp, mid + 1, upperBound, comp);
			merge(arr, temp, lowerBound, mid + 1, upperBound, comp);
		}
	}

	/**
	 * 快速排序辅助函数:划分内排序然后递归
	 */
	private static <E extends Comparable<? super E>> void recQuickSort(
			E[] arr, int left, int right) {
		int size = right - left + 1;
		if (size < 10) {// Knuth建议切割点为9
			insertSort(arr, left, right);
		} else {
			E pivot = medianOfThree(arr, left, right);// 三数据项取中,解决逆序的低效问题,while中>0的比较也不用了(因为left<pivot)
			int partition = partitionIt(arr, left, right, pivot);
			recQuickSort(arr, left, partition - 1);
			recQuickSort(arr, partition + 1, right);
		}
	}

	/**
	 * 快速排序辅助函数:划分内排序然后递归
	 */
	private static <E> void recQuickSort(E[] arr, int left, int right,
			Comparator<? super E> comp) {
		int size = right - left + 1;
		if (size < 10) {// Knuth建议切割点为9
			insertSort(arr, left, right, comp);
		} else {
			E pivot = medianOfThree(arr, left, right, comp);// 三数据项取中,解决逆序的低效问题,while中>0的比较也不用了(因为left<pivot)
			int partition = partitionIt(arr, left, right, pivot, comp);
			recQuickSort(arr, left, partition - 1, comp);
			recQuickSort(arr, partition + 1, right, comp);
		}
	}
}