几种最简单的常用排序算法（c/c++)

一站幸福

非常适合初学者
1.快速排序（c++）

#include<iostream> #include<vector> #include<iterator> using namespace std; class FastSort { private:          vector<int> array; public:          int create();          int paixu(vector<int>& array,int left,int right);          inline int usepaixu();          int print(); }; int FastSort::create() {     cout<<"请输入要排序的数组，以CTRL+Z结束:"<<endl;     int number;     while(cin>>number)     array.push_back(number);     return 0; } int FastSort::paixu(vector<int>& array,int left,int right) {     if(array.empty())     {         create();     }     int newleft=left;     int newright=right;     int mid=array[left];     int temp=0;     while(newleft<newright)          {             while(array[newright]>=mid&&newleft!=newright)                   --newright;             if(array[newright]<mid) array[newleft]=array[newright];             while(array[newleft]<=mid&&newleft!=newright)                   ++newleft;             if(array[newleft]>mid)  array[newright]=array[newleft];          }    array[newleft]=mid;    if(left<newleft-1)   paixu(array,left,newleft-1);    if(right>newright+1) paixu(array,newright+1,right);    return 0; } int FastSort::usepaixu() {     paixu(array,0,array.size()-1);     return 0; } int FastSort::print() {     cout<<"排序后的数组为:"<<endl;     for(vector<int>::iterator iter=array.begin()         ;iter!=array.end();iter++)         cout<<*iter<<" "<<flush;     cout<<endl;     return 0; } int main() {     FastSort test;     test.create();     test.usepaixu();     test.print();     system("pause");     return 0; }

2.快速排序（c)

#include"stdio.h" void quick_sort(int s[], int l, int r) { int k,a,b,m=s[l]; a=l,b=r; while(l<r) {   if(s[r]<=m)   {    s[l]=s[r];    s[r]=s[++l];    s[l]=m;   }   else r--;         quick_sort(s,a,l-1);   quick_sort(s,l+1,b); } }int main() { int array[]={53,36,48,41,60,7,13,5,56}; int l=0,r=sizeof(array)/sizeof(int)-1;     quick_sort(array, l, r); for(l=0;l<=r;l++) printf("%d ",array[l]);     printf("\n");     return 0; }

3.希尔排序

#include"stdio.h" int main() { int array[]={113,76,55,23,60,17,18,85,66,11}; int h,j,i,m,len=sizeof(array)/sizeof(int);     for(h=len/2;h>0;h=h/2) {   for(j=h;j<len;j++)   {    for(i=j-h;i>=0;i=i-h)    {     m=array;                 if(array[i+h]<m)                 {        array=array[i+h];        array[i+h]=m;                 }    }   } } for(j=0;j<len;j++) printf("%d ",array[j]); printf("\n"); getchar();     return 0; }

4.选择排序

#include"stdio.h" int main() { int array[6]={24,70,12,85,106,8}; int i,j,n=0,middle,sub,min; for(j=0;j<6;j++) { min=array[n]; for(i=n;i<6;i++) {   if(min>array)   {    min=array;          sub=i;   } }     middle=array[n]; array[n]=array[sub]; array[sub]=middle; n++; }     for(j=0;j<6;j++) printf("%d ",array[j]); printf("\n"); return 0; }

5.冒泡排序

#include<iostream> #include<vector> #include<iterator> using namespace std; class sort { private:     vector<int> dig; public:     int newner();     int paixu();     int print(); }; int sort::newner() {     cout<<"请输入你排序的数组:"<<endl;     int number;     while(cin>>number)         dig.push_back(number);     return 0; } int sort::paixu() {     for(int i=0;i!=dig.size();i++)     for(vector<int>::iterator iter=dig.begin()         ;iter!=dig.end()-1;iter++)         if(*iter>*(iter+1))         {             iter=dig.insert(iter,*(iter+1));             iter=iter+2;             iter=dig.erase(iter);             iter=iter-2;         }     cout<<endl;         return 0; } int sort::print() {     if(dig.empty())     {         cout<<"没有输入要输入的数组!"<<endl;         return 1;     }     cout<<"排序后的数组为："<<endl;     for(vector<int>::iterator iter=dig.begin()         ;iter!=dig.end();iter++)         cout<<*iter<<" "<<flush;     cout<<endl;     return 0; } int main() {     sort test;     test.newner();     test.paixu();     test.print();     return 0; }

6.排序树

#include<iostream> #include<vector> #include<iterator> using namespace std; class SortTree { private:     struct node     {         int data;         node* left;         node* right;         node(const int x=0):data(x),left(),right(){}     };     node* root; public:     SortTree():root(){}     int insert(node*& a,node*& b);     int insert(const int& x);     int print(node*& p);     int print();     int clear(node*& p);     ~SortTree(); }; int SortTree::clear(node*& p) {     if(p==NULL) return 0;     clear(p->left);     clear(p->right);     delete p;     return 0; } SortTree::~SortTree() {     clear(root); } int SortTree::insert(node*& a,node*& b) {     if(b==NULL) { b=a;return 0;}     if(a->data>b->data) insert(a,b->right);     else insert(a,b->left);     return 0; } int SortTree::insert(const int& x) {     node* p=new node(x);     insert(p,root);     return 0; } int SortTree::print(node*& p) {     if(p==NULL) return 0;     print(p->left);     cout<<p->data<<" "<<flush;     print(p->right);     return 0; } inline int SortTree::print() {     print(root);     return 0; } int main() {     SortTree test;     srand(10);     for(int i=0;i<10;i++)     {         int t=rand()%100;         test.insert(t);     }     test.print();     cout<<endl;     return 0; }

