2.1.5 排序
考点:各种排序算法及它们的时间复杂度。
排序算法有很多,包括插入排序算法、冒泡排序算法、堆排序算法、归并排序算法、选择排序算法、计数排序算法、基数排序算法、桶排序算法、快速排序算法等。下面介绍几种常考的排序算法。
1.冒泡排序算法
简单的冒泡排序算法如下。
public void bubbleSort()
{
int out,in;
for(out=nElems-1;out>0;out--)
for(in=0;in<out;in++)
if(a[in]>a[in+1])
swap(in,in+1);
}
上述冒泡排序算法的时间复杂度为O(n2)。
2.选择排序算法
常用的选择排序算法如下。
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);
}
}
上述选择排序算法的时间复杂度为O(n2)。
3.插入排序算法
在插入排序算法中,一组数据在某个时刻是局部有序的,而在冒泡排序和选择排序中是完全有序的。
public void insertionSort()
{
int in,out;
for(out=1;out<nElems;out++)
{
long temp=a[out];
in=out;
while(in>0&&a[in-1]>=temp)
{
a[in]=a[in-1];
--in;
}
a[in]=temp;
}
}
上述插入排序算法的效率比冒泡排序的高一倍,比选择排序算法略高,但其时间复杂度也是O(n2)。如果数据基本有序,几乎需要O(n)的时间。
4.快速排序算法
快速排序算法的根本机制在于划分,划分数据就是把数据分为两组,使所有关键字大于特定值的数据项在一组,使所有关键字小于特定值的数据项在另一组。
public int partitionIt(int left,int right,long pivot)
{
int leftPtr=left-1;
int rightPtr=right+1;
while(true)
{
while(leftPtr<right &&
theArray[++leftPtr]<pivot)
;
while(rightPtr>left &&
theArray[--rightPtr]>pivot)
;
if(leftPtr>=rightPtr)
break;
else
swap(leftPtr,rightPtr);
}
return leftPtr;
}
快速排序算法本质上通过把一个数组划分为两个子数组,并递归地调用自身为每一个子数组进行快速排序。
综上所述,常用排序算法的时间复杂度对比如表2.1所示。
表2.1 常用排序算法的时间复杂度对比
版权声明:51Testing软件测试网获得人民邮电出版社和作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。