这里主要对8种排序算法做个总结,分别是插入排序,选择排序,冒泡排序,希尔排序,归并排序,堆排序,快速排序以及基数排序。
1、 插入排序
比较和交换的时间复杂度为O(n^2),算法自适应,对于数据已基本有序的情况,时间复杂度为O(n),算法稳定,开销很低,适合于数据已基本有序或者数据量小的情况。
public void insertionSort() {// 插入排序
int out, in;
int count1 = 0, count2 = 0;// 复制次数,比较次数
for (out = 1; out < nElems; out++) {
long temp = a[out];
in = out;
boolean flag=in>0&&a[in-1]>=temp;
while(flag){
if(a[in-1]>=temp){
if(in>0){
a[in]=a[in-1];
count1++;
--in;
}
}
count2++;
flag=in>0&&a[in-1]>=temp;
}
a[in] = temp;
}
System.out.println("复制次数为:" + count1 + " 比较次数为:" + count2);
}
2、 选择排序
算法不稳定,O(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自适应的。在大多数情况下都不推荐使用。只有在希望减少交换次数的情况下可以用。
public void selectionSort(){//选择排序
int out, in, min;
for(out=0;out<nElems-1;out++){
min=out;
for(in=out+1;in<nElems;in++){
if(a[in]<a[min]){
min=in;
}
swap(out,min);
}
}
}
3、 冒泡排序
算法稳定,O(1)的额外的空间,比较和交换的时间复杂度都是O(n^2),自适应,对于已基本排序的算法,时间复杂度为O(n)。冒泡算法的许多性质和插入算法相似,但对于系统开销高一点点。
public void bubbleSort() {// 冒泡排序,单项
int out, in;
for (out = nElems - 1; out > 1; out--) {
for (in = 0; in < out; in++) {
if (a[in] > a[in + 1]) {
swap(in, in + 1);
}
}
}
}
分享到:
相关推荐
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
java排序算法使用及场景说明 文档后面有一些别人的链接,多在google上搜索Java排序算法,及维基百科上面也有很全的算法介绍。
java实现的常用的几种基本排序算法,插入、交换、选择、归并
JAVA排序算法总结,对常用的算法进行了总结,可以看看哦!!
Java排序算法实现 Java排序算法实现 Java排序算法实现
关于八种常见的排序算法的总结,里面有可运行的Java代码,方便打印
Java排序算法代码.
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
Java常用8大排序算法,包含每种算法详细介绍,及代码如何实现。
Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全
尚硅谷Java排序算法PPT
Java排序算法 Java排序算法.rar
排序算法总结.doc 排序算法总结.doc 排序算法总结.doc
排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际...
java最常见的八种排序算法
Java各种排序算法代码.rar
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
java产生多个随机数写入文件中,比较四种排序算法的效率
Java排序算法 Java排序算法 Java排序算法