今天发布一篇关于我自己研究发现的一种能实现快速排序的算法，速度超快，我暂时命名为量子排序算法吧。
1.原理介绍：
原理其实很简单，就是我们可以把一个乱序数组，看成是本来就已经排好顺序了。那么我们直接拿到手的就是已经排好顺序的数组了。
2.代码：
废话不多说，直接上代码。
import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;
public class TreeListUtil {
public static void main(String[] args) {
//比较冒泡排序，和我的量子排序算法速度
int[] nums = generateRndLargeArr() ;
long begin_t = 0 ;long end_t = 0 ;
begin_t = System.currentTimeMillis() ;
List<Integer> li1 = autoReOrder(nums) ;
end_t = System.currentTimeMillis() ;
ptl("我的量子排序算法，速度为"+ (end_t- begin_t) +"毫秒") ;
begin_t = System.currentTimeMillis() ;
List<Integer> li2 = maoPao(nums) ;
end_t = System.currentTimeMillis() ;
ptl("冒泡排序算法，速度为"+ (end_t- begin_t) +"毫秒") ;
ptl("") ;
}
private static int[] generateRndLargeArr() {
int len = 300000 ;
int[] arr = new int[len] ;
for(int i = 0 ; i <= len -1 ; i ++ ){
arr[i] = (int) (Math.random()*( 10000000-0 +1) + 0);
}
return arr ;
}
private static void ptl( String s) {
System.out.println(s);
}
public static List<Integer> autoReOrder(int[] values) { // 考虑 了可能存在重复值，但是不能覆盖旧的重复值的情况
TreeMap<Integer , List<Integer>> map = new TreeMap<>() ;
for( int i : values ){
List<Integer> li = map.get(i) ;
if(li==null){
li = new ArrayList<>() ;
}
li.add(i) ;
map.put( i , li ) ;
}
List<Integer> res = new ArrayList<>() ;
for(Integer key : map.keySet() ){
List<Integer> li = map.get(key) ;
if(li!=null && li.size() > 0 ){
for(int j : li ){
res.add(j) ;
}
}
}
return res ;
}
public static List<Integer> maoPao(int[] values) {
for(int i = 0 ; i <= values.length -1 ; i ++ ){
for(int j = i ; j <= values.length -1 ; j ++ ){
if( values[i] > values[j] ){
int tmp = values[i] ;
values[i] = values[j] ;
values[j] = tmp ;
}
}
}
List<Integer> li = new ArrayList<>() ;
for( int i : values ){
li.add(i) ;
}
return li ;
}
}
3.结果展示：
这边数据量不大，仅仅是300000个随机数，冒泡算法花费了120多秒才完成排序。而我的量子排序算法才357毫秒就完成了排序，不到1秒钟。可见其速度之快。
4.算法复杂度总结
量子排序的时间复杂度是 2O(n)，属于线性阶的。
冒泡排序的时间复杂度是 O(n^2)+O(n)，也就是平方阶加线性阶。显而易见，量子排序的算法无疑是最省时间的。
量子排序的空间复杂度是 n* O(n) + 2*O(n) , 也就是 (2+n)O(n)
冒泡排序的空间复杂度是 O(n)。显而易见，冒泡排序的优点就是节省系统的内存占用。
(
个人理解：
时间复杂度怎么看，其实你看算法内的for循环，如果是单层for循环，那时间复杂度就是一个O(n)，如果是2个for循环用内嵌的方式，那么就是 O(n^2)
空间复杂度怎么看，你可以查看算法中的这种申请内存的语句： new int[100] ; 一个这种语句就是一个O(n)。如果把这种语句放在for循环内部，就是 n(O(n))
具体怎么看算法公式，还可以参考这篇文档：
https://baijiahao.baidu.com/s?id=1662190834355918541&wfr=spider&for=pc
)
综上所述，当我们计算机内存充足时，大可以采用量子排序的算法大大提升排序的速度，节省时间，也就是用空间换时间。但是当数据特别大的时候，如果内存也不够用，这个时候可能就要考虑分成多份任务去做了，及时释放内存占用。
当我们计算机性能比较一般，内存不够用的话，我们可以采用冒泡排序算法，节省内存开销，但是缺点就是比较费时，尤其是当数据量比较大时，也不知道算到猴年马月。
感觉有用的伙伴点下关注或者赞嘛，谢谢了。有什么不足也欢迎大家指出。非常感谢！