发布日期:2016-01-06 10:27 来源: 标签: 编程语言 开发语言 C++入门教程 C++快速排序
本章我们主要学习C++高级排序算法中的快速排序法,下面我们就做一下具体讲解,希望大家多多支持中国站长网络学院。
高级排序算法:高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使用这个过程(最容易的方法——递归)。
快速排序:
#include <iostream.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);
}


void main()
{
     int data[] = {10,9,8,7,6,5,4};
     QuickSort(data,7);
     for (int i=0;i<7;i++)
         cout<<data[i]<<" ";
     cout<<"\n";
}
这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况
1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。
2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。
第一层递归,循环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)算法,但是通常情况下速度要慢于快速排序(因为要重组堆)。

相关评论

专题信息
    Visual C++是一个功能强大的可视化软件开发工具,是高等院校计算机及相关专业主要核心课程。 本教程对Visual C++ 的应用与开发进行了详细系统的介绍,内容主要包括:Visual C++程序的建立,菜单、工具栏和状态栏的创建,对话框和常用控件,窗口、文档与视图,图形绘制,数据库应用,多媒体技术等。 本教程以案例教学为主,各章节都附有大量的实例,并且操作步骤详细,有利于引导读者更好的消化、理解和实际应用本章节所学的知识内容,希望大家能多多支持中国站长网络学院!