devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

排序算法总结_1、给定数组a,其中有n个元素且按照字典序从小到大排列: a={1, 3, 5, 7} 使用递归

作者：木道寻08 | 2024-08-03 19:37:25

赞

踩

1、给定数组a,其中有n个元素且按照字典序从小到大排列: a={1, 3, 5, 7} 使用递归

1. 冒泡


原理：将序列划分为无序和有序区，不断通过交换较大元素至无序区尾完成排序。

要点：设计交换判断条件，提前结束以排好序的序列循环。

  1. void BubbleSortArray() 
  2. { 
  3.       for(int i=1;i<n;i++) 
  4.       { 
  5.           int flag=false;//交换标志
  6.         for(int j=0;j<n-i;j++) 
  7.          { 
  8.               if(a[j]>a[j+1])//比较交换相邻元素 
  9.                { 
  10.                    int temp; 
  11.                    temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; 
  12.                    flag=true;
  13.                } 
  14.          } 
  15.            if(!flag)break;
  16.       } 
  17. }

效率 O（n²）,适用于排序小列表。 


2.  选择排序

原理：将序列划分为无序和有序区，寻找无序区中的最小值和无序区的首元素交换，有序区扩大一个，循环最终完成全部排序。

  1. void SelectSortArray() 
  2. { 
  3.     int min_index; 
  4.     for(int i=0;i<n-1;i++) 
  5.     { 
  6.          min_index=i; 
  7.          for(int j=i+1;j<n;j++)//每次扫描选择最小项 
  8.             if(arr[j]<arr[min_index])  min_index=j; 
  9.          if(min_index!=i)//找到最小项交换，即将这一项移到列表中的正确位置 
  10.          { 
  11.              int temp; 
  12.              temp=arr[i];     arr[i]=arr[min_index];   arr[min_index]=temp; 
  13.          } 
  14.     } 
  15. }

效率 O（n²）,适用于排序小列表。 


3. 插入排序

原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。

要点：设立哨兵，作为临时存储和判断数组边界之用。

  1. void InsertSortArray() 
  2. { 
  3.    for(int i=1;i<n;i++)//循环从第二个数组元素开始，因为arr[0]作为最初已排序部分 i，j分别为有序区和无序区指针
  4.   { 
  5.     int temp=arr[i];//temp标记为未排序第一个元素 
  6.     int j=i-1; 
  7.     while (j>=0 && arr[j]>temp)/*将temp与已排序元素从小到大比较，寻找temp应插入的位置*/ 
  8.       { 
  9.         arr[j+1]=arr[j]; 
  10.          j--; 
  11.       } 
  12.      arr[j+1]=temp; 
  13.    } 
  14. }
最佳效率O（n）；最糟效率O（n²）与冒泡、选择相同，适用于排序小列表
若列表基本有序，则插入排序比冒泡、选择更有效率。

4. 希尔排序

原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。

要点：增量的选择以及排序最终以1为增量进行排序结束。

实现：

  1. Void shellSort(Node L[],int d)
  2.  
  3. {
  4.  
  5.    While(d>=1)//直到增量缩小为1
  6.    {
  7.  
  8.     Shell(L,d);
  9.  
  10.     d=d/2;//缩小增量
  11.  
  12.    }
  13.  
  14. }
  15.  
  16. Void Shell(Node L[],int d)
  17.  
  18. {
  19.  
  20.    Int i,j;
  21.  
  22.    For(i=d+1;i<length;i++)
  23.  
  24.    {
  25.  
  26.      if(L[i]<L[i-d])
  27.  
  28.      {
  29.  
  30.         L[0]=L[i];
  31.  
  32.         j=i-d;
  33.  
  34.        While(j>0&&L[j]>L[0])
  35.  
  36.           {
  37.  
  38.                L[j+d]=L[j];//移动
  39.  
  40.                j=j-d;//查找
  41.  
  42.            }
  43.  
  44.        L[j+d]=L[0];
  45.  
  46.      }
  47.  
  48.    }
  49.  
  50. }

适用于排序小列表。
效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。
壳（Shell）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。


5. 归并排序

转自：http://blog.csdn.net/eric491179912/article/details/6754905


归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。
1.两路归并排序算法思路
①把 n 个记录看成 n 个长度为 l 的有序子表；
②进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表；
③重复第②步直到所有记录归并成一个长度为 n 的有序表为止。
【例】 有一组关键字 {4,7,5,3,2,8,6,1},n=8, 将其按由小到大的顺序排序。 两路归并排序操作过程如图 9.12 所示，其中 l 为子表长度。

