排序技术_各种算法原理 图解 代码兑现

排序技术_各种算法原理 图解 代码实现

排序技术有很多种，下面简单介绍一下几种。

一  插入排序1.1  直接插入排序基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。
图解：

代码实现：

//直接顺序排序void InsertSort(int r[], int n){    for (int i=2; i<n; i++){       r[0]=r[i];                        //设置哨兵  for (int j=i-1; r[0]<r[j]; j--)   //寻找插入位置        r[j+1]=r[j];                //记录后移  r[j+1]=r[0];                 }for(int k=1;k<n;k++)       cout<<r[k]<<" ";  cout<<"\n";}

1.2 希尔排序基本思想是： 先将整个待排序记录序列分割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。
图解：
代码实现：

//希尔排序void ShellSort(int r[], int n){int i;int d;int j;    for (d=n/2; d>=1; d=d/2)            //以增量为d进行直接插入排序{     for (i=d+1; i<n; i++)    {                r[0]=r[i];                 //暂存被插入记录               for (j=i-d; j>0 && r[0]<r[j]; j=j-d)                     r[j+d]=r[j];       //记录后移d个位置                          r[j+d]=r[0]; }}   for(i=1;i<n;i++)       cout<<r[i]<<" ";   cout<<"\n";}

二 交换排序2.1 起泡排序起泡排序是交换排序中最简单的排序方法，其基本思想是： 两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。
图解：


代码实现：

//起泡排序void BubbleSort(int r[], int n){int temp;int exchange;int bound;    exchange=n-1;                       //第一趟起泡排序的范围是r[0]到r[n-1]while (exchange)                    //仅当上一趟排序有记录交换才进行本趟排序{bound=exchange; exchange=0;      for (int j=0; j<bound; j++)     //一趟起泡排序    if (r[j]>r[j+1]) {  temp=r[j];  r[j]=r[j+1];  r[j+1]=temp;  exchange=j;                   //记录每一次发生记录交换的位置   }}for(int i=0;i<n;i++)       cout<<r[i]<<" ";cout<<"\n";}

2.2快速排序基本思想:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
图解：

代码实现：

//快速排序一次划分int Partition(int r[], int first, int end){int i=first;                        //初始化int j=end;int temp;            while (i<j){         while (i<j && r[i]<= r[j])j--;                        //右侧扫描       if (i<j)   {  temp=r[i];                 //将较小记录交换到前面         r[i]=r[j];         r[j]=temp;              i++;    }       while (i<j && r[i]<= r[j])    i++;                         //左侧扫描           if (i<j)   {              temp=r[j];          r[j]=r[i];          r[i]=temp;                //将较大记录交换到后面               j--;    }}    return i;                           //i为轴值记录的最终位置}//快速排序void QuickSort(int r[], int first, int end){    if (first<end) {                                   //递归结束           int pivot=Partition(r, first, end);  //一次划分           QuickSort(r, first, pivot-1);//递归地对左侧子序列进行快速排序           QuickSort(r, pivot+1, end);  //递归地对右侧子序列进行快速排序}}

三 选择排序3.1 简单选择排序基本思想：设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。
图解：
代码实现：

//简单选择排序void SelectSort(int r[ ], int n){ int i;int j;int index;int temp;    for (i=0; i<n-1; i++)              //对n个记录进行n-1趟简单选择排序{         index=i;        for (j=i+1; j<n; j++)            //在无序区中选取最小记录        if (r[j]<r[index]) index=j;       if (index!=i)    {  temp=r[i];  r[i]=r[index];  r[index]=temp;   }}    for(i=0;i<n;i++)        cout<<r[i]<<" ";    cout<<"\n";}

3.2 堆排序

堆的定义

    堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（小根堆）；或者每个结点的值都大于或等于其左右孩子结点的值（大根堆）。

大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆（Binary Heap），类似地可定义k叉堆。

假设当前要筛选结点的编号为k，堆中最后一个结点的编号为m，并且结点k的左右子树均是堆（即r[k+1] ~ r[m]满足堆的条件），则筛选算法用伪代码可描述为：

具体的筛选代码如下：

//筛选法调整堆void Sift(int r[], int k, int m){  int i;int j;int temp;i=k; j=2*i+1;                            //置i为要筛的结点，j为i的左孩子  while (j<=m)                          //筛选还没有进行到叶子  {      if (j<m && r[j]<r[j+1])   j++;                          //比较i的左右孩子，j为较大者      if (r[i]>r[j]) break;             //根结点已经大于左右孩子中的较大者      else   {           temp=r[i];       r[i]=r[j];   r[j]=temp;                   //将根结点与结点j交换           i=j;   j=2*i+1;                     //被筛结点位于原来结点j的位置 }  }}

堆排序

堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。

代码实现：

//堆排序void HeapSort(int r[ ], int n){     int i;  int temp;  for (i=n/2; i>=0; i--)                //初始建堆，从最后一个非终端结点至根结点     Sift(r, i, n) ;        for (i=n-1; i>0; i--)                //重复执行移走堆顶及重建堆的操作   {   temp=r[i];   r[i]=r[0];   r[0]=temp;      Sift(r, 0, i-1);   }   for(i=0;i<n;i++)      cout<<r[i]<<" ";   cout<<"\n";}

四 归并排序二路归并排序基本思想：将若干个有序序列进行两两归并，直至所有待排序记录都在一个有序序列为止。


一路归并算法实现：

//一次归并void Merge(int r[], int r1[], int s, int m, int t){int i=s;int j=m+1;int k=s;           while (i<=m && j<=t) {            if (r[i]<=r[j])  r1[k++]=r[i++];            //取r[i]和r[j]中较小者放入r1[k]         else  r1[k++]=r[j++];  }      if (i<=m)   while (i<=m)                  //若第一个子序列没处理完，则进行收尾处理           r1[k++]=r[i++];       else    while (j<=t)                  //若第二个子序列没处理完，则进行收尾处理        r1[k++]=r[j++]; }

//一趟归并void MergePass(int r[ ], int r1[ ], int n, int h){int i=0;int k;   while (i<=n-2*h)                     //待归并记录至少有两个长度为h的子序列   {     Merge(r, r1, i, i+h-1, i+2*h-1);        i+=2*h;   }   if (i<n-h)    Merge(r, r1, i, i+h-1, n);       //待归并序列中有一个长度小于h   else for (k=i; k<=n; k++)            //待归并序列中只剩一个子序列        r1[k]=r[k];}//归并排序的非递归算法void MergeSort1(int r[ ], int r1[ ], int n ){   int h=1;  int i;  while (h<n)  {    MergePass(r, r1, n-1, h);           //归并    h=2*h;    MergePass(r1, r, n-1, h);    h=2*h;  }  for(i=0;i<n;i++)      cout<<r[i]<<" ";  cout<<"\n";}

下面看看二路归并排序的递归实现

//归并排序的递归算法void MergeSort2(int r[], int r1[], int r2[],int s, int t){  int m;if (s==t) {r1[s]=r[s];}    else {             m=(s+t)/2;            MergeSort2(r, r2, r1, s, m);        //归并排序前半个子序列            MergeSort2(r, r2, r1, m+1, t);      //归并排序后半个子序列            Merge(r2, r1, s, m, t);             //将两个已排序的子序列归并 } }

总结各种排序方法的比较（未完待续）：

查看更多 下一篇