分类： C/C++
2009-08-06 13:33:34
 |
|
内部排序算法
一、插入排序
1：直接插入排序
(1)基本思想
待排序的记录放在数组R[0…n-1]中
排序过程中某一时刻，R被划分成两个子区间R[0…i-1] (有序和)R[i…n-1](无序)
直接插入的基本操作是将当前无序区的一个记录R[i]插入到有序区R[0…i-1]中适当的位置
这种方法通常称为增量法，因为它每次使有序区增加1个记录
(2)代码
void insertsort(int R[],int n)//对R[0…n-1]按递增顺序进行直接插入排序
{
int i,j;
int temp;
for(i=1;i
{
temp=R[i];
j=i-1;//j指向有序区最后一个元素
while(j>=0&&temp
{
R[j+1]=R[j];//将值大于R[i]的记录后移
j--;
}
R[j+1]=temp;//在j+1处插入R[i]
}
}
(3)性能分析
直接插入排序有两重循环：
a：对于n个记录的数组，外循环表示要进行n-1趟排序
b：每趟循环中，当R[i]>= R[i-1]时，无须进入内循环，每趟比较一次，n-1趟比较n-1次；
当R[i]
(4)小结(直接插入排序性能)
最好时间O(n)
平均时间O(n2)
最坏时间O(n2)
稳定性--稳定
2：希尔排序
(1)基本思想
希尔排序实际上是一种分组插入的方法
先取小于n的整数d1作为第一个增量，把数组分成d1个组，所有距离为d1的倍数的记录放在一个组内，在各组内进行直接插入排序；
然后，取第二个增量d2(
一直到所取的增量dt =1，即所有记录放在同一组进行直接插入排序为止
(2)代码
void shellsort(int R[ ],int n)//对R[0…n-1]按递增顺序进行希尔排序
{
int i,j,d;
int temp;
d=n/2;//d的初值取n/2
while(d>0)
{
for(i=d;i
{
j=i-d;
while(j>=0&&R[j+d]
{
temp=R[j];//R[j]与R[j+d]交换
R[j]=R[j+d];
R[j+d]=temp;
j=j-d;
}
}
d=d/2;//递减增量
}
}
(3)为什么希尔排序优于直接插入排序?
当增量d=1时，希尔排序和直接插入排序基本一致！
原因：a:当n值较小时，直接插入排序的最好时间复杂度O(n)和最坏复杂度O(n2)差别不大
b:当表基本有序时，直接插入所需的比较和移动次数较少
(4)小结(希尔排序性能)
平均时间O(n1.25)
稳定性--不稳定
二、交换排序
1：冒泡排序
(1)基本思想
整个算法是从最下面的记录开始，通过无序区相邻记录的比较和交换，使值最小的记录如气泡一般逐渐往上“漂浮”直至“水面”，经过一趟冒泡排序后，值最小的记录到达最上端；
然后，再在剩下的记录中找值次小的记录，并把它交换到第2个位置上；
依次类推，一直到所有记录都有序为止
(2)代码
void bubblesort(int R[],int n)
{
int i,j;
int temp;
for(i=0;i
{
for(j=n-1;j>i;j--)//第一趟j从1至n-1，最后一趟j取n-1
if(R[j]
{
temp=R[j];//交换R[j]与R[j-1]，将较小值的记录前移
R[j]=R[j-1];
R[j-1]=temp;
}//if交换
}//外层的for循环
}
(3)改进冒泡排序的基本思想和代码
上面的冒泡排序中，在第i(i
所以当某趟已无交换时，说明已经排好序了，算法可以结束
void bubblesort(int R[],int n)
{
int i,j, exchange;//添加了exchange
int temp;
for(i=0;i
{
exchange=0; //添加了exchange
for(j=n-1;j>i;j--)//第一趟j从1至n-1，最后一趟j取n-1
if(R[j]
{
temp=R[j];//交换R[j]与R[j-1]，将较小值的记录前移
R[j]=R[j-1];
R[j-1]=temp;
exchange=1; //添加了exchange
}//if交换
if(exchange=0)return; //添加了exchange
}//外层的for循环
}
(4)性能分析(改进的冒泡排序算法)
若数组的初始状态是正序的，则一趟即可完成排序，时间复杂度为O(n)；
若数组的初始状态是反序的，则进行n-1趟排序，每次进行n-i-1次比较，时间复杂度O(n2)
(5)小结(改进的冒泡排序性能)
最好时间O(n)
平均时间O(n2)
最坏时间O(n2)
稳定性--稳定
2：快速排序
(1)基本思想
在待排序的数组的n个元素中取一个元素(一般取第一个)，将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，这样是一趟快速排序；
然后对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；
总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子表长度为1！
(2)代码
void quicksort(int R[],int low,int high)
{
int temp;//枢轴元素
if(low
{
temp=R[low];//以数组的第一个元素作为基准进行划分
int i=low,j=high;
while(i
{
while(i
if(i
while(i
if(i
}
R[i]=temp;//枢轴元素移到合适的位置
quicksort(R,low,i-1);
quicksort(R,i+1,high);
}//结束if
}
(3)小结(快速排序性能)
最好时间O(nlogn)
平均时间O(nlogn)
最坏时间O(n2)
解释：在所有同数量级(O(nlogn))的排序方法中，快速排序被认为是平均性能最好的一种；
但是，若初始记录序列按关键字有序或基本有序时，快速排序则蜕化为冒泡排序，此时，算法的时间复杂度为O(n2)
稳定性--不稳定
三、选择排序
1：直接选择排序
(1)基本思想(详见(3)与直接插入排序的对比)
(2)代码
void selectsort(int R[],int n)
{
int i,j,k;
int temp;
for(i=0;i
{
k=i;
for(j=i;j
if(R[j]
k=j;//用k记下目前找到的最小值的位置
if(k!=i)
{
temp=R[i];//交换R[i]和R[k]
R[i]=R[k];
R[k]=temp;
}//结束if
}//结束for即n-1趟
}
(3)直接插入排序与直接选择排序的对比!
直接插入排序：把无序区第一个元素和有序区的所有元素对比，将这个无序区的第一个元素插入到有序区的适当位置，构成新的有序区如此循环
直接选择排序：找出无序区中最小的元素放在无序区的第一个位置，这样，有序区和无序区的调整后第一个位置的元素就构成了新的有序区，如此循环
(4) 小结(直接选择排序性能)
最好时间O(n2)
平均时间O(n2)
最坏时间O(n2)
稳定性--不稳定
2：堆排序
什么是堆?本文讨论的是大根堆，即概念如下：Ri>=R2i且Ri >=R2i+1，小根堆与之相反
(1)基本思想
首先将数组R[n]中元素按从左向右顺序排列，构成一个完全二叉树，此时，任意节点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R[i/2]；
假设完全二叉树某个节点i对它的左、右子树已经是堆，接下来要将R[2i]和R[2i+1]中的较大者与R[i]交换，但是，这有可能破坏下一级的堆，于是继续采用上述的方法构建下一级的堆，直至完全二叉树节点i构成堆为止；
对于任意一棵二叉树，从i=n/2到1，反复利用上述思想建堆，大者“上浮”，小者“下沉”!
(2)代码
调整堆的算法sift()如下：
void sift(int R[],int low,int high)//假设完全二叉树节点i对它的左、右孩子已经是堆
{
int i=low,j=2*i;//R[j]是R[i]的左孩子
int temp=R[i];
while(j<=high)
{
if(j
if(temp
{
R[i]=R[j];//将R[j]调整到双亲节点位置上
i=j;//修改i和j的值，以便向下筛选
j=2*i;
}
else break;//跳出while循环
}//while循环
R[i]=temp;//被筛选节点的值最终放入的位置
}
堆排序的算法如下：
void heapsort(int R[],int n)//按照递增顺序排序
{
int i;
int temp;
for(i=n/2;i>=0;i--)//循环建立初始堆
sift(R,i,n);
for(i=n-1;i>=1;i--)//进行n-1趟循环，完成堆排序
{
temp=R[0];//将当前循环内第一个元素和最后一个元素交换
R[0]=R[i];
R[i]=temp;
sift(R,0,i-1);//筛选出R[0]节点，得到i-1个节点的堆
}//结束n-1趟循环
}
(4)小结(堆排序性能)
最好时间O(nlogn)
平均时间O(nlogn)
最坏时间O(nlogn)
稳定性--不稳定
四、其他排序算法(简略)
1：归并排序：稳定
2：基数排序：稳定
五、内部排序算法总结
1：
内部排序各种算法的性能比较(表)
|
|
排序方法 |
最好时间 |
平均时间 |
最坏时间 |
稳定性 |
|
插入排序 |
直接插入排序 |
O(n) |
O(n2) |
O(n2) |
稳定 |
|
希尔排序 |
|
O(n1.25) |
|
不稳定 | |
|
交换排序 |
冒泡排序 |
O(n) |
O(n2) |
O(n2) |
稳定 |
|
快速排序 |
O(nlogn) |
O(nlogn) |
O(n2) |
不稳定 | |
|
选择排序 |
直接选择排序 |
O(n2) |
O(n2) |
O(n2) |
不稳定 |
|
堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
不稳定 | |
|
其他排序 |
归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
稳定 |
|
基数排序 |
|
|
|
稳定 |
2：内部排序各种算法的选择
(1)当n较小时：可采用直接插入排序和直接选择排序
当记录规模小时，可选择直接插入排序；
当记录规模大时，可选择直接选择排序，因为直接插入排序所需的记录移动操作比直接选择排序多
(2)当记录基本有序时：可采用直接插入排序和冒泡排序
(3)当n较大时：可采用时间复杂度为O(nlogn)的快速排序、堆排序和归并排序