2.算法实现
　　此算法的实现不像图示那样简单，现分三步来讨论。首先从宏观上分析，首先让子表表长 L=1 进行处理；不断地使 L=2*L ，进行子表处理，直到 L>=n 为止，把这一过程写成一个主体框架函数 mergesort 。然后对于某确定的子表表长 L ，将 n 个记录分成若干组子表，两两归并，这里显然要循环若干次，把这一步写成一个函数 mergepass ，可由 mergesort 调用。最后再看每一组（一对）子表的归并，其原理是相同的，只是子表表长不同，换句话说，是子表的首记录号与尾记录号不同，把这个归并操作作为核心算法写成函数 merge ，由 mergepass 来调用。
3.具体算法
[cpp] view plaincopy



引子：这篇文章以前写过，最近复习排序算法，觉得以前的代码还可以改进，因此有了此文。

归并排序算法以O（NlogN）最坏情形运行时间运行，而所使用的比较次数几乎是最优的。

该算法中最基本的操作是合并两个已排序的表，这只需要线性的时间，但同时需要分配一个临时数组来暂存数据。

归并排序算法可以用递归的形式实现，形式简洁易懂。如果N=1，则只有一个元素需要排序，我们可以什么都不做；否则，递归地将前半部分数据和后半部分数据各自归并排序，然后合并这两个部分。

归并排序算法也可以用非递归的形式实现，稍微难理解一点。它刚好是递归分治算法的逆向思维形式，在使用递归分治算法时，程序员只需考虑将一个大问题分成若干个形式相同的小问题，和解的边界条件，具体如何解决这些小问题是由计算机自动完成的；而非递归形式要求程序员从最基本的情况出发，即从解决小问题出发，一步步扩展到大问题。

我这里两种形式都给出。

另外，很多人在写递归形式的归并排序算法时，临时数组是在MergeSort函数中分配的，这使得在任一时刻都可能有logN个临时数组处在活动期，如果数据较多，则开销很大，实用性很差。

我把临时数组设置在Merge函数中，避免了这个问题。

///

递归形式：

template <class T>

void MSort(T a[], int left, int right)

{

if (left < right)

{

int center = (left + right) / 2;

MSort(a, left, center);

MSort(a, center+1, right);

Merge(a, left, center+1, right+1);

}

}



template <class T>

void MergeSort(T a[], int n)

{

MSort(a, 0, n-1);

}

///

非递归形式：

算法介绍：先介绍三个变量beforeLen，afterLen和i的作用：

int beforeLen; //合并前序列的长度

int afterLen;//合并后序列的长度，合并后序列的长度是合并前的两倍

int i = 0;//开始合并时第一个序列的起始位置下标，每次都是从0开始

i，i+beforeLen，i+afterLen定义被合并的两个序列的边界。

算法的工作过程如下：

开始时，beforeLen被置为1，i被置为0。外部for循环的循环体每执行一次，都使beforeLen和afterLen加倍。内部的while循环执行序列的合并工作，它的循环体每执行一次，i都向前移动afterLen个位置。当n不是afterLen的倍数时，如果被合并序列的起始位置i，加上合并后序列的长度afterLen，超过输入数组的边界n，就结束内部循环；此时如果被合并序列的起始位置i，加上合并前序列的长度beforeLen，小于输入数组的边界n，还需要执行一次合并工作，把最后长度不足afterLen，但超过beforeLen的序列合并起来。这个工作由语句Merge(a, i, i+beforeLen, n);完成。



template <class T>

void MergeSort(T a[], int n)

{

int beforeLen; //合并前序列的长度

int afterLen = 1;//合并后序列的长度



for (beforeLen=1; afterLen<n; beforeLen=afterLen)

{

afterLen = beforeLen << 1; //合并后序列的长度是合并前的两倍



int i = 0;//开始合并时第一个序列的起始位置下标，每次都是从0开始

for ( ; i+afterLen<n; i+=afterLen)

Merge(a, i, i+beforeLen, i+afterLen);



if (i+beforeLen < n)

Merge(a, i, i+beforeLen, n);

}

}

///

上面两种算法都要用到下面的合并函数。

/*函数介绍：合并两个有序的子数组

输入：数组a[]，下标left，center，元素个数len，a[left]~a[center-1]及a[center]~a[len-1]已经按非递减顺序排序。

输出：按非递减顺序排序的子数组a[left]~a[len-1]。

*/

template <class T>

void Merge(T a[], int left, int center, int len)

