比较排序与非比较排序的对比

  常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。在冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)。比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。

  非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

 

非比较排序

常见的比较排序主要有以下几种:基数排序、计数排序、桶排序。

基数排序

1、基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

2、算法实现

 package com.allSorts;

 import java.util.ArrayList;
import java.util.List; /**
* Created by Demrystv.
*/
public class Ji1Shu {
public static void main(String[] args) {
int[] a = {23,45,67,88,90,21,42,52,73,61};
System.out.println("排序前:");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
} //基数排序
sort(a); System.out.println("");
System.out.println("排序后:");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
} private static void sort(int[] a){ //找到最大值,看最大值有几位,从而确定要比较几次,个十百千万。。。
int max = 0;
for(int i=0;i<a.length;i++){
if(max<a[i]){
max = a[i];
}
} //找到最大值后,确定要比较几次
int times = 0;
while (max>0){
max = max/10;
times++;
} //建立从0到9十个队列
List<ArrayList> list1 = new ArrayList<>();
for(int i=0;i<10;i++){
ArrayList list2 = new ArrayList();
list1.add(list2);
} //进行times次分配和收集,不断的重复即可。
for(int i=0;i<times;i++){ //分配,按照比较的所在的位的大小将其放入list1 中,类似于数组链表中的链表
for(int j=0;j<a.length;j++){
int x = a[j] % (int)Math.pow(10,i+1) / (int)Math.pow(10,i);
ArrayList list3 = list1.get(x);
list3.add(a[j]);
list1.set(x,list3);
} //收集,然后以此从数组的从左到右,链表的从上到下进行收集,将其重新放进一个新的数组中
int count = 0 ;
for(int j=0;j<10;j++){
while (list1.get(j).size()>0){
ArrayList<Integer> list4 = list1.get(j);
a[count] = list4.get(0);
list4.remove(0);
count++;
}
}
} }
}

3、分析

  基数排序是稳定的排序算法。

  基数排序的时间复杂度为O(k*n),空间复杂度为O(m),k为数组中数值的最大位数,m为桶的的个数。

计数排序

1、基本思想是:对每一个输入的元素arr[i],确定小于 arr[i] 的元素个数,可以直接把 arr[i] 放到它输出数组中的位置上。假设有x个数小于 arr[i],所以 arr[i] 应该放在数组的第(x+1)个位置上。
2、算法实现
 package com.allSorts;

 /**
* Created by Demrystv.
*/
public class Ji4Shu {
public static void main(String[] args) {
int[] a = {23,42,53,64,63,32,13,52,97,94,26};
System.out.println("排序前:");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
} //计数排序
sort(a); System.out.println("");
System.out.println("排序后:");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
} private static void sort(int[] a){ if(a==null || a.length==0){
return;
} int max=0,min=0;
for(int i=0;i<a.length;i++){
max = Math.max(max,a[i]);
min = Math.min(min,a[i]);
} int[] help = new int[max-min+1];
int pos; for(int i=0;i<a.length;i++){
pos = a[i]-min;
help[pos]++;
} int index=0;
for(int i=0;i<help.length;i++){
while (help[i]>0){
a[index] = i + min;
index++;
help[i]--;
}
}
}
}

3、分析

  计数排序是稳定的排序算法。

  计数排序的时间复杂度为O(k+n),空间复杂度为O(m),k为数组中最大数与最小数差值,m为桶的的个数。

桶排序

1、基本思想是把数组 arr 划分为n个大小相同子区间(桶),每个子区间各自排序,最后合并。计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。
2、算法实现
 package com.allSorts;

 import java.util.ArrayList;
import java.util.Collections; /**
* Created by Demrystv.
*/
public class Tong {
public static void main(String[] args) {
int[] a = {32,45,42,51,53,86,95,53,93,55,59};
System.out.println("排序前:");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
} //桶排序
sort(a); System.out.println("");
System.out.println("排序后:");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
} private static void sort(int[] a){ if(a==null || a.length==0){
return;
} int max=0,min=0;
for(int i=0;i<a.length;i++){
max = Math.max(max,a[i]);
min = Math.min(min,a[i]);
} //确定桶数,并且建立一系列的桶
int bucketNum = (max-min)/a.length+1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i=0;i<bucketNum;i++){
bucketArr.add(new ArrayList<Integer>());
} //将每个元素放入桶
for(int i=0;i<a.length;i++){
int num = (a[i]-min)/a.length;
bucketArr.get(num).add(a[i]);
} //对每个桶进行排序
for(int i=0;i<bucketArr.size();i++){
Collections.sort(bucketArr.get(i));
} int index = 0;
for(int i=0;i<bucketArr.size();i++){
while (bucketArr.get(i).size()>0){
a[index++] = bucketArr.get(i).get(0);
bucketArr.get(i).remove(0);
}
}
}
}

3、分析

桶排序可用于最大最小值相差较大的数据情况,。
但桶排序要求数据的分布必须均匀,否则可能导致数据都集中到一个桶中,导致桶排序失效。

最新文章

  1. MobaXterm.9.4|ssh连接工具
  2. dell交换机固件
  3. Extjs 下拉框下拉选项为Object object
  4. WindDbug应用
  5. JAVA基础1
  6. tornado模板的自动编码问题(autoescape )
  7. CSS3弹性伸缩布局(下)——flex布局
  8. C#之可选参数和命名参数
  9. 下一个计划 : .NET/.NET Core应用性能管理系统
  10. 后台程序处理 (一)python asyncio 协程使用
  11. RabbitMQ 通信过程
  12. Android学习笔记之AppWidget
  13. (NO.00003)iOS游戏简单的机器人投射游戏成形记(二十一)
  14. python zip dict函数
  15. Python学习笔记-SQLSERVER的大批量导入以及日常操作(比executemany快3倍)
  16. input子系统 KeyPad-Touch上报数据格式与机制【转】
  17. python模块--zipfile文件压缩
  18. 02-HTML之head标签
  19. UVA.1640.The Counting Problem / BZOJ.1833.[ZJOI2010]数字计数(数位DP)
  20. CloudFlare防护下的破绽:寻找真实IP的几条途径

热门文章

  1. NR / 5G - The Best CQI algorithm
  2. 自定义内建模块 - Python Build Your Own Built-In Module
  3. ELF文件之六——使用链接脚本-2个函数-data-bss-temp
  4. centos6.5下编译安装单实例MySQL5.1
  5. Laravel + Serverless Framework 快速创建 CMS 内容管理系统
  6. ElasticSearch集群-Windows
  7. 【转】Redis内部数据结构详解——ziplist
  8. 学会这一招,小白也能使用数据可视化BI软件创建医院数据实时展示大屏
  9. linux中的链接命令
  10. 刷题85. Maximal Rectangle