论坛首页 入门技术论坛

Java 排序方法

浏览 2660 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2012-06-20  

public class SortMain {
	// 用于临时储值
	static int temp = 0;

	public static void main(String[] args) {
		// 需要排序的数据
		int[] Source = { 2, 4, 6, 1, 3, 5, 8, 4, 10, 18 };

		// 冒泡排序法
		// printSource(bubbleSort(Source));

		// 插入排序法
		// printSource(insertSort(Source));

		// 反转数组
		// printSource(reverseSort(Source));

		// 希尔排序法(shell)
		// printSource(shellSort(Source));

		// 选择排序法
		// printSource(selectSort(Source));

		//printSource(Source);
		// 快速排序法
		//printSource(QuickSort(Source, 0, Source.length - 1));
	}

	// 使用冒泡排序法
	public static int[] bubbleSort(int[] Source) {

		// 获取需要排序的数据
		int[] bubbleArray = Source;
		// 进行排序
		for (int i = 0; i < bubbleArray.length; i++)// 从数组第一个元素进行遍历
		{
			for (int j = i + 1; j < bubbleArray.length; j++)// 从下标为i+1的元素进行遍历
			{
				if (bubbleArray[i] > bubbleArray[j])// 对bubbleArray[i]>bubbleArray[j]进行比较
				{
					temp = bubbleArray[i]; // 将bubbleArray[i]存于临时变量中
					bubbleArray[i] = bubbleArray[j]; // 实现i和j的数据对换操作
					bubbleArray[j] = temp;
				}
			}
		}
		return bubbleArray;
	}
	
	/***
	 * 
	 * @param Source 返回数组
	 * @return
	 * 
	 * 插入排序法 Insertion Sort
	 * 简言之,插入排序就是每一步都讲一个待排数据按其大小插入到已经排序的数据中的
	 * 适当位置,知道全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种,
	 * 这里只介绍直接插入排序。
	 */
	// 使用插入排序法
	public static int[] insertSort(int[] Source) {
		// 获取需要排序的数据
		int[] insertSort = Source;

		// 开始执行插入排序
		for (int i = 1; i < insertSort.length; i++) {
			for (int j = 0; j < i; j++) {
				if (insertSort[j] > insertSort[i]) {
					temp = insertSort[i];
					insertSort[i] = insertSort[j];
					insertSort[j] = temp;
				}
			}
		}
		return insertSort;
	}

	// 反转数组法
	public static int[] reverseSort(int[] Source) {
		// 获取需要排序的数据
		int[] reverseSort = Source;

		for (int i = 0; i < reverseSort.length / 2; i++) {
			temp = reverseSort[i];
			reverseSort[i] = reverseSort[reverseSort.length - i - 1];
			reverseSort[reverseSort.length - 1 - i] = temp;
		}

		return reverseSort;
	}

	// 希尔排序法
	public static int[] shellSort(int[] Source) {
		for (int increment = Source.length / 2; increment >= 2; increment /= 2) {
			// System.out.print(increment+"\t");
			System.out.println();
			for (int i = 0; i < increment; i++) {
				insertSource(Source, i, increment);
			}
		}
		System.out.println();
		// System.out.println("执行最后一步");
		printSource(Source);
		// System.out.println("执行完毕");
		insertSource(Source, 0, 1);
		// System.out.println();

		return Source;
	}

	// 希尔排序法中的调用方法
	public static void insertSource(int[] Source, int start, int inc) {
		System.out.print("start:" + start + "inc:" + inc + "\t");
		System.out.println();
		int temp;
		for (int i = start + inc; i < Source.length; i += inc) {
			System.out.println("i-------:" + i);
			for (int j = i; j >= inc; j -= inc) {
				System.out.println("j:" + j);
				if (Source[j] < Source[j - inc]) {
					temp = Source[j];
					Source[j] = Source[j - inc];
					Source[j - inc] = temp;
				}
			}
		}
	}

	/***
	 * 
	 * @param Source
	 * @return
	 * 选择排序法 Selecttion Sort
	 * 选择排序的基本思想是:对待排序的记录序列进行n-1遍的处理,第一遍是将L[1..n]中
	 * 的最小者与L[1]交换位置,第二遍处理是讲L[2..n]中的最小者与L[2]交换位置,....,第i遍
	 * 处理是讲L[i..n]中的最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置就已
	 * 经从小到大的顺序排列好了。
	 * 
	 * 选择排序于冒泡排序的区别:冒泡排序每次比较后,如果发现书序不对立即进行交换,而选择排序
	 * 不立即进行交换,而是找出最小的元素后在进行交换
	 */
	// 选择排序法
	public static int[] selectSort(int[] Source) {
		// 获取需要排序的数据
		int[] selectSort = Source;

		int index;
		for (int i = 0; i < selectSort.length; i++) {
			index = i;
			for (int j = i + 1; j < selectSort.length; j++) {
				if (selectSort[index] > selectSort[j]) {
					index = j;
				}
			}
			temp = selectSort[i];
			selectSort[i] = selectSort[index];
			selectSort[index] = temp;
		}
		return selectSort;
	}

	
	/***
	 * 快速排序法
	 * 快速排序是对冒泡排序的一种改进,它的基本思想是:通过一趟排序将排序的数据分割
	 * 成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此
	 * 方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数
	 * 据变成有序序列
	 */
	// 快速排序法
	static boolean bool = true;

	public static int[] QuickSort(int[] Source, int left, int right) {
		int i = left;
		int j = right;
		int temp = 0;
		int between = Source[(left + right) / 2];
		do {
			while (Source[i] < between && i <= right) {
				i++;
			}
			while (Source[j] > between && j >= left) {
				j--;
			}

			if (i <= j) {
				temp = Source[i];
				Source[i] = Source[j];
				Source[j] = temp;

				i++;
				j--;
			}

			/*if (bool) {
				printSource(Source);
				bool = false;
			}*/

		} while (i <= j);

		printSource(Source);

		if (left < j) {
			QuickSort(Source, left, j);
		}

		if (right > i) {
			QuickSort(Source, i, right);
		}

		return Source;
	}

	// 打印方法
	public static void printSource(int[] Source) {
		for (int i = 0; i < Source.length; i++) {
			System.out.print(Source[i] + "\t");
		}
		System.out.println();
	}
}
 
   发表时间:2012-07-10  
LZ总结的不错
0 请登录后投票
   发表时间:2012-08-13  
Collections和Arrays是干嘛的
0 请登录后投票
论坛首页 入门技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics