乱序算法
Ⅰ 分布式系统中的RPC请求经常出现乱序的情况. 写一个算法来将一个乱序的序列保序输出，求C语言大神
基本思想是将每一行存入一个链表结点，data表示起始数据，len表示每行元素个数。
structListNode
{
intdata;
intlen;
ListNode*next;
};
voidInsertNode(ListNode*&pHead,ListNode*pNode)
{
ListNode*pTmp=NULL;
if(pNode==NULL)
{
printf("pNodeisNULL! ");
return;
}
if(pHead==NULL)
{
pHead=pNode;
}
else
{
for(pTmp=pHead;pTmp->next!=NULL;pTmp=pTmp->next)
;
pTmp->next=pNode;
}
}
voidSortAndPrint(inta[],intn)
{
ListNode*pHead=NULL;
ListNode*temp=NULL;
inti=0;
intdata=0;
intdataLen=0;
while(i<n)
{
intj=0;
intlen=0;
intmoreNum=a[i];
intlessNum=a[i];
//查找小于一个数的连续数出现次数
while(j<i)
{
if(a[j]==lessNum-1)
{
j=0;
lessNum--;
continue;
}
j++;
}
//只有小于一个数的所有数均出现时才存数据
if(lessNum==1)
{
j=0;
while(j<i)
{
if(a[j]==moreNum+1)
{
len++;
moreNum++;
j=0;
continue;
}
j++;
}
ListNode*p=(ListNode*)malloc(sizeof(ListNode));
memset(p,0,sizeof(ListNode));
p->data=a[i];
p->len=len;
p->next=NULL;
InsertNode(pHead,p);
}
i++;
}
//按顺序打印序列
for(temp=pHead;temp!=NULL;temp=temp->next)
{
dataLen=temp->len;
data=temp->data;
while(dataLen)
{
printf("%d,",data++);
dataLen--;
}
printf("%d ",data);
}
//释放资源
ListNode*prev=NULL;
ListNode*curr=pHead;
while(curr!=NULL)
{
prev=curr;
curr=curr->next;
if(prev!=NULL)
{
free(prev);
prev=NULL;
}
}
}
intmain(void)
{
inta[]={1,2,5,8,10,4,3,6,9,7};
SortAndPrint(a,10);
return0;
}
Ⅱ C++中排序的算法分析(文字分析)
排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。
而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。
对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。
我将按照算法的复杂度，从简单到难来分析算法。
第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N*N)（因为没有使用word,所以无法打出上标和下标）。
第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。
第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。
第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。
现在，让我们开始吧：
一、简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。
1.冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)
第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。
写成公式就是1/2*(n-1)*n。
现在注意，我们给出O方法的定义：
若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。（呵呵，不要说没
学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因，我们通常都是通过循环次数来对比算法。
2.交换法：
交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData[i])
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,9,10,8->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)
第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。
3.选择法：
现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择最小的与第二个交换，这样往复下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i<Count-1;i++)
{
iTemp = pData[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)
第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)
第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次)
循环次数：6次
交换次数：2次
其他：
第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)
第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)
第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。
我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n
所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。
4.插入法：
插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
iTemp = pData[i];
iPos = i-1;
while((iPos>=0) && (iTemp<pData[iPos]))
{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7(交换1次)(循环1次)
第二轮：9,10,8,7->8,9,10,7(交换1次)(循环2次)
第一轮：8,9,10,7->7,8,9,10(交换1次)(循环3次)
循环次数：6次
交换次数：3次
其他：
第一轮：8,10,7,9->8,10,7,9(交换0次)(循环1次)
第二轮：8,10,7,9->7,8,10,9(交换1次)(循环2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)(循环1次)
循环次数：4次
交换次数：2次
上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，
因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<=
1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单
排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似
选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’
而这里显然多了一些，所以我们浪费了时间。
最终，我个人认为，在简单排序算法中，选择法是最好的。
二、高级排序算法：
高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后
把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使
用这个过程（最容易的方法——递归）。
1.快速排序：
#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)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。
三、其他排序
1.双向冒泡：
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。
代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。
写这段代码的作者认为这样可以在冒泡的基础上减少一些交换（我不这么认为，也许我错了）。
反正我认为这是一段有趣的代码，值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do
{
//正向的部分
for(int i=right;i>=left;i--)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//反向的部分
for(i=left;i<right+1;i++)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
2.SHELL排序
这个排序非常复杂，看了程序就知道了。
首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。
工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序
以次类推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int iTemp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step[i];
s = -k;
for(int j=k;j<Count;j++)
{
iTemp = pData[j];
w = j-k;//求上step个元素的下标
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp<pData[w]) && (w>=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
呵呵，程序看起来有些头疼。不过也不是很难，把s==0的块去掉就轻松多了，这里是避免使用0
步长造成程序异常而写的代码。这个代码我认为很值得一看。
这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因
避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并
“超出本书讨论范围”的原因（我也不知道过程），我们只有结果了。
四、基于模板的通用排序：
这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index,char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char* GetData(){ return m_strDatamember; };
//这里重载了操作符：
CMyData& operator =(CMyData &SrcData);
bool operator <(CMyData& data );
bool operator >(CMyData& data );
private:
char* m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index,char* strData):
m_iIndex(Index),
m_iDataSize(0),
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,SrcData.GetData());
return *this;
}
bool CMyData::operator <(CMyData& data )
{
return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include "MyData.h"
template <class T>
void run(T* pData,int left,int right)
{
int i,j;
T 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);
}
template <class T>
void QuickSort(T* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
CMyData data[] = {
CMyData(8,"xulion"),
CMyData(7,"sanzoo"),
CMyData(6,"wangjun"),
CMyData(5,"VCKBASE"),
CMyData(4,"jacky2000"),
CMyData(3,"cwally"),
CMyData(2,"VCUSER"),
CMyData(1,"isdong")
};
QuickSort(data,8);
for (int i=0;i<8;i++)
cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n";
cout<<"\n";
}
Ⅲ 把一个完全乱序的数列，用什么排序算法能最快的排列出来
一般情况，也就是这些数是随机的，那么可以是快速排序，堆排序，归并排序，他们的算法复杂度都是n*log2n(2是底数)
Ⅳ 如何实现hash排序算法
不知道你在说什么鸟语？ hash的意思就是乱序，排序就是有序，你的问题等价于乱序有序算法。乱序怎么还能有序呢？
自己去网络一下hash排序这个词，看看别人都是怎么描述的吧，根本不是你这个意思。
Ⅳ 乱序执行的区别
乱序执行技术与顺序执行技术
未来主流的计算市场（台式机、服务器和笔记本电脑）需要的是有限多核架构，更加强调核的单线程性能，而很多核架构（数十甚至上百个内核）则将应用于流计算、HPC和SoC等特殊计算环境。这也将成为未来英特尔处理器的一个分水岭，于是就有了所谓“大核”和“小核”处理器之分。前者以目前的酷睿架构为发展基准，追求更好的单线程性能; 后者则以凌动（Atom）内核为基础，在设计上强调更高的并行度和更低的功耗。
在指令执行方面，“大核”采用的是乱序执行（out-of-order execution）模式，而“小核”则采用顺序执行（In-order execution）模式。与顺序执行相对应的乱序执行，是指CPU允许将多条指令不按程序规定的顺序分开发送给各相应电路单元处理的技术。
对比
与顺序执行技术相比，乱序执行能够更有效地提高IPC，即提高每个时钟频率能够执行的指令数量。一般来说在同样一个主频周期当中，无序核执行指令数量要比有序核执行的数量更多，因而乱序执行架构的处理器单核的计算能力比较强。但乱序执行模式的处理器在电路设计上比较复杂，核的功耗也比较高，在手机和某些嵌入式应用需要绝对低功耗的场合较难达到其设计要求，因此凌动处理器很自然地就采用了顺序执行模式。
未来，很多核处理器和有限多核处理器将并行发展，以共同满足日益分化和复杂的计算环境的需求。而评价一款处理器好坏的标准也会更加复杂，可能既不是通过主频甚至也不是IPC，而要根据其应用特性来具体判断。
乱序执行技术与龙芯2F芯片
应用
龙芯处理器在工业控制、PC、笔记本、军工方面已经有非常成熟的应用，其实在某种意义上说，国产芯片已经进入了主流市场。据王成江先生透露，有很多政府以及军队都在长期使用龙芯平台。
对比
曙光千兆防火墙采用的是龙芯2F芯片，它是64位的通用RISC处理器，采用90nm的CMOS工艺制造，完全兼容MIPS 64标准。龙芯2F是基于龙芯2E处理器的改进版本，于2007年研制成功。龙芯2F集成了高性能龙芯2号CPU核，四发射动态超标量结构，9-10 级超流水线，支持寄存器重命名、动态调度、转移预测等乱序执行技术;龙芯2F在龙芯2E的基础上提高了I/O性能和内存访问带宽，集成内存控制器，提升了数据吞吐的速度，为网络安全产品提供了比较好的平台。
乱序执行技术与英特尔E8400处理器
简介
45纳米英特尔酷睿2双核处理器E8400可为嵌入式应用提供长达7年的生命周期支持。这款处理器同时还支持英特尔可信执行技术（Intel Trusted Execution Technology），以帮助客户部署安全的嵌入式解决方案。
增强的多媒体性能
该款45纳米处理器中引入了超级乱序执行引擎，能够增强专为图形和多媒体处理优化的英特尔SIMD流指令扩展（SSE）算法。超级乱序执行引擎能够降低延迟，并在加快现有SSE指令运行速度的同时，显着提升最新SSE4指令集的表现。开发人员可充分利用SSE4多媒体指令集，提升交互式客户端或数字签名等终端嵌入式应用内在的视频编辑和编码功能。
英特尔可信执行技术
英特尔可信执行技术是英特尔酷睿2双核处理器E8400中的一项硬件延展技术，它将硬件数据安全性引入了嵌入式市场，使得双核处理器成为了防务、政府、中型网络安全设备和零售应用的理想选择。这项安全技术旨在保护虚拟化计算环境中的数据免遭软件攻击、病毒入侵及其它类型威胁。[6]
编辑本段
乱序执行技术与Intel的Nehalem架构芯片
建立
Nehalem还是基本建立在酷睿微架构（Core Microarchitecture）的骨架上，外加增添了SMT、3层Cache、TLB和分支预测的等级化、IMC、QPI和支持DDR3、新增加SSE4.2指令等技术。比起从Pentium 4的NetBurst架构到酷睿微架构的较大变化来说，从酷睿微架到Nehalem架构的基本核心部分的变化则要小一些，因为Nehalem还是4指令宽度的解码/重命名/撤销。
原因
Nehalem的乱序引擎显着的扩大了，除了性能原因，还有就是为了提供SMT，因为SMT需要资源共享。
和酷睿 2一样，Nehalem的寄存器重命名表（register alias table，RAT）指明每一个结构寄存器（architectural register）要么进入重排序缓冲（Re-Order Buffer，ROB），要么是进入撤销寄存器文件（Retirement Register File，RRF，或翻译为引退寄存器文件），并且保持有绝大多数最近的推测值状态（speculative state）。而RRF则保持有绝大多数最近的非推测状态（non-speculative state）。RAT可以每周期重命名4个微操作，给每一个微操作在ROB中一个目的地寄存器（destination register）。被重命名的指令就读取它们的源操作数并被发送到通用架构的保留站（unified Reservation Station，RS，可以被各种指令类型使用）。
Nehalem的ROB（重排序缓冲）从96项增加到128项，RS（保留站）从32项增加到36项，它们都由两个线程所共享，但是使用不同的策略。ROB是静态分配给2个线程，使得2个线程在指令流里都可以预测得一样远。而RS则是竞争共享，基于各线程的需求。这是因为许多时候一个线程可能会中止，从内存等待操作数，而使用到很少的RS项。这样就不如让另一个更活跃的线程尽可能多地使用RS项。在RS中的指令当其所有操作数都准备好时，就被分配到执行单元去。
Nehalem的执行单元与酷睿 2相比，基本没有大的改变，而且并不受SMT的影响，除了使用率更高之外。
编辑本段
乱序执行技术与威盛凌珑(VIA Nano)处理器
简介
威盛凌珑（VIA Nano）处理器是威盛 x86 平台系列第一款 64 位的超标量乱序执行处理器，旨在激活传统台式和笔记本 PC 市场，为广为需求计算技术、娱乐和网络连接应用提供了真正优质性能。
威盛 C7系列处理器采用市场领先的节能科技，威盛凌珑（VIA Nano）处理器系列在同一功耗范围，把性能提高到原来的四倍，从而进一步提升了其每瓦性能值的领导地位。而与C7系列处理器相同的针脚兼容保证了OEM 和主板商能更平顺地实现二者的转换，另外，也让现有系统和主板升级更易行。
威盛凌珑（VIA Nano） 处理器系列
处理器名称
型号
主频
威盛 V4 前端总线
封装
处理器制程
闲置功耗
VIA Nano
L2100
1.8GHz
800MHz
NanoBGA2
65nm
500mW
VIA Nano
L2200
1.6GHz
800MHz
NanoBGA2
65nm
100mW
VIA Nano
U2300
1.3+GHz
800MHz
NanoBGA2
65nm
100mW
VIA Nano
U2500
1.2GHz
800MHz
NanoBGA2
65nm
100mW
VIA Nano
U2400
1.0GHz
800MHz
NanoBGA2
65nm
100mW
关键架构性能
尺寸
威盛凌珑（VIA Nano）处理器采用富士通先进的65纳米处理器技术，实现了高性能和低功耗完美的融合。它进一步巩固了威盛在处理器小型化的领导地位，通过超密集设计，实现了x86平台新一代更小型化设计和应用。
封装尺寸：威盛凌珑（VIA Nano）BGA2 封装（21mm x 21mm）
核心尺寸：7.650mm x 8.275mm （63.3平方毫米）
64 位的超标量乱序执行的微体系结构
威盛凌珑（VIA Nano）处理器支持完整 64 位指令集，具备宏融合 （Macro-Fusion），微融合 （micro-fusion）功能，和精密复杂的分支预测。进一步降低了处理器功耗，提升了其效能。
高性能计算和媒体处理
威盛凌珑（VIA Nano）处理器支持高速、低功耗威盛V4 前端总线，最低为800 MHz，支持新的SSE指令、2个64KB L1 高速缓存和1MB独立L2 高速缓存，具有 16路信道连接性能，实现了多媒体性能的一大飞跃。
特别值得一提的是，威盛凌珑（VIA Nano）处理器在高性能浮点运算方面有了非常显着的提升，使用了全新的浮点加法运算法则，大大降低了 x86处理器中的浮点延迟时间（the lowest floating-point add latency），同样，浮点乘法器也拥有了最低的浮点延迟时间。
换句话说，这意味着威盛凌珑（VIA Nano）处理器提供了出色的流畅播放蓝光盘和其它高清视频格式的性能，它能解码的媒体流速度可以达到40Mbps ，此外它独有的双时钟浮点单元（FPU）和 128 位的数据通路，提供了绝佳的游戏体验，提供了极顺畅的 3D 图片表现
下图表明了威盛凌珑（VIA Nano）处理器在计算方面优于广受欢迎的 C7 处理器之处：
高级功耗和热量管理
强劲的动态电源管理，包括支持新型“C6”电源状态，PowerSaver科技，全新的电路设计和机制来管理芯片核心温度，降低功耗提升了热量管理水平。
通过处理器中的以上创新科技，威盛凌珑（VIA Nano）处理器在拥有超标量结构，实现显着的性能提升的同时，功耗却能维持和之前的威盛 C7 系列 处理器一样的范围。
威盛 1.0 GHz 的凌珑（VIA Nano） ULV 处理器的首样产品最大的设计功耗（TDP）只有 5 瓦（空闲运行功耗只有100 毫瓦），而 1.8GHz 的威盛凌珑（VIA Nano）处理器的功耗也只有 25.5 瓦（空闲运行功耗 500 毫瓦）。
威盛凌珑（VIA Nano） 处理器计算性能虽增加，功耗仍维持不变，这进一步提升了每瓦性能值， 更始其成为业内每瓦性能值最佳的产品。
2007 上测试的性能总分
1.6GHz Celeron-M 的TDP（最大热功耗） = 31瓦; 1.6GHz 威盛Nano 的TDP = 17 瓦
操作系统 = Windows Vista 企业版
可升级威盛 C7处理器：威盛凌珑（VIA Nano）处理器与威盛 C7处理器家族产品针脚兼容，使 OEM 厂商和主板厂商能平顺的进行新架构的产品交替，能让他们仅需透过单一主板或系统设计，能扩展延伸到不同的市场领域中。
绿色科技：此外还完全符合 RoHS 标准和 WEEE 规则，产品无卤素、无铅，对保护环境和可持续计算科技大有裨益。
增强的威盛 PadLock安全引擎
威盛凌珑（VIA Nano）处理器承继了威盛处理器家族内核硬件加密加速器和安全特性，包括双随机数据生成器（RNG）、一个AES加密引擎、NX Bit 和一个处理 SHA-1/SHA-256 加密计算的安全混编引擎。
AMD Phenom Intel Core 2 Intel Atom VIA C7 VIA Nano
安全混编 No No No 完全 SHA-1 & SHA-256 完全 SHA-1 & SHA-256
缓冲区溢出 NX Bit NX Bit NX Bit NX Bit NX Bit
内核编密码（On-Die Encryption） No No No 完全 AES 编/译 acceleration RSA 加速 CBC, CFB-M, AC, CTR modes 25Gb/s 峰值 完全 AES 编/译 acceleration RSA 加速CBC, CFB-M, AC, CTR modes 25Gb/s 峰值
随机数字生成器（Random Number Generation） (RNG) No No No 2 个增强的硬件RNG ，Feeds输出至SHA 引起的速度为 12Mb/s 2 个增强的硬件RNG ，Feeds输出至SHA 引起的速度为 12Mb/s [7]
编辑本段
巴塞罗那新特性解析：堆栈操作与乱序执行
起源
Intel最早的Pentium M处理器引入了一项名为“dedicated stack manager”（专注堆栈管理器）的新特性，正如其名字所暗示的一样，专注堆栈管理器专门处理所有的X86堆栈操作（例如push, pop, call, return等）。它将这些伐数据集中处理而无需其他执行单元参与，这尤其简化了CPU整数执行单元的工作，加快了整数执行单元的处理速度。
技术
AMD在Barcelona中也引入了类似的技术，AMD称之为Sideband Stack Optimizer（边带堆栈优化器）。有了边带堆栈优化器，处理器中的伐指令不再需要经过3路编码，也不再由整数执行单元处理，这加快了堆栈的处理速度，也同时加快了整数执行单元的处理速度。
在Intel Core微构架中一个重要改进是OOOE乱序执行：当装载指令队列发生等待时，处理器可以将队列后方处于等待的指令优先装载并执行，而不是一直等待到堵塞结束。平均而言，约30%的指令会发生一定时间的堵塞，这一乱序执行模式的引入，使新构架CPU性能有了明显的提高。AMD的K8构架并不支持OOOE乱序执行指令，所以即使K8构架有优秀的内置内存控制器，也依然被对手的Core构架击败。正视这一技术上的落后，AMD在K8L构架的首款芯片Barcelona上及时改进为OOOE技术，这一改进必将为K8L构架的性能带来极大的提高。
Barcelona将可以乱序执行指令，同样也可以在前一指令尚未处理完成时，装载并用空载单元处理下一指令，即使这两条指令需要读取不同的内存地址。Barcelona拥有3个地址生成单元，可以完成3个寄存指令每周期，而Core构架每周期只能执行1次-K8L构架的寄存速度要比Core构架强大3倍。
K8L构架中加入了新的SSE4指令扩展：SSEEXTRQ/INSERTQ指令和MOVNTSD/MOVNTSS指令。前者可以将多条指令合并为一条指令执行，后者用来计算流量寄存指令。Intel也会将在稍候发布的Penryn处理器中加入。
Ⅵ 序号为1至n的n个人,分序号为1至n的n个物品,序号不重合的概率,的算法
回答：
这个问题是一个经典问题,即“乱序问题”.
n个人分n个物品,不管序号重不重,共有n!种分法；
序号不重的分法共有d(n) = n!∑{i=0,n}[(-1)!/i!].
故序号不重的概率P(n)是
P(n) = d(n)/n!= ∑{i=0,n}[(-1)!/i!].
Ⅶ 排序算法的复杂度
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。 这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： #include<iostream>usingnamespacestd;voidBubbleSort(int*pData,intCount){intiTemp;for(inti=0;i<Count;i++){for(intj=Count-1;j>i;j--){if(pData[j]<pData[j-1]){iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp;}}}}voidmain(){intdata[7]={10,9,8,7,6,5,4};BubbleSort(data,7）;for(inti=0;i<7;i++){cout<<data[i]<<;}cout<<endl;system(PAUSE);}倒序（最糟情况)
第一轮：10，9，8，7->10，9，7，8->10，7，9，8->7，10，9，8（交换3次)
第二轮：7，10，9，8->7，10，8，9->7，8，10，9（交换2次)
第一轮：7，8，10，9->7，8，9，10（交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8，10，7，9->8，10，7，9->8，7，10，9->7，8，10，9（交换2次)
第二轮：7，8，10，9->7，8，9，10->7，8，10，9（交换1次)
（这是原撰写人的--7，8，10，9->7，8，10，9->7，8，10，9（交换0次)，第二轮应该是这样的）
第三轮：7，8，9，10->7，8，9，10（交换1次)
循环次数：6次
交换次数：3次
上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。
写成公式就是1/2*(n-1）*n。
现在注意，我们给出O方法的定义：
若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n)，则f(n) = O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看1/2*(n-1）*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1）*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的
有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），
复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的
原因，我们通常都是通过循环次数来对比算法。 交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。 #include<iostream.h>voidExchangeSort(int*pData，intCount){intiTemp;for(inti=0;i<Count-1;i++){//共（count-1）轮，每轮得到一个最小值for(intj=i+1;j<Count;j++){//每次从剩下的数字中寻找最小值，于当前最小值相比，如果小则交换if(pData[j]<pData[i]){iTemp=pData[i];pData[i]=pData[j];pData[j]=iTemp;}}}}voidmain(){intdata[]={10,9,8,7,6,5,4};ExchangeSort(data,sizeof(data)/sizeof(int));for(inti=0;i<sizeof(data)/sizeof(int);i++){cout<<data[i]<<;}cout<<endl;system(PAUSE);}第一轮： 9，10，8，7->8，10，9，7->7，10，9，8（交换3次)
第二轮：7，10，9，8->7，9，10，8->7，8，10，9（交换2次)
第一轮：7，8，10，9->7，8，9，10（交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8，10，7，9->8，10，7，9->7，10，8，9->7，10，8，9（交换1次)
第二轮：7，10，8，9->7，8，10，9->7，8，10，9（交换1次)
第一轮：7，8，10，9->7，8，9，10（交换1次)
循环次数：6次
交换次数：3次
从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样
也是1/2*(n-1）*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以
只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。 现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）
这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从剩下的部分中
选择最小的与第二个交换，这样往复下去。 #include<iostream.h>voidSelectSort(int*pData，intCount){intiTemp;intiPos;for(inti=0;i<Count-1;i++){iTemp=pData[i];iPos=i;for(intj=i+1;j<Count;j++){if(pData[j]<iTemp){iTemp=pData[j];iPos=j;}}pData[iPos]=pData[i];pData[i]=iTemp;}}voidmain(){intdata[]={10，9，8，7，6，5，4};SelectSort(data，7）;for(inti=0;i<7;i++)cout<<data[i]<<;cout<<
;}倒序（最糟情况)
第一轮：10，9，8，7->(iTemp=9）10，9，8，7->(iTemp=8）10，9，8，7->(iTemp=7）7，9，8，10（交换1次)
第二轮：7，9，8，10->7，9，8，10(iTemp=8）->(iTemp=8）7，8，9，10（交换1次)
第一轮：7，8，9，10->(iTemp=9）7，8，9，10（交换0次)
循环次数：6次
交换次数：2次
其他：
第一轮：8，10，7，9->(iTemp=8）8，10，7，9->(iTemp=7）8，10，7，9->(iTemp=7）7，10，8，9（交换1次)
第二轮：7，10，8，9->(iTemp=8）7，10，8，9->(iTemp=8）7，8，10，9（交换1次)
第一轮：7，8，10，9->(iTemp=9）7，8，9，10（交换1次)
循环次数：6次
交换次数：3次
遗憾的是算法需要的循环次数依然是1/2*(n-1）*n。所以算法复杂度为O(n*n)。
我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n
所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。 插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张 #include<iostream.h>voidInsertSort(int*pData，intCount){intiTemp;intiPos;for(inti=1;i<Count;i++){iTemp=pData[i];//保存要插入的数iPos=i-1;//被插入的数组数字个数while((iPos>=0)&&(iTemp<pData[iPos])){//从最后一个（最大数字）开始对比，大于它的数字往后移位pData[iPos+1]=pData[iPos];iPos--;}pData[iPos+1]=iTemp;//插入数字的位置}}voidmain(){intdata[]={10，9，8，7，6，5，4};InsertSort(data，7);for(inti=0;i<7;i++)cout<<data<<;cout<<
;}其他：
第一轮：8，10，7，9->8，10，7，9(交换0次)(循环1次)
第二轮：9，10，8，7->8，9，10，7（交换1次)（循环2次)
第一轮：8，9，10，7->7，8，9，10（交换1次)（循环3次)
循环次数：6次
交换次数：3次
其他：
第一轮：8，10，7，9->8，10，7，9（交换0次)（循环1次)
第二轮：8，10，7，9->7，8，10，9（交换1次)（循环2次)
第一轮：7，8，10，9->7，8，9，10（交换1次)（循环1次)
循环次数：4次
交换次数：2次
上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，
因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<=
1/2*n*(n-1）<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单
排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似
选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’
而这里显然多了一些，所以我们浪费了时间。
最终，我个人认为，在简单排序算法中，选择法是最好的。 高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后
把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使
用这个过程（最容易的方法——递归）。
1.快速排序：//这段代码编译可以通过，一运行就出错，内部的细节有些问题，我还没找到解决方法。 #include<iostream.h>voidrun(int*pData，intleft，intright){inti，j;intmiddle，iTemp;i=left;j=right;middle=pData[left];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);}voidQuickSort(int*pData，intCount){run(pData，0，Count-1）;}voidmain(){intdata[]={10，9，8，7，6，5，4};QuickSort(data，7）;for(inti=0;i<7;i++)cout<<data[i]<<;//原作者此处代码有误，输出因为date[i],date数组名输出的是地址cout<<
;}这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况
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)算法，但是通常情况下速度要慢
于快速排序（因为要重组堆）。 双向冒泡
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。 #include<iostream.h>inlinevoidexchange(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}voidbubblesort(int*array,intnum){inti,j,k,flag=0;for(i=0;i<num;i++){printf(%d,array[i]);}printf(
);for(i=0;i<num;i++){//所有数的个数为num个flag=0;for(j=i;j<num-i-1;j++){//每循环一次最底端的数的顺序都会排好，所以初始时j=i;if(array[j]>array[j+1]){exchange(&array[j],&array[j+1]);flag=1;}}for(k=num-1-i-1;k>i;k--){//每循环一次最顶端的数据的顺序也会排好，所以初始时k=num-i-2if(array[k]<array[k-1]){exchange(&array[k],&array[k-1]);flag=1;}}if(flag==0){//如果flag未发生改变则说明未发生数据交换，则排序完成return;}}}voidmain(){intdata[]={10，9，8，7，6，5，4，3，2，1，-10，-1};bubblesort(data，12）;for(inti=0;i<12;i++)cout<<data<<;cout<<
;} 这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index，char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char* GetData(){ return m_strDatamember; };
//这里重载了操作符：
CMyData& operator =(CMyData &SrcData);
bool operator <(CMyData& data );
bool operator >(CMyData& data );
private:
char* m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index，char* strData):
m_iIndex(Index)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember，strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember，SrcData.GetData());
return *this;
}
bool CMyData::operator <(CMyData& data )
{
return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include MyData.h
template <class T>
void run(T* pData，int left，int right)
{
int i，j;
T middle，iTemp;
i = left;
j = right;
//下面的比较都调用我们重载的操作符函数
middle = pData[(left+right)/2]; //求中间值
do{
while((pData<middle) && (i<right))//从左扫描大于中值的数
i++；
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp = pData;
pData = 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);
}
template <class T>
void QuickSort(T* pData，int Count)
{
run(pData，0，Count-1）;
}
void main()
{
CMyData data[] = {
CMyData（8，xulion)，
CMyData（7，sanzoo)，
CMyData（6，wangjun)，
CMyData（5，VCKBASE)，
CMyData（4，jacky2000)，
CMyData（3，cwally)，
CMyData（2，VCUSER)，
CMyData（1，isdong)
};
QuickSort(data，8）;
for (int i=0;i<8;i++)
cout<<data.m_iIndex<< <<data.GetData()<<
;
cout<<
;