quick sort and quick-sort implements and the compare of different sorts - Githubissues

vinthony / vinthony.github.io

all about myself.

8 stars 1 forks source link

quick sort and quick-sort implements and the compare of different sorts #12

Open vinthony opened 9 years ago

vinthony commented 9 years ago

quick sort

选定一个位置的数为分割，如果小于这个数则放在这个数左面，大于这个数放在右边
递归进行此过程
为了保证不会出现worse case ，可以对要排序的数组进行shuffle
shuffle

见生成一个在一定范围内不重复的随机数组

selection

选出一个数组中第K小（大）的数（面试题）
利用quicksort的概念，从最左边开始选分割m，如果m的index是第K大，则返回a[m]
如果小于k，则在0...m区间继续进行这过程，否则在m+1...n进行这一过程
duplicate key
在有大量重复的key时候优化quick sort，采用两个分割来进行调用
排序性能比较

排序方式	inplace	stable？	best	average	worst	remarks
选择排序	√		`½N²`	`½N²`	`½N²`	N 次交换
插入排序	√	√	`N`	`¼N²`	`½N²`	在局部排好序或者N比较小时效率比较高
希尔排序	√		`Nlog（3）N`	？	cN`3/2`	编码较少，小于平方的复杂度
并归排序		√	`½NlgN`	`NlgN`	`NlgN`	稳定的算法，但是需要额外的空间
快速排序	√		`NlgN`	`2NlgN`	`½N²`	实际应用中最快的算法
3-way快排	√		`N`	`2NlgN`	`½N²`	大量重复key的时候的改进快排