首页 > 软件开发 > c语言 > 正文
6.3.2 高级排序
2015-11-23 13:29:18     我来说两句      
收藏    我要投稿

高级排序算法中将只介绍这一种,同时也是目前所知道的最快的。它的工作看起来仍然象一个二叉树。首先选择一个中间值middle程序中使用数组中间值,然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使 用这个过程(最容易的方法——递归)。

世界杯外围投注官网import <Foundation/Foundation.h>

void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中间值
do{
while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
 i++;
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
     j--;
    if(i<=j)//找到了一对值
{
     //交换
    iTemp = pData[i];
    pData[i] = pData[j];
    pData[j] = iTemp;
    i++;
    j--;
 }
}while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)
 //当左边部分有值(left<j),递归左半边
 if(left<j)
   run(pData,left,j);
 //当右边部分有值(right>i),递归右半边
 if(right>i)
    run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
 run(pData,0,Count-1);
}
测试算法:
int main (int argc, const char * argv[]) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
 int arr[] == {10,9,8,7,6,5,4};
 QuickSort( ( (arr, 7);
 for(int i = 0; i < 7; i++)
 {
  NSLog(@"%i",arr[i]);
 }
    [pool drain];
    return 0;
}

这里没有给出行为的分析,因为这个很简单,直接来分析算法:首先考虑最理想的情况:

数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。

每次我们选择的值刚好是中间值,这样,数组才可以被等分。

第一层递归,循环n次,第二层循环2*(n/2)......

所以共有:

n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n

所以算法复杂度为:

O(log2(n)*n)

其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变成交换法(由于使用了递归,情况更糟)。但是认为这种情况发生的几率有多大?完全不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。如果担心这个问题,可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢 于快速排序,因为要重组堆。

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:6.3.1 简单排序
下一篇:6.3.3 其它排序
相关文章
图文推荐
排行
热门
文章
下载
读书

关于我们 | 联系我们 | 服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑--致力于做实用的IT技术学习网站

世界杯外围投注官网