新建 文本文档 (3).txt

各种排序算法 附带源码 不过是以记事本的格式的 要自己建

  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"; 
} 

最后，希望大家愉快的编程。有什么意见，给我提吧！