排序算法在程序中会用到很多,这里介绍几种常见的排序方法以及比较
冒泡排序:对一个队列里的数据,挨个进行轮询和交换,每次轮询出一个当前最大或者最小的值放在队尾,然后继续下次轮询,轮询长度-1,就跟冒泡一样,所以称为冒泡排序,运算时间复杂度N平方
选择排序:对一个队列里的数据,选出当前最大或者最小的值,然后将他与队首的数据交换,然后从第二个开始,进行相同的操作,运算时间复杂度N平方,但由于他不像冒泡一样需要不停的交换位置,所以会比冒泡快一些
插入排序:对一个队列里的数据,从第二个开始,与此位置之前的数据进行比较,形成局部有序的队列,循环此操作,直到队尾,运算时间复杂度依然为N平方,但他由于保证了局部的有序性,所以比较的次数会更少一些,相对前两种会更快
希 尔排序:其实就是用步长控制的插入排序,希尔排序通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而让数据项可以大幅度移动, 这样的方式可以使每次移动之后的数据离他们在最终序列中的位置相差不大,保证数据的基本有序,大大提升了排序速度,运算时间复杂度N*logN
快速排序:对一个队列,以他队尾的数据为基准值,先划分成两块数据,一块都大于这个值,一块小于这个值,然后对这两块进行同样的操作,这是最快的排序方法,运算时间复杂度N*logN
下面是代码:
public static void sort(int[] a)
{
long time1,time2;
int c;
time1=System.currentTimeMillis();
// /*冒泡排序*/
// for(int i=a.length-1;i>1;i--)
// {
// for(int j=0;j<i;j++)
// {
//
// if(a[j]<a[j+1])
// {
// c=a[j];
// a[j]=a[j+1];
// a[j+1]=c;
// }
// }
// }
// /*选择排序*/
// int pos=0;
// for(int i=0;i<a.length-2;i++)
// {
// for(int j=i;j<a.length-1;j++)
// {
// if(a[pos]<a[j+1])
// pos=j+1;
// }
// c=a[i];
// a[i]=a[pos];
// a[pos]=c;
// pos=i+1;
// }
// /*插入排序*/
// for(int i=1;i<a.length;i++)
// {
// c=a[i];
// int m=i-1;
// while(m>=0&&a[m]<c)
// {
// a[m+1]=a[m];
// m--;
// }
// a[m+1]=c;
// }
// /*希尔排序*/
// int h=1;
// int m=0;
// while(3*h+1<a.length)
// h=3*h+1;
// while(h>0)
// {
// for(int i=h;i<a.length;i++)
// {
// c=a[i];
// m=i-h;
// while(m>=0&&a[m]<c)
// {
// a[m+h]=a[m];
// m-=h;
// }
// a[m+h]=c;
//
// }
// h=(h-1)/3;
// }
/*快速排序*/
provide(a,0,a.length-1);
time2=System.currentTimeMillis();
System.out.println("time:"+(time2-time1));
}
/*递归调用划分*/
public static void provide(int[] a,int left,int right)
{
try
{
if(right<=left)
return;
else
{
/*设置基准点*/
int prov=a[right];
/*取得划分中断点*/
int par=partitionIt(a,left,right,prov);
/*对划分后的两边再次划分*/
provide(a,left,par-1);
provide(a,par+1,right);
}
}
catch(Exception e)
{
System.out.println("eer:"+left+"."+right);
}
}
/*划分算法*/
public static int partitionIt(int[] a,int left,int right,int prov)
{
/*设置左右端点的指针*/
int leftP=left-1;
int rightP=right;
int c;//用于交换的中间变量
/*当左右指针未相遇时继续操作*/
while(leftP<rightP)
{
/*当左指针的数据小于基准值时跳出*/
while(leftP<a.length-1&&a[++leftP]>prov)
;
/*当右指针的数据大于基准值时跳出*/
while(rightP>leftP&&a[--rightP]<prov)
;
/*左右指针都停下时交换数据*/
c=a[leftP];
a[leftP]=a[rightP];
a[rightP]=c;
}
/*划分结束,将基准点与指针的相遇点交换*/
c=a[rightP];
a[rightP]=a[right];
a[right]=c;
return leftP;
}
http://gophinight.bokee.com/6190469.html
分享到:
相关推荐
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
C# 常用经典算法,选择排序 冒泡排序 快速排序 插入排序 希尔排序
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
本文件是7种常用排序算法的实现(C++),包括冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序。代码详细有注释且有测试用例。
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
C# 排序算法大全参考资料,比较清淅的一个版本。集中介绍了C#中的冒泡算法、选择排序、插入排序、希尔排序等常用算法,并包含示例代码和注意事项等。
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
printf("\t1: 插入排序\n"); printf("\t2: 冒泡法排序\n"); printf("\t3: 快速排序\n"); printf("\t4: 直接选择排序\n"); printf("\t5: 堆排序\n"); printf("\t6: 归并排序\n"); printf("\t7: 希尔排序\n"); ...
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
排序算法汇总(选择排序 ,直接插入排序,冒泡排序,希尔排序,快速排序,堆排序)
七种排序算法(包括直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,归并排序) 还有两道题 1./*设计并实现一个有效的对n个整数重排的算法,使得所有负数位于非负数之前,给出算法的性能...
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
排序算法汇总P: 冒泡排序快速排序直接选择排序插入排序希尔排序 堆排序........
快速排序、选择排序、冒泡排序、希尔排序、插入排序、懒人排序等6种排序算法C实现
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。