排序算法相关

常见的排序算法做出整理：

 

笔试建议使用选择排序，面试建议使用快速排序

 

稳定性：对待排序序列中，值相等的记录，排序前后相对次序不变，称为稳定。

 

冒泡排序：

介绍：双层迭代，比较相邻的数大小，根据结果交换位置

时间复杂度：O(n*n)，读n的平方阶

稳定性：稳定

备注：最慢的排序算法

 

选择排序：

介绍：双层迭代，比较并记录最小的数，并和外层迭代的元素相交换

时间复杂度：O(n*n)

稳定性：不稳定

备注：优于冒泡算法

 

public class ChooseSort {
	public static void main(String[] args) {
		Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
		sort(c);
		for (Comparable data : c) {
			System.out.print(data + " ");
		}
	}

	public static void sort(Comparable[] c) {
		for (int i = 0; i < c.length; i++) {
			Comparable min = c[i]; // 最小值
			int no = i; // 最小值位置
			for (int j = i; j < c.length; j++) {
				if (c[j].compareTo(min) < 0) {
					min = c[j];
					no = j;
				}
			}
			c[no] = c[i];
			c[i] = min;
		}
	}
}

 

 

插入排序：

介绍：小的左边，大的右边

时间复杂度：O(n*n)

稳定性：稳定

备注：大部分已排序时较好

 

快速排序：

介绍：高级冒泡，选第一个值作为中枢数据，左右同时开始比较，一趟排序后保证中枢数据左面的都是小数，右面的都是大数，最后递归排序小数组和大数组。

时间复杂度：O(n*logn)

稳定性：不稳定

备注：效率较好

代码摘自：http://baike.baidu.com/view/19016.htm

 

public class QuickSort {
	public static void sort(Comparable[] data, int low, int high) {
		// 枢纽元,一般以第一个元素为基准进行划分
		Comparable pivotKey = data[low];
		// 进行扫描的指针i,j;i从左边开始,j从右边开始
		int i = low;
		int j = high;
		if (low < high) {
			// 从数组两端交替地向中间扫描
			while (i < j) {
				while (i < j && data[j].compareTo(pivotKey) > 0) {
					j--;
				}// end while
				if (i < j) {
					// 比枢纽元素小的移动到左边
					data[i] = data[j];
					i++;
				}// end if
				while (i < j && data[i].compareTo(pivotKey) < 0) {
					i++;
				}// end while
				if (i < j) {
					// 比枢纽元素大的移动到右边
					data[j] = data[i];
					j--;
				}// end if
			}// end while
			// 枢纽元素移动到正确位置
			data[i] = pivotKey;
			// 前半个子表递归排序
			sort(data, low, i - 1);
			// 后半个子表递归排序
			sort(data, i + 1, high);
		}// end if
	}// end sort

	public static void main(String[] args) {
		// 在JDK1.5版本以上,基本数据类型可以自动装箱
		// int,double等基本类型的包装类已实现了Comparable接口
		Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
		sort(c, 0, c.length - 1);
		for (Comparable data : c) {
			System.out.print(data + " ");
		}
	}
}