java 排序算法

package endual.paixu;

import java.util.Arrays;

/**
 * 选择排序 时间复杂度是n的平方
 * 
 * @author endual
 * 
 **/
public class PaiXu {

	private static int[] arrs = { 2, 5, 2, 3, 5, 778, 45, 23, 123, 1, 45, 74,
			98 };
	private static int[] temp = new int[arrs.length];

	public static void main(String[] args) {
		PaiXu.mian();
	}

	private static void mian() {

		int[] arr = PaiXu.jishu(arrs);
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}

	}

	// --------------------------最开始当然是冒泡算法-------------------------------------------------------
	/**
	 * 冒泡算法是最早接触到是排序算法，当时的我还在C语言课程发呆，狂想， 当然我还记得我课本上的那副冒泡的图，希望下面的代码没有敲错
	 * 
	 * 最开始当然是冒泡算法，冒泡算法我看到过三个形式，真是坑爹啊，三种啊，有木有。当然我只提供一种写法
	 * 
	 * @param arrs
	 * @return
	 */
	public static int[] maopao_1(int[] arrs) {

		for (int i = 0; i < arrs.length; i++) {

			for (int j = arrs.length - 1; j > i; j--) { // arrs[0]是顶部，从最后面的一个冒上来

				int temp = arrs[j];
				if (temp < arrs[j - 1]) {

					arrs[j] = arrs[j - 1];
					arrs[j - 1] = temp;
					temp = arrs[j]; // 把小的值
				}
			}
		}
		return arrs;
	}

	// ----------------------------------------------选择排序-----------------------------------------------------------

	/**
	 * 从小到大的排序
	 * 
	 * @param arrs
	 * @return 选择排序，不稳定的排序 算法描述： 我有一排书，要把书从低到高排列在书架上，那么，我首先把书仍在地上，然后选择最低的那一本书
	 *         放在书架上，然后在选择最低的那本书放在书架上，然后再选择最低的那本书放在书架上。
	 * 
	 *         特点：移动数的次数变少了
	 * 
	 */
	public static int[] xuanzhe(int[] arrs) {

		for (int i = 0; i < arrs.length; i++) {

			int temp = arrs[i];
			int index = i;
			for (int j = i + 1; j < arrs.length; j++) { // 每次都找到一个最小数，这里并没有移动数字

				if (arrs[j] < temp) {
					temp = arrs[j];
					index = j;
				}
			} // end for
			if (i != index) {
				arrs[index] = arrs[i]; // 最小的数与开头的数的位子进行调换，这里才是移动了数字
				arrs[i] = temp;
			}

		}

		return arrs;
	}

	// -----------------------------------------
	// 插入算法-------------------------------------------------------------------------
	/**
	 * 插入算法
	 * 
	 * @param arrs
	 * @return
	 * 
	 *         算法描述：描述的还是书架的排书的问题。一些列书放着， 第一本书已经放好了， 第二本书看看高度和第一本书比较，
	 *         如果是高，那么正常不动
	 *         如果是低，那么拿出第二本书（这个时候，第二本书的位置是空的），然后把第一本书移动到第二本书的位置上（这个时候
	 *         ，第一本书的位置是空的），然后把第二本书插入到第一本书的位置上。 第三本书看看高度和第二本书进行比较， 如果是高，那么不动
	 *         如果是低：那就拿出第三本书（这个时候，第三本书的位置是空的），然后把第二本书放到第三本的位置上（这个时候，第二本书的位置是空的），
	 *         然后和第一本书进行比较， 如果是高，那么就插入到第二本书的位子中
	 *         如果是低，那么第一本放到第二本书的位置上（这个时候，第一本书的位置是空的），然后把第三本放到第一本书的位置上
	 *         第四本书看看高度和第三本书比较下， 如果是高，那么不动
	 *         如果是低，那么就拿出第四本书（这个时候，第四本书的位置是空的），然后把第三本书移动到低四本书的位置上
	 *         （这个时候，第三本书的位置是空的）， 然后和第二本书进行比较： 如果是高，那么就放到第三本的位置上，
	 *         如果是低，那么把第二本书移动到第三本的位置上（这个时候，第二本书的位置是空的）， 然后把第三本书和第一本书进行比较
	 *         如果是高，那么可以插入到第二本书的位置上 如果是低：那么把第一本书移动到第二本书的位置上，然后把第四本书插入到第一本书的位置上
	 *         第五本书：。。。。。。。。。。。。。。。。 特点：
	 * 
	 */
	public static int[] charu(int[] arrs) {

		for (int i = 0; i < arrs.length; i++) {

			int j = i; // 貌似多余的，不过是为了区别操作时的分段更加清晰
			int tempPro = arrs[j];
			while (j > 0 && (tempPro < arrs[j - 1])) {
				arrs[j] = arrs[j - 1]; // 我要把位置换过来,移动位置
				j--;
			}
			arrs[j] = tempPro; // 一次覆盖
		}

		return arrs;
	}

	/**
	 * 想法也是插入算法
	 * 
	 * @param arrs
	 * @return
	 */
	public static int[] charu_3(int[] arrs) {

		for (int i = 0; i < arrs.length; i++) {

			for (int j = i; j > 0; j--) {
				int temp = arrs[j];
				if (temp < arrs[j - 1]) {
					arrs[j] = arrs[j - 1];
					arrs[j - 1] = temp; // 这一步有点牵强啊，把不需要移动的数也移动了
				} else {
					break;
				}
			}
		}

		return arrs;
	}

	/**
	 * 这个写法其实和标准的写法是一样的，只不是写法不一样而已，其实这样更加的清晰了
	 */
	public static int[] charu_2(int[] arrs) {

		for (int i = 0; i < arrs.length; i++) {

			int j = i;
			int tempPro = 0;
			tempPro = arrs[j];
			while (j > 0) {
				if (tempPro < arrs[j - 1]) {
					arrs[j] = arrs[j - 1]; // 我要把位置换过来,移动位置
					j--;
				} else {
					break;
				}
			}
			arrs[j] = tempPro; // 一次覆盖
		}

		return arrs;
	}

	// ------------------------------------------排序
	// 希尔排序-----建议间距是n/2-------------------------------------------------------------
	/**
	 * 希尔排序是插入排序的一个变种，你看我们插入的时候，往往都是后面一个队前面一个比较，而希尔排序的核心就是对插入排序进行修改，
	 * 使之对由索引间距相等的元素构成的字数组进行排序
	 * 将一个数组通过等间距的提取数组中的数，组成等间距的子数组，再有子数组中每组提取一个最小的，一次提取，进行排列；
	 * 然后在减小等间距的距离，再一次的进行重新排列，知道最后的间距为1结束。 一般开始的间距为数组长度的n/2
	 * 
	 * @param arrs
	 * @return
	 */

	public static int[] shellSort(int[] arr) {
		int i, j, n = 1, temp, len = arr.length;

		while (n <= len / 2) { // 间距的控制,设定好间距一定要保证为1的存在
			n = n * 2 + 1; // 经典的设计
		}

		// int n =
		while (n > 0) {
			for (i = n; i < len; i++) {
				temp = arr[i];
				j = i;
				while (j >= n && arr[j - n] >= temp) {
					arr[j] = arr[j - n];
					j -= n;
				}
				arr[j] = temp;
			}
			n = (n - 1) / 2; // 调整间距
			System.out.println("---" + n);
		}

		return arr;
	}

	// ---------------这个写法不怎么清晰思路，第二种写法比较好------------------归并排序算法-----有点难度了，基本上需要上网在查找下资料才能读懂意思-------------------------------------
	/**
	 * 归并排序 (Merge sort) 将一个数组分成两半，对着两半分别排序，再将他们归并为一个有序数组。 归并排序的算法通常是用 递归 实现的。
	 * 这是一种分治法的算法
	 * 
	 * 描述： 假设有两个数组分别各自有序，归并两个有序数组并非难事，但需要一个附加的数组。从头到尾处理这两个数组，将一个数组中的
	 * 一个元素与另一个数组中的一个元素进行比较，并将较小的元素复制到第三个新的数组中去。在达到其中一个数组的末尾时，
	 * 只需将另一个数组中剩余的元素复制到第三个新的数组中去。
	 * 
	 * 算法描述：在归并排序中，待归并的两个有序数组实际上是原来数组的两半。也就是说，将原来数组分成两半，对着两半分别排序，
	 * 将排序后的这两半归并为第二个临时数组。然后再将这个临时数组复制回原来数组。
	 * 
	 * @param arrs
	 * @return
	 * 
	 *         第一个参数： 第二个参数： 第三个参数：l是的哥参数的数组的最小下表 第四个参数：r是第一个参数的数组的最大下标
	 * 
	 * 
	 */
	public static int[] guibin(int[] data, int[] temp, int stIndex, int endIndex) {

		if (stIndex == endIndex) { // 递归停止的条件
			return data;
		}

		int mid = (stIndex + endIndex) / 2; // 获取数组的中间数
		guibin(data, temp, stIndex, mid);
		guibin(data, temp, mid + 1, endIndex);

		for (int i = stIndex; i <= endIndex; i++) { // 将data中数据复制到中间的数组中去
			temp[i] = data[i];
		}

		int i1 = stIndex;
		int i2 = mid + 1;

		for (int cur = stIndex; cur <= endIndex; cur++) {

			if (i1 == mid + 1)
				data[cur] = temp[i2++];

			else if (i2 > endIndex)
				data[cur] = temp[i1++];

			else if (temp[i1] < temp[i2])
				data[cur] = temp[i1++];
			else
				data[cur] = temp[i2++];
		}
		return data;
	}

	// 归并排序------------------这个写法比较的标准---------------------------------------------------------
	public static void mergeSort(int[] arrs) {
		int stLeft = 0;
		int endRight = arrs.length - 1;
		// 归并排序
		sort(arrs, stLeft, endRight);
	}

	public static void sort(int[] data, int left, int right) {
		if (left >= right) // 停止的条件
			return;
		// 找出中间索引
		int center = (left + right) / 2;
		// 对左边数组进行递归
		sort(data, left, center);
		// 对右边数组进行递归
		sort(data, center + 1, right);
		// 合并
		merge(data, left, center, right);
		print(data);
	}

	/**
	 * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
	 * 
	 * @param data
	 *            数组对象
	 * @param left
	 *            左数组的第一个元素的索引
	 * @param center
	 *            左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
	 * @param right
	 *            右数组最后一个元素的索引
	 */
	public static void merge(int[] data, int left, int center, int right) {
		// 临时数组
		int[] tmpArr = new int[data.length];
		// 右数组第一个元素索引
		int mid = center + 1;
		// third 记录临时数组的索引
		int third = left;
		// 缓存左数组第一个元素的索引
		int tmp = left;
		while (left <= center && mid <= right) { // 每一次while比较，从两个数组（data数组中，以mid为点，前面是一组，后面是一组）中取出最小的放入临时数组

			if (data[left] <= data[mid]) { // 左边组和右边组的比较
				tmpArr[third] = data[left];
				third++; // 临时数组中，存入了数，那么就向后移动一位
				left++; // 左边组移动一位
			} else {
				tmpArr[third] = data[mid];
				third++; // 临时数组每次比较都要移动一位的
				mid++; // 右边组移动一位
			}

		}

		// 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
		while (mid <= right) { // 说明右边数组还要树没有用完成，那么前部复制到temp这个临时数组中去
			tmpArr[third++] = data[mid++];
		}
		while (left <= center) { // 说明左边数组还要树没有用完成，那么前部复制到temp这个临时数组中去
			tmpArr[third++] = data[left++];
		}
		// 将临时数组中的内容拷贝回原数组中
		// （原left-right范围的内容被复制回原数组）
		while (tmp <= right) {
			data[tmp] = tmpArr[tmp];
			tmp++;
		}
	}

	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}

	// ---------------------------------快速排序算法------------------------------------------
	// 快速排序算法
	/**
	 * 快速排序将数组分成两部分，但与归并排序不同的是，这两部分不吸烟是数组的两半，相反，快速排序从数组中选出一个元素， 称为
	 * 支点，然后重现排列数组元素，使得 1.支点所处的位置是读校园火灾等于支点 2.支点前的元素都是小于或者是等于支点，
	 * 3.支点后面的元素都是大于或者等于支点的
	 * 
	 * @param arrs
	 * @return
	 */
	public static int[] kuaisu(int[] datax) {

		int[] data = { 1, 1, 1, 2, 1, 1, 1 };
		quickSort(data, 0, data.length - 1);
		System.out.println("排序后的数组：");
		print(data);
		return data;
	}

	public static void swap(int[] data, int i, int j) {
		// if (i == j) {
		// return;
		// }
		// 交换下位置
		int temp = data[j];
		data[j] = data[i];
		data[i] = temp;

		// data[i] = data[i] + data[j];
		// data[j] = data[i] - data[j];
		// data[i] = data[i] - data[j];
	}

	public static void quickSort(int[] data, int start, int end) {
		if (start >= end)
			return;

		// 以起始索引为分界点
		int pivot = data[start];
		int i = start + 1; // 右边的位置n-1,其中n是数组的长度
		int j = end;

		while (true) { // 真的支点是data[j],右边是大于这个data[j]的
			while (i <= end && data[i] <= pivot) {
				i++;
			}
			while (j > start && data[j] > pivot) {
				j--;
			}
			if (i < j) {
				swap(data, i, j);
			} else {
				break;
			}
		}

		// 交换 j和分界点的值
		swap(data, start, j);
		print(data);
		// 递归左子序列
		quickSort(data, start, j - 1);
		// 递归右子序列
		quickSort(data, j + 1, end);
	}

	// ---------------------------------基数排序算法------------------------------------------
	/**
	 * 基数排序是不基于数对数的比较的，而是运用了排列的方法，0到9一共10个数，每个数都是0到9这些数字够成了，
	 * 在一个数组中，有一个最大值，那么它是几位的，其他的数字就是几位的，比如12345，这个数在数组中最大，是五位的， 其他用0在数字前面步位，比如
	 * 1，45,12345 ===》》00001,00045,12345，然后按照最后一位开始，放入到对应的
	 * 数组桶中，有一个顺序，然后按照倒数第二个数，再次放入桶中。。。依次下去。。。。。
	 * 
	 * 正规描述
	 * 基数排序已经不再是一种常规的排序方式，它更多地像一种排序方法的应用，基数排序必须依赖于另外的排序方法。
	 * 基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。
	 * 多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字
	 * ；第1个排序关键字，第2个排序关键字，第3个排序关键字......然后，根据子关键字对待排序数据进行排序。 多关键字排序时有两种解决方案：
	 * 最高位优先法（MSD）(Most Significant Digit first) 最低位优先法（LSD）(Least Significant
	 * Digit first) 例如，对如下数据序列进行排序。 192,221,12,23
	 * 可以观察到它的每个数据至多只有3位，因此可以将每个数据拆分成3个关键字：百位（高位）、十位、个位（低位）。
	 * 如果按照习惯思维，会先比较百位，百位大的数据大，百位相同的再比较十位，十位大的数据大；最后再比较个位。人得习惯思维是最高位优先方式。
	 * 如果按照人得思维方式
	 * ，计算机实现起来有一定的困难，当开始比较十位时，程序还需要判断它们的百位是否相同--这就认为地增加了难度，计算机通常会选择最低位优先法。
	 * 基数排序方法对任一子关键字排序时必须借助于另一种排序方法，而且这种排序方法必须是稳定的。
	 * 对于多关键字拆分出来的子关键字，它们一定位于0-9这个可枚举的范围内，这个范围不大，因此用桶式排序效率非常好。
	 * 对于多关键字排序来说，程序将待排数据拆分成多个子关键字后，对子关键字排序既可以使用桶式排序，也可以使用任何一种稳定的排序方法。
	 * 
	 * 
	 * @param data
	 * @return
	 */
	public static int[] jishu(int[] data) {
		// data = new int[] { 1100, 192, 221, 12, 23 };
		int end = data.length ;
		radixSort(data, 10, end);
		System.out.println("排序后的数组：");
		return data;
	}

	public static void radixSort(int[] data, int radix, int d) {
		// 缓存数组
		int[] tmp = new int[data.length];
		// buckets用于记录待排序元素的信息
		// buckets数组定义了max-min个桶
		int[] buckets = new int[radix]; //10个桶

		for (int i = 0, rate = 1; i < d; i++) {

			// 重置count数组，开始统计下一个关键字，将buckets,里面的数组全部填充为0
			Arrays.fill(buckets, 0);
//			for (int ii=0; ii<buckets.length; ii++)
//				buckets[ii] = 0; 
//          以上的for循环，功能就是Arrays.fill()函数的功能			
			
			// 将data中的元素完全复制到tmp数组中
			System.arraycopy(data, 0, tmp, 0, data.length);
			// 计算每个待排序数据的子关键字
			for (int j = 0; j < data.length; j++) {
				int subKey = (tmp[j] / rate) % radix;
				buckets[subKey]++;
			}

			for (int j = 1; j < radix; j++) {
				buckets[j] = buckets[j] + buckets[j - 1];
			}

			// 按子关键字对指定的数据进行排序
			for (int m = data.length - 1; m >= 0; m--) {
				int subKey = (tmp[m] / rate) % radix;
				data[--buckets[subKey]] = tmp[m];
			}
			rate *= radix;
		}

	}

	// ---------------------------------桶数排序算法------------------------------------------
	/**
	 * 桶式排序不再是一种基于比较的排序方法，它是一种比较巧妙的排序方式，但这种排序方式需要待排序的序列满足以下两个特征：
	 * 待排序列所有的值处于一个可枚举的范围之类； 待排序列所在的这个可枚举的范围不应该太大，否则排序开销太大。 排序的具体步骤如下：
	 * （1）对于这个可枚举范围构建一个buckets数组，用于记录“落入”每个桶中元素的个数；
	 * （2）将（1）中得到的buckets数组重新进行计算，按如下公式重新计算： buckets[i] = buckets[i]
	 * +buckets[i-1] (其中1<=i<buckets.length);
	 * 
	 * @param data
	 * @return
	 */
	public static int[] tong(int[] data) { // 也叫“计数排序”

		data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
		bucketSort(data, 0, data.length + 1);
		return data;
	}

	public static void bucketSort(int[] data, int min, int max) {
		// 缓存数组
		int[] tmp = new int[data.length];
		// buckets用于记录待排序元素的信息
		// buckets数组定义了max-min个桶
		int[] buckets = new int[max - min];
		// 计算每个元素在序列出现的次数
		for (int i = 0; i < data.length; i++) {
			buckets[data[i] - min]++;
		}
		// 计算“落入”各桶内的元素在有序序列中的位置
		for (int i = 1; i < max - min; i++) {
			buckets[i] = buckets[i] + buckets[i - 1];
		}
		// 将data中的元素完全复制到tmp数组中
		System.arraycopy(data, 0, tmp, 0, data.length);
		// 根据buckets数组中的信息将待排序列的各元素放入相应位置
		for (int k = data.length - 1; k >= 0; k--) {
			data[--buckets[tmp[k] - min]] = tmp[k];
		}
	}

}

 

