各种排序算法时间复杂度和空间复杂度表

各种排序算法时间复杂度和空间复杂度表:

比较时间复杂度函数的情况如下图：

对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法：

接下来博主抽时间要整理一下各经典算法思想和心得，敬请期待

一、快速排序（Quicksort）

import java.util.Arrays;

public class MySort {
	public static void main(String args[]){
		int[] array = {5,3,9,1,6,4,10,2,8,7};
		System.out.println("Before: " + Arrays.toString(array));
		new MySort().quickSort(array, 0, array.length-1);
		System.out.println("After:  " + Arrays.toString(array));
	}
	
	/**
	 * 快速排序： 递归实现的挖坑填数法
	 * @param array
	 * @param left
	 * @param right
	 */
	private void quickSort(int[] array, int left, int right){
		if(left >= right){
			return;
		}
		
		int i = left;
		int j = right;
		int key = array[left];
		while(i<j){
			while(array[j] >= key && i<j){	//从后向前搜索，比key小的值就挖出来填到i处的坑
				j--;
			}
			array[i] = array[j];
			while(array[i] <= key && i<j){	//从前向后搜索，找出比key大的值填到刚才j处空缺的坑
				i++;
			}
			array[j] = array[i];
		}
		array[i] = key;		//把key回填到数组的空缺处
		System.out.println("Sort:   " + Arrays.toString(array));
		quickSort(array, left, i-1);
		quickSort(array, i+1, right);
	}
}

快速排序的测试代码输出结果如下：

Before: [5, 3, 9, 1, 6, 4, 10, 2, 8, 7]
Sort:   [2, 3, 4, 1, 5, 6, 10, 9, 8, 7]
Sort:   [1, 2, 4, 3, 5, 6, 10, 9, 8, 7]
Sort:   [1, 2, 3, 4, 5, 6, 10, 9, 8, 7]
Sort:   [1, 2, 3, 4, 5, 6, 10, 9, 8, 7]
Sort:   [1, 2, 3, 4, 5, 6, 7, 9, 8, 10]
Sort:   [1, 2, 3, 4, 5, 6, 7, 9, 8, 10]
Sort:   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
After:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

【参考资料】：

• 白话经典算法系列之六 快速排序 快速搞定
• 必须知道的八大种排序算法【java实现】