【2015工作总结】排序算法

排序算法汇总：

	时间复杂度	空间复杂度
稳定排序
气泡排序	最差、平均都是O(n²)，最好是O(n)	1
鸡尾酒排序	最差、平均都是O(n²)，最好是O(n)	1
插入排序	最差、平均都是O(n²)，最好是O(n)	1
归并排序	最差、平均、最好都是O(nlog n)	O(n)
桶排序	O(n)	O(n)
基数排序	O(dn)	O(n)
二叉树排序	O(nlog n)	O(n)
图书馆排序	O(nlog n)	O(n)
不稳定排序
选择排序	最差、平均都是O(n²)	1
希尔排序	O(nlog n)	1
堆排序	最差、平均、最好都是O(nlog n)	1
快速排序	平均是O(nlog n)，最坏是O(n²)	O(nlog n)

 

排序算法解释：

1	大部分程序的大部分指令之执行一次，或者最多几次。 如果一个程序的所有指令都具有这样的性质，我们说这个程序的执行时间是常数。
logN	如果一个程序的运行时间是对数级的，则随着N的增大程序会渐渐慢下来， 如果一个程序将一个大的问题分解成一系列更小的问题， 每一步都将问题的规模缩减成几分之一，一般就会出现这样的运行时间函数。 在我们所关心的范围内，可以认为运行时间小于一个大的常数。 对数的基数会影响这个常数，但改变不会太大： 当N=1000时，如果基数是10，logN等于3；如果基数是2，logN约等于10. 当N=1 00 000，logN只是前值的两倍。 当N时原来的两倍，logN只增长了一个常数因子： 仅当从N增长到N平方时，logN才会增长到原来的两倍。
N	如果程序的运行时间的线性的，很可能是这样的情况： 对每个输入的元素都做了少量的处理。 当N=1 000 000时，运行时间大概也就是这个数值； 当N增长到原来的两倍时，运行时间大概也增长到原来的两倍。 如果一个算法必须处理N个输入（或者产生N个输出），那么这种情况是最优的。
NlogN	如果某个算法将问题分解成更小的子问题，独立地解决各个子问题， 最后将结果综合起来，运行时间一般就是NlogN。 我们找不到一个更好的形容，就暂且将这样的算法运行时间叫做NlogN。 当N=1 000 000时，NlogN大约是20 000 000。 当N增长到原来的两倍，运行时间超过原来的两倍，但超过不是太多。
N平方	如果一个算法的运行时间是二次的（quadratic）， 那么它一般只能用于一些规模较小的问题。 这样的运行时间通常存在于需要处理每一对输入数据项的算法 （在程序中很可能表现为一个嵌套循环）中， 当N=1000时，运行时间是1 000 000； 如果N增长到原来的两倍，则运行时间将增长到原来的四倍。
N三次方	类似的，如果一个算法需要处理输入数据想的三元组 （很可能表现为三重嵌套循环）， 其运行时间一般就是三次的，只能用于一些规模较小的问题。 当N=100时，运行时间就是1 000 000； 如果N增长到原来的两倍，运行时间将会增长到原来的八倍。
2的N次方	如果一个算法的运行时间是指数级的（exponential）， 一般它很难在实践中使用，即使这样的算法通常是对问题的直接求解。 当N=20时，运行时间是1 000 000； 如果增长到原来的两倍时，运行时间将是原时间的平方！

 

排序算法-冒泡排序：

  // 冒泡排序
	public static void bubbleSort(int[] source) {
		if (null != source && source.length > 0)
		for (int i = source.length - 1; i > 0; i--)
			for (int j = 0; j < i; j++)
				if (source[j] > source[j + 1])
					swap(source, j, j + 1);
	}
	// 数组两个位置的值互换
	public static void swap(int[] source, int x, int y) {
		int temp = source[x];
		source[x] = source[y];
		source[y] = temp;
	}
	// 数组打印控制台
	public static void print(int[] source) {
		for (int i : source) 
			System.out.print(i+" ");
	}

	public static void main(String[] args) {
		int[] a = {4,2,1,6,3,6,0,-5,1,1};
		bubbleSort(a);
		print(a);
	}

 

