雨城Java教程系列——常用排序算法

 

周末憋在家里，复习了一下正则表达式，及常用排序算法，再此小写一篇博文，算是这两日的工作报告了，（~_~）....

 

常见排序算法(一)→冒泡排序

冒泡排序算法的思想：很简单，每次遍历完序列都把最大（小）的元素放在最前面，然后再对剩下的序列从父前面的一个过程，每次遍历完之后待排序序列就少一个元素，当待排序序列减小为只有一个元素的时候排序就结束了。因此，复杂度在最坏的情况下是O（N ^ 2）

 

package com.syc.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 * 
 * @author Michael
 * @time 9:47:21 PM
 * @date Sep 23, 2012
 */
public class BubbleSort {
	static int[] num = { 1, 21, 4, 3, 56, 65, 33, 67, 2222, 666 };

	public static void main(String[] args) {
		Arrays.sort(num);
		showArray(num);
	}

	/**
	 * From min to max（冒泡排序1）
	 */
	public static void fromMintoMax1() {
		// int[] num = { 1, 21, 4, 3, 56, 65, 33, 67, 2222, 666 };
		for (int i = 0, len = num.length; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (num[i] > num[j]) {
					int temp = num[i];
					num[i] = num[j];
					num[j] = temp;
				}
			}
		}
	}

	/**
	 * From min to max（冒泡排序2，已优化）
	 */
	public static void fromMintoMax2() {
		for (int i = 0, len = num.length; i < len; i++) {
			int k = i;
			for (int j = k + 1; j < len; j++) {
				if (num[j] < num[k]) {
					k = j;
				}
			}
			if (k != i) {
				int temp = num[k];
				num[k] = num[i];
				num[i] = temp;
			}
		}
		showArray(num);
	}

	/**
	 * From min to max（冒泡排序3，已优化，效率较前两种高）
	 */
	public static void fromMintoMax3() {
		int k, temp;
		for (int i = 0, len = num.length; i < len; i++) {
			k = i;
			for (int j = k + 1; j < len; j++) {
				if (num[j] < num[k]) {
					k = j;
				}
			}
			if (k != i) {
				temp = num[k];
				num[k] = num[i];
				num[i] = temp;
			}
		}
		showArray(num);
	}

	/**
	 * From mxx to min（冒泡排序1）
	 */
	public static void fromMaxtoMin1() {
		for (int i = 0, len = num.length; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (num[i] < num[j]) {
					int temp = num[i];
					num[i] = num[j];
					num[j] = temp;
				}
			}
		}
		showArray(num);
	}

	/**
	 * From mxx to min（冒泡排序2,已优化，）
	 */
	public static void fromMaxtoMin2() {
		for (int i = 0, len = num.length; i < len; i++) {
			int k = i;
			for (int j = k + 1; j < len; j++) {
				if (num[j] > num[k]) {
					k = j;
				}
			}
			if (k != i) {
				int temp = num[k];
				num[k] = num[i];
				num[i] = temp;
			}
		}

		showArray(num);
	}

	/**
	 * 
	 * @param array
	 */
	public static void showArray(int[] array) {
		for (int arr : array) {
			System.out.print(arr + " ");
		}
		System.out.println("");
	}

}

 

 

 

常见排序算法(二)→插入排序

插入排序是最简单最直观的排序算法了，它的依据是：遍历到第N个元素的时候前面的N-1个元素已经是排序好的了，那么就查找前面的N-1个元素把这第N个元素放在合适的位置，如此下去直到遍历完序列的元素为止。

　算法的复杂度也是简单的，排序第一个需要1的复杂度，排序第二个需要2的复杂度，因此整个的复杂度就是：
　1 + 2 + 3 + …… + N = O（N ^ 2）的复杂度。

 

 

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。

最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。

最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。

插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。

因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

Java实现：

 

package com.syc.sort;

/**
 * 
 * @author Michael
 * @time 9:17:30 PM
 * @date Sep 23, 2012
 */
public class InsertSort {
	/**
	 * 
	 * @param array
	 */
	public static void showArray(int[] array) {
		for (int arr : array) {
			System.out.print(arr + " ");
		}
		System.out.println("");
	}

	/**
	 * 
	 * @param array
	 */
	public static void insertSort(int[] array) {
		int index;
		for (int i = 1; i < array.length; i++) {
			int currentData = array[i];
			for (index = i; (index > 0) && (currentData < array[index - 1]); index--) {
				array[index] = array[index - 1];
			}
			array[index] = currentData;
			showArray(array);
		}
	}

	public static void main(String[] args) {
		int[] array = { 9, 2, 7, 3 };
		insertSort(array);
	}
}

 

 

 

 

---------------