c/c++ 算法之快速排序法 冒泡排序法,选择排序法,插入排序法

本文详细叙述和实现了快速排序算法,冒泡排序 选择排序 插入排序比较简单,原理在这里不再详述,直接用代码进行了实现。

快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二,分别对左边与右边数列进行排序,而影响快速排序法效率的正是轴心的选择。
这边所介绍的第一个快速排序法版本,是在多数的教科书上所提及的版本,因为它最容易理解,最符合轴心分割与左右进行排序的概念,适合对初学者进行讲解。

解法这边所介绍的快速演算如下:将最左边的数设定为轴,并记录其值为s
廻圈处理:
令索引i 从数列左方往右方找,直到找到大于s 的数
令索引j 从数列左右方往左方找,直到找到小于s 的数
如果i>=j,则离开回圈
如果i<j,则交换索引i与j两处的值
将左侧的轴与j 进行交换
对轴左边进行递回
对轴右边进行递回
透过以下演算法,则轴左边的值都会小于s,轴右边的值都会大于s,如此再对轴左右两边进行
递回,就可以对完成排序的目的,例如下面的实例,*表示要交换的数,[]表示轴:
[41] 24 76* 11 45 64 21 69 19 36*
[41] 24 36 11 45* 64 21 69 19* 76
[41] 24 36 11 19 64* 21* 69 45 76
[41] 24 36 11 19 21 64 69 45 76
21 24 36 11 19 [41] 64 69 45 76

算法实现c/c++版:

/*快速排序法
sort 函数说明,添加者 Steve;
left:数组a的最小下标;
right:数组a的最大下标;
a[]:数组;
N:数组长度
*/

void  sort(int left,int right ,int a[],int N)
 {
  if (left<right)
  {
   int al=left;
   int ar=right+1;
   int aleft=a[left];
 
   while(1)
   {
    while((al+1<N)&&(aleft>a[++al]));
 
    while((ar-1>-1)&&(aleft<a[--ar]));
    if (al>=ar)
    {
     break;
    }
 
    int temp=a[al];
    a[al]=a[ar];
    a[ar]=temp;
         }
 
  a[left]=a[ar];
  a[ar]=aleft;
 
   sort(left,ar-1,a,N);
   sort(ar+1,right,a,N);
  
  }
  
 }

//冒泡排序法

void bufferSort(int a[],int N)
 {
  for (int i=0;i<N-1;i++)
   for(int j=0;j<N-i-1;j++)
  {
   if (a[j]>a[j+1])
   {
    int temp=a[j];
    a[j]=a[j+1];
    a[j+1]=temp;
   }
  
  }

}

//选择排序法
 void SelectSort(int a[],int N)
 {
  for (int i=0;i<N-1;i++)
  {
     int Min=a[i];
     int index=i;

for(int j=i+1;j<N;j++)
      if (Min>a[j])
      {
    Min=a[j];
    index=j;
      }
   a[index]=a[i];
   a[i]=Min;
 
  }
 }

//插入排序法

void inserSort(int a[],int N)
 {
  for ( int i=1;i<N;i++ )
  {
   int temp=a[i];
  int  j=i-1;
   while(temp<a[j])
   {
    a[j+1]=a[j];
   
    j--;
    if(j<0)
     break;

}
    a[j+1]=temp;
  }
 }
 int _tmain(int argc, _TCHAR* argv[])
 {
  int a[]={-2,3,4,-9};
 
  cout<<" 排序前"<<endl;
  for (int i=0;i<4;i++)
  {
   cout<<a[i]<<" ";
  }
  cout<<endl<<"排序后"<<endl;
  //sort(0,3,a,4);//快速排序
   // bufferSort(a,4);//冒泡排序
    // SelectSort(a,4);//选择排序
 inserSort(a,4);
  for (int i=0;i<4;i++)
  {
   cout<<a[i]<<" ";
  }
  return 0;
 }

如果有更好的排序思想,欢迎交流

上一篇:OpenStack-Ocata版+CentOS7.6 云平台环境搭建 — 4.镜像服务(glance)


下一篇:Event(事件)