C++ 简单排序算法

tandd1988 贡献于2014-03-17

作者 dell  创建于2014-03-17 02:17:00   修改者dell  修改于2014-03-17 02:18:00字数9267

文档摘要:下面的内排序算法可算是数据结构中的重要内容,程序代码全部用C++实现,已在visual C++6.0上运行过了。 
关键词:

  和很多计算机系的同学们一样,我在大学二年级时也学了《数据结构》这门课。当时我的老师是一个中科大的博士,现在已经是教授了。他在课上曾经这样评价这门课:《数据结构》几乎是所有计算机课程的基础课,如果把这门课学好了,其他的专业课就不成问题了。还有,IT公司的面试经常涉及到数据结构的相关知识,该课程的重要性由此可见。但是当时年少无知根本没好好学习,等到笔试,面试时才幡然悔悟。下面的内排序算法可算是数据结构中的重要内容,程序代码全部用C++实现,已在visual C++6.0上运行过了。   一.插入排序(insert sorting) 最差情况下,直接插入排序的最大时间代价为θ(n²),最小时间代价为θ(n),平均时间代价为θ(n²)。   [cpp] view plaincopyprint? 1. #include    2. using namespace std;   3.    4. /*交换函数,作用是交换数组中的两个元素的位置*/   5. void swap(int array[],int i,int j)   6. {   7.     int tmp=array[i];   8.     array[i]=array[j];   9.     array[j]=tmp;   10. }   11.    12. /*插入排序*/   13. void InsertSort(int array[],int n)   14. {   15.     for(int i=1;i0;j--)   18.         {   19.             if(array[j]>array[j-1])   20.                 swap(array,j,j-1);   21.             else   22.                 break;   23.         }   24.     }   25. }   26.    27. int main()   28. {   29.     int array[5]={3,1,2,5,4};   30.     InsertSort(array,5);   31.     for(int i=0;i<5;i++)   32.         cout<   2. using namespace std;   3.    4. /*交换函数,作用是交换数组中的两个元素的位置*/   5. void swap(int array[],int i,int j)   6. {   7.     int tmp=array[i];   8.     array[i]=array[j];   9.     array[j]=tmp;   10. }   11.    12. /*冒泡排序*/   13. void BubbleSort(int array[],int n)   14. {   15.     for(int i=0;ii;j--)   18.         {   19.             if(array[j]   2. using namespace std;   3.    4. /*交换函数,作用是交换数组中的两个元素的位置*/   5. void swap(int array[],int i,int j)   6. {   7.     int tmp=array[i];   8.     array[i]=array[j];   9.     array[j]=tmp;   10. }   11.    12. /*选择排序*/   13. void SelectionSort(int array[],int n)   14. {   15.     for(int i=0;iarray[j])   21.                 smallest=j;   22.         }   23.         swap(array,i,smallest);   24.     }   25. }   26.    27. int main()   28. {   29.     int array[5]={3,1,2,5,4};   30.     SelectionSort(array,5);   31.     for(int i=0;i<5;i++)   32.         cout<   2. using namespace std;   3.    4. /*交换函数,作用是交换数组中的两个元素的位置*/   5. void swap(int array[],int i,int j)   6. {   7.     int tmp=array[i];   8.     array[i]=array[j];   9.     array[j]=tmp;   10. }   11.    12. /*希尔排序*/   13. void ShellSort(int array[],int n)   14. {   15.     for(int delta=n/2;delta>0;delta/=2)   16.     {   17.         for(int i=0;i0;k-=delta)   22.                 {   23.                     if(array[k]   2. using namespace std;   3.    4. /*交换函数,作用是交换数组中的两个元素的位置*/   5. void swap(int array[],int i,int j)   6. {   7.     int tmp=array[i];   8.     array[i]=array[j];   9.     array[j]=tmp;   10. }   11.    12. /*将轴值放到数组的适当的位置*/   13. int partition(int array[],int left,int right)   14. {   15.     int mid=(left+right)/2;   16.     int tmp=array[mid];   17.     swap(array,mid,right);   18.     int i=left;   19.     int j=right;   20.     while(1)   21.     {   22.         /*i指针向右移动,直到找到一个大于轴值的值*/   23.         while(1)   24.         {   25.             /*如果i与j相遇则确定轴值位置,将其返回*/   26.             if(i==j)   27.             {   28.                 array[i]=tmp;   29.                 return i;   30.             }   31.             if(array[i]>tmp)   32.             {   33.                 array[j]=array[i];   34.                 j--;   35.                 break;   36.             }   37.             i++;   38.         }   39.         /*j指针向左移动,直到找到一个小于轴值的值*/   40.         while(1)   41.         {   42.             /*如果i与j相遇则确定轴值位置,将其返回*/   43.             if(i==j)   44.             {   45.                 array[j]=tmp;   46.                 return j;   47.             }   48.             if(array[j]   2. using namespace std;   3.    4. /*归并过程--将两个有序数组合并成一个有序数组*/   5. void merge(int array[],int tempArray[],int left,int right,int middle)   6. {   7.     int index1=left;   8.     int index2=middle+1;   9.     for(int i=left;(index1<=middle)&&(index2<=right);i++)   10.     {   11.         if(array[index1]   2. #include "MaxHeap.h"   3. using namespace std;   4.    5. /*最大堆排序函数*/   6. void heapSort(int array[],int n)   7. {   8.     MaxHeap max_heap=MaxHeap(array,n);   9.    10.     /*删除堆的最大值(堆顶),即每次将最大值与数组的最后一个元素交换位置*/   11.     for(int i=0;i<7;i++)   12.         max_heap.removeMax();   13. }   14.    15. int main()   16. {   17.     int array[8]={4,3,7,1,2,8,5,6};   18.     heapSort(array,8);   19.     for(int i=0;i<8;i++)   20.         cout<   2. using namespace std;   3.    4. /*最大堆定义*/   5. class MaxHeap   6. {   7. private:   8.     int size; //最大堆的元素数目   9. int * array;  //最大堆数组的首地址指针   10. public:   11.     MaxHeap(int array[],int n); //用已有数组初始化一个最大堆    12.          void buildHeap();   //构建最大堆   13.     void siftDown(int index);  //向下筛选法   14.     void swap(int index1,int index2);  //交换位置为index1与index2的元素   15.     void removeMax();  //删除堆顶的最大值--与数组最后一个元素交换位置并重新构建最大堆   16.     int leftChild(int index);  //返回左孩子的位置   17.     int rightChild(int index);  //返回右孩子的位置   18. };        MaxHeap.cpp   [cpp] view plaincopyprint? 1. #include    2. #include "MaxHeap.h"   3. using namespace std;   4.    5. /*最大堆成员函数实现*/   6. MaxHeap::MaxHeap(int array[],int n)   7. {   8.     this->array=array;   9.     size=n;   10.     buildHeap();   11. }   12.    13. void MaxHeap::buildHeap()   14. {   15.     for(int i=size/2-1;i>=0;i--)   16.         siftDown(i);   17. }   18.    19. void MaxHeap::siftDown(int index)   20. {   21.     int max_index=leftChild(index);   22.     while(max_indexarray[max_index])   25.             max_index++;   26.         if(array[index]>array[max_index])   27.             break;   28.         swap(index,max_index);   29.         index=max_index;   30.         max_index=leftChild(index);   31.     }   32. }   33.    34. void MaxHeap::swap(int index1,int index2)   35. {   36.     int temp=array[index1];   37.     array[index1]=array[index2];   38.     array[index2]=temp;   39. }   40.    41. void MaxHeap::removeMax()   42. {   43.     swap(0,size-1);   44.     size--;   45.     siftDown(0);   46. }   47.    48. int MaxHeap::leftChild(int index)   49. {   50.     return index*2+1;   51. }   52.    53. int MaxHeap::rightChild(int index)   54. {   55.     return index*2+2;   56. }        八.基数排序(radix sorting) 基数排序的时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法。基数排序法是属于稳定性的排序。   [cpp] view plaincopyprint? 1. #include    2. using namespace std;   3.    4. /*计算关键字位数的最大值*/   5. int KeySize(int array[],int size)   6. {   7.     int key_size=1;   8.    9.     for(int i=0;i0)   14.         {   15.             temp++;   16.             n*=10;   17.         }   18.         key_size=(temp>key_size)?temp:key_size;   19.     }   20.     return key_size;   21. }   22.    23. /*基数排序*/   24. void RadixSort(int array[],int size)   25. {   26.     int bucket[10][10]={0};//定义基数桶   27.     int order[10]={0};//保存每个基数桶之中的元素个数   28.     int key_size=KeySize(array,size);//计算关键字位数的最大值   29.        30.     for(int n=1;key_size>0;n*=10,key_size--)   31.     {   32.         /*将待排序的元素按照关键值的大小依次放入基数桶之中*/   33.         for(int i=0;i

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档