总结

前面讲了10种基本的排序算法，现在来作下总结，基于下面几个方面来比较各个排序算法的优劣：

时间复杂度，空间复杂度，稳定性，适用场景

排序算法	时间复杂度	空间复杂度	稳定性	适用场景
直接选择排序	O(n^2)	O(1)	不稳定	时间效率不高，但是空间效率很高，算法实现比较简单
堆排序	O(nlogn),底数为2	O(1)	不稳定	时间效率很高，但是不稳定
冒泡排序	O(n^2)	O(1)	稳定	算法实现比较简单，稳定，且对于已基本排序的数据排序，时间复杂度为O(n)
快速排序	最好O(nlogn),底数为2  最坏O(n^2) 平均O(nlogn),底数为2	O(logn),底数为2	不稳定	时间效率很高，但是不稳定
直接插入排序	O(n^2)	O(1)	稳定
折半插入排序	O(n^2)	O(1)	稳定	时间效率比直接插入排序要好
希尔排序	O(n(logn)^2),底数为2	O(1)	不稳定
归并排序	O(nlogn),底数为2	O(n)	稳定	空间复杂度较高
桶式排序	O(k+n)	O(k+n)	稳定	待排序数据的范围在0~k之间，只能为整形序列
基数排序			稳定	依赖子关键字排序算法，子关键字排序算法必须是稳定的

 

推荐博客：http://blog.csdn.net/apei830/article/details/6596146

推荐书籍：http://book.360buy.com/10058405.html  数据结构与算法分析Java语言描述（第2版）

                 http://book.360buy.com/10079271.html  数据结构与算法分析：Java语言描述（第2版）