{

T *t = new T[len-left];//存放被合并后的元素

int i = left;

int j = center;

int k = 0;



while (i<center && j<len)

{

if (a[i] <= a[j])

t[k++] = a[i++];

else

t[k++] = a[j++];

}



while (i < center)

t[k++] = a[i++];



while (j < len)

t[k++] = a[j++];



//把t[]的元素复制回a[]

for (i=left,k=0; i<len; i++,k++)

a[i] = t[k];



delete []t;

}


c算法分析
（1）稳定性
　归并排序是一种稳定的排序。
（2）存储结构要求
　可用顺序存储结构。也易于在链表上实现。
（3）时间复杂度
　对长度为n的文件，需进行 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
（4）空间复杂度
　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
注意：
　若用单链表做存储结构，很容易给出就地的归并排序。 


6. 快速排序

  1. /*快速排序的算法思想：选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程。*/                  void swap(int a,int b){int t;t =a ;a =b ;b =t ;} 
  2.         int Partition(int [] arr,int low,int high) 
  3.         { 
  4.             int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素 
  5.             while (low < high) 
  6.             { 
  7.                 //从后往前栽后半部分中寻找第一个小于枢纽元素的元素 
  8.                 while (low < high && arr[high] >= pivot) 
  9.                 { 
  10.                     --high; 
  11.                 } 
  12.                 //将这个比枢纽元素小的元素交换到前半部分 
  13.                 swap(arr[low], arr[high]); 
  14.                 //从前往后在前半部分中寻找第一个大于枢纽元素的元素 
  15.                 while (low <high &&arr [low ]<=pivot ) 
  16.                 { 
  17.                     ++low ; 
  18.                 } 
  19.                 swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分 
  20.             } 
  21.             return low ;//返回枢纽元素所在的位置 
  22.         } 
  23.         void QuickSort(int [] a,int low,int high) 
  24.         { 
  25.             if (low <high ) 
  26.             { 
  27.                 int n=Partition (a ,low ,high ); 
  28.                 QuickSort (a ,low ,n ); 
  29.                 QuickSort (a ,n +1,high ); 
  30.             } 
  31.         }

平均效率O（nlogn），适用于排序大列表。
此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n²）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。
基于分治法。


7. 堆排序

  1.     #include <iostream>  
  2.       
  3.     using namespace std;  
  4.       
  5.     template<class T>  
  6.     void Sift(T* heap,int start,int end)    //start和end标示无序区  
  7.     {  
  8.         T temp = heap[start];   //记录  
  9.         int parent = start;  
  10.         int child = 2*start+1;  
  11.         while (child<=end)  
  12.         {  
  13.             if(child<end&&heap[child]<heap[child+1])  
  14.                 child++;  
  15.             if(heap[child]>temp)  
  16.             {  
  17.                 heap[parent]=heap[child];  
  18.                 parent = child;  
  19.                 child = 2*child+1;  
  20.                 continue;  
  21.             }  
  22.             else  
  23.                 break;  
  24.         }  
  25.         heap[parent] = temp;  
  26.     }  
  27.       
  28.     template <class T>  
  29.     void MakeHeap(T* heap,int Size)  
  30.     {  
  31.         int end;  
  32.     //由于所有树叶无需进行下滤（没有孩子）， 所以只对0 - size/2的结点进行下滤即可
  33.         for(int start = Size/2-1;start>=0;start--)  
  34.             Sift(heap,start,Size-1);  
  35.     }  
  36.       
  37.     template <class T>  
  38.     void HeapSort(T* heap,int Size)  
  39.     {  
  40.         MakeHeap(heap,Size);  
  41.         T temp;  
  42.         for (int i = Size-1;i >= 0;i--)  
  43.         {  
  44.             temp = heap[i];  
  45.             heap[i] = heap[0];  
  46.             heap[0] = temp;  
  47.             Sift(heap,0,i-1);  
  48.         }  
  49.         for (int i = 0;i < Size;i++)  
  50.         {  
  51.             cout<<heap[i]<<endl;  
  52.         }  
  53.     }  
  54.       
  55.     int main()  
  56.     {  
  57.         int num[10] = {1,4,3,8,9,0,2,7,5,6};  
  58.         HeapSort<int>(num,10);  
  59.     }

本质上，堆排序就是选择排序，每次选择当前无序区最大的放入有序区。

对于直接选择排序，选择的过程要进行遍历，一次选择过程的复杂度为O(n)。堆排序利用堆的性质和二叉树的结构使得每次选择的复杂度降低为O(logn)，从而有效地改进了选择排序。

8. 基数排序（待定）


9. 拓扑排序

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/924538
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号