排序算法-选择排序：

	//选择排序
	public static void selectSort(int[] source) {
		if (null != source && source.length > 0)
			for (int i = 0; i < source.length; i++)
				for (int j = i + 1; j < source.length; j++)
					if (source[i] > source[j])
						swap(source, i, j);
	}
	public static void main(String[] args) {
		int[] a = {4,2,1,6,3,6,0,-5,1,1};
		selectSort(a);
		print(a);
	}

 

排序算法-插入排序：

	// 插入排序
	public static void insertSort(int[] source) {
		if (null != source && source.length > 0)
			for (int i = 1; i < source.length; i++)
				for (int j = i; (j > 0) && (source[j] < source[j - 1]); j--)
					swap(source, j , j - 1);
	}
	public static void main(String[] args) {
		int[] a = {4,2,1,6,3,6,0,-5,1,1};
		insertSort(a);
		print(a);
	}

 

排序算法-Shell排序

	// Shell排序
	public static void shellSort(int[] source, int index) {
		int i, j, k;			// 循环计数变量
		int temp;			// 暂存变量
		boolean change;	// 数据是否变化
		int dataLength;	// 分隔集合的间隔长度
		int pointer;		// 进行处理的位置
		
		dataLength = index / 2;	// 初始集合间隔长度
		while (dataLength != 0) {	// 数列仍可进行分隔
			// 对每个集合进行处理
			for (j = dataLength; j < index; j++) {
				change = false;
				temp = source[j];					// 暂存data[j]的值，待交换值时用
				pointer = j - dataLength;	// 计算进行处理的位置
				// 进行集合内数值的比较
				while (temp < source[pointer] && pointer >= 0 && pointer <= index) {
					source[pointer + dataLength] = source[pointer];
					// 计算下一个欲进行处理的位置
					pointer = pointer - dataLength;
					change = true;
					if (pointer < 0 || pointer > index)
						break;
				}
				// 于最后的数值交换
				source[pointer + dataLength] = temp;
				
				if (change) {
					// 打印目前排序结果
					System.out.print("排序中：");
					for (k = 0; k < index; k++)
						System.out.printf(" %3s ", source[k]);
					System.out.println("");	
				}
			}
			dataLength = dataLength / 2;	//计算下次分割的间隔长度
		}
	}
	public static void main(String[] args) {
		int[] a = {4,2,1,6,3,6,0,-5,1,1};
		shellSort(a, a.length);
		print(a);
	}

 

排序算法-二分排序：

 

	// 二分排序 查找
	public static int binarySearch(int[] a, int value) {
		int size = a.length;
		int low = 0, high = size - 1;
		int mid;
		while (low <= high) {
			mid = (low + high) / 2;
			if (a[mid] < value) {
				low = low + 1;
			} else if (a[mid] > value) {
				high = high - 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] a = {4,2,1,6,3,6,0,-5,1,1};
		shellSort(a, a.length);
		System.out.println(binarySearch(a,4));
	}

 

排序算法-快速排序

	// 快速排序
	public static void quickSort(int[] source, int low, int high) {
		int i, j, x;
		if (low < high) {
			i = low;
			j = high;
			x = source[i];
			while (i < j) {
				while (i < j && source[j] > x) {
					j--;
				}
				if (i < j) {
					source[i] = source[j];
					i++;
				}
				while (i < j && source[i] < x) {
					i++;
				}
				if (i < j) {
					source[j] = source[i];
					j--;
				}
			}
			source[i] = x;
			quickSort(source, low, i - 1);
			quickSort(source, i + 1, high);
		}
	}

	public static void main(String[] args) {
		int[] a = {4,2,1,6,3,6,0,-5,1,1};
		quickSort(a, 0, a.length - 1);
		print(a);
	}