7.堆排序

#include<iostream> #include<vector> #include<iterator> using namespace std; class DuiSort { private:     vector<int> nArray; public:     int create();     int swap(int& a,int& b);     int paixu();     int print(); }; int DuiSort::create() {     cout<<"请输入要排序的数组:"<<endl;     int number;     while(cin>>number)         nArray.push_back(number);     return 0; } int DuiSort::swap(int& a,int& b) {     int temp=a;     a=b;     b=temp;     return 0; } int DuiSort::paixu() {     int size=nArray.size();     if(nArray.empty())         create();     for(int i=size/2-1;i>=0;i--)          while(2*i+1<size)          {               int j=2*i+1;               if((j+1)<size&&nArray[j]<nArray[j+1])                  j++;               if(nArray<nArray[j])               {                   swap(nArray,nArray[j]);                   i=j;               }               else break;           }      for(int i=size-1;i>0;i--)          {                swap(nArray[0],nArray);                int t=0;                while(2*t+1<i)                {                     int j=2*t+1;                     if((j+1)<i&&nArray[j]<nArray[j+1])                        j++;                     if(nArray[t]<nArray[j])                     {                        swap(nArray[t],nArray[j]);                        t=j;                     }                     else  break;                }          }          return 0; } int DuiSort::print() {      cout<<"排序后的数组为:"<<endl;      for(vector<int>::iterator iter=nArray.begin();          iter!=nArray.end();iter++)          cout<<*iter<<" "<<flush;      cout<<endl;      return 0; } int main() {      DuiSort test;      test.create();      test.paixu();      test.print();      return 0; }

8.选择排序（动态链表）

#define null 0 #include"stdio.h" #include"malloc.h" struct student { int num; struct student *next; }; int n=0; struct student *create(void) { struct student *head,*p1,*p2; p1=p2=(struct student*)malloc(sizeof(struct student)); head=null; scanf("%d",&p1->num); while(p1->num!=null) { n=n+1; if(n==1)head=p1; p1=(struct student*)malloc(sizeof(struct student)); p2->next=p1; p2=p1; scanf("%d",&p1->num); } p1->next=null; return(head); } /*------------------    动态链表的建立 -------------------*/ struct student *paixu(struct student *head) { struct student *listp,*limbo,*listx; /*----------------------------------------------------------------------------------------------------------    1.listP为无序区链表的遍历指针，作提取节点和有序区比较的作。    2.limbo为过渡指针，每当无序区遍历到的节点值小于有序区节点遍历到的值，则节点插到有序区链表的最后面，并且把      此节点的next地址设定为null，next为null为有序区链表遍历结束的条件，为了不使无序区的节点失去联系，需要把此   节点next的值赋值给limbo,再把null赋值给next，把limbo的值赋值给listp，使listP指向无序区下一个需要插入节点。    3.listx为有序区链表的便利指针，listx->next=null为遍历结束的标示。 ------------------------------------------------------------------------------------------------------------*/ listp=limbo=listx=head; if(listp->num!=null) { listp=listp->next; head->next=null; } else printf("链表为空，无法排序"); /*-----------------------------------------------------------------------------------------    把第一个节点放入有序区，listp指向下一个需要比较的节点，然后把刚放入有序的阶段的next设为null。 -------------------------------------------------------------------------------------------*/ if(listp->num!=null) { if(listp->num>head->num) { limbo=listp->next; listp->next=head; head=listp; listp=limbo; } else { head->next=listp; limbo=listp->next; listp->next=null; listp=limbo; } } /*------------------------------------------------------------------------------------------------ 第二个节点放入有序区，如果大于有序区的首节点，就让有序区的头指针指向它，指针listP指向下一个需要 比较的节点；否则就把节点的next设置为null，在让指针p指向下一个需要比较的节点（利用过渡节点limbo）。 -------------------------------------------------------------------------------------------------*/ while(listp->num!=null) { listx=head; while(listx->next!=null) { if(listp->num>listx->num) { limbo=listp->next; listp->next=head; head=listp; listp=limbo; break; } if(listp->num>=listx->next->num&&listp->num<=listx->num) { limbo=listp->next; listp->next=listx->next; listx->next=listp; listp=limbo; break; } else { listx=listx->next; } } if(listx->next==null&&listp->num<listx->num) { listx->next=listp; limbo=listp->next; listp->next=null; listp=limbo; } } /*-------------------------------------------------------------------------------------------------------------------------------- 把其余节点依次放入有序区， 如果大于有序区的首节点，就让有序区的头指针指向它，指针listP指向下一个需要比较的节点； 如果小于有序区的当前尾节点，插入在有序区链表尾部，把节点的next设置为null，让指针listp指向下一个需要比较的节点（用过渡节点limbo）； 如果小于等于当前listx指向的节点并且大于等于listx->next指向的节点，就插入他们中间。 ---------------------------------------------------------------------------------------------------------------------------------*/ return(head); /*------------------------- 把head的值返回给函数。 --------------------------*/ } int print(struct student *head) { struct student *y; y=head; while(y) { printf("%d ",y->num); y=y->next; } return 0; } /*--------------      链表输出 ---------------*/ int main(void) { struct student *head,*a; head=create(); a=paixu(head); print(a); return 0; }

506076894

我去年买了个表