9

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

 4 years ago
source link: https://itimetraveler.github.io/2015/11/03/%E5%90%84%E7%A7%8D%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%92%8C%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E8%A1%A8/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

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

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

对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法：
所以对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]

【参考资料】：


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK