排序算法新版（懒得继续_随笔

排序算法新版（懒得继续排序算法

文章目录

- 排序算法
- - 比较类算法
  - - 插入排序
    - - 1. 直接插入排序
      - 2. 折半插入排序
      - 3. 希尔排序
    - 交换排序
    - - 4. 冒泡排序
      - 5. 快速排序
    - 选择排序
    - - 6. 简单选择排序
      - 7. 1堆排序（最大堆）
      - 7. 2 堆排序（最小堆）
    - 归并排序
    - - 8. 二路归并排序
      - 9. 多路归并排序
  - 非比较类算法
  - - - 10. 计数排序
      - 11. 桶排序
      - 12. 基数排序
  - 非比较类算法
  - - - 10. 计数排序
      - 11. 桶排序
      - 12. 基数排序

排序算法方法时间复杂度/平均时间复杂度/最坏时间复杂度/最好空间复杂度稳定性直接插入排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1)稳定折半插入排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1)稳定希尔排序 O ( n 1.3 ) O(n^{1.3}) O(n1.3) O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1)不稳定冒泡排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1)稳定快速排序 O ( n l o g 2 n ) O(nlog_2 n) O(nlog2n) O ( n 2 ) O(n^2) O(n2) O ( n l o g 2 n ) O(nlog_2 n) O(nlog2n) O ( n ) O(n) O(n)/ O ( l o g 2 n ) O(log_2 n) O(log2n)不稳定简单选择排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)不稳定堆排序 O ( n l o g 2 n ) O(nlog_2 n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2 n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2 n) O(nlog2n) O ( 1 ) O(1) O(1)不稳定二路归并排序 O ( n l o g 2 n ) O(nlog_2 n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2 n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2 n) O(nlog2n) O ( n ) O(n) O(n)稳定多路归并排序计数排序桶排序基数排序比较类算法插入排序

把目标插入到一个已经有序的序列中它应该在的位置上

1. 直接插入排序

原理

The algorithm that people often use to sort bridge hands is to consider the cards one at a time , inserting each into its proper place among those alreadly considered(keeping them sorted). In a computer implementation , we need to make space to insert the current item by moving larger items one position to the right , before inserting the current item into the vacated position.

把第一个元素当作以及排了序的序列，从第二个位置开始，把要插入的元素当作哨兵并且生成副本0号位，依次与已经排了序的序列的元素从后往前比较，大于哨兵便向后移动一格，直到找到第一个比相应元素小的，然后把哨兵放到该元素后面。

复杂度分析

时间

Insertion sort uses O ( n 4 / 2 ) O(n ^4/2) O(n4/2) compares and O ( n 4 / 2 ) O(n ^4/2) O(n4/2) exchanges to sort a randomly ordered array of length N with distinct keys , on the average.

The worst case is O ( n 2 / 2 ) O(n^2/2) O(n2/2) compares and the same exchanges and the best case is N-1compares and 0 exchanges.

空间

空间上在原址上 *** 作，为常数级别

伪代码

Insertion_sort(A)

      for j←2  to length[A]
               
             temp = A[j]
               
             i ←j-1
               
             while i>0 and A[i] > temp
               
                     A[i+1]←A[i]
               
                      i --
               
              A[i+1] = temp

代码c++实现

void insertsort(int A[],int n)
{
    int i=0;
   for(int j=2;j<=n;j//依次将A[2]~ A[N]插入前面已经排好的顺序序列
   {
      A[0]=A[j];//以A【0】来记录要排序的值,复制为哨兵，防止覆盖
      i=j-1;
      while(i>0&&A[i]>A[0])
         //从j-1开始往后挪，直到i对应的数比哨兵小，i+1位填上哨兵，排好了
      {
          A[i+1]=A[i];
          i--;
      }
       A[i+1]=A[0];
   }
}

实例化

#include 
using namespace std;

void insertsort(int A[],int n)
{
    int i=0;
   for(int j=2;j<=n;j++)
   {
      A[0]=A[j]; //以A【0】来记录要排序的值
      i=j-1;
      while(i>0&&A[i]>A[0])
      {
          A[i+1]=A[i];
          i--;
      }
       A[i+1]=A[0];
   }
}

int main()
{
	int n;
	cin>>n;
	int* A=new int[n+1];//0位作为标志位
	//i=0为空
	for (int i=1;i>A[i];
	}
	insertsort(A,n);
	for (int i=1;i原理 
 
 折半插入排序是在直接插入排序的在已经排好序的序列中找寻要排序的值应该要插入的位置时使用二分查找法，也就是减少了查找位置的时候的比较的次数，移动次数没有改变，是对插入排序的一种优化 
 
复杂度分析 
 
 时间 
 
compares is 
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        )
       
      
      
       O(nlog_2n)
      
     
    O(nlog2n) while exchanges is 
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2) so the whole is still 
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2) 
 
 空间 
 

    
     
      
       
        O
       
       
        (
       
       
        1
       
       
        )
       
      
      
       O(1)
      
     
    O(1) 
伪代码 
 for j <- 2 to length(A) do
   
   A[0] <- A[j];
   low <- 1;
   high <- j-1;
   
   while low<=high do 
     mid<- (low+high)/2;
     if A[mid]>A[0] then 
     high <-mid-1;
     else 
     low <-mid+1;
     end;
     
     for i<- j-1 to low do
     A[j+1]<-A[j];
     A[low]<-A[0];
     end
    
   end

 
代码c++实现 
void binaryinsertsort(int A[],int n)
{
    int i,j,low,mid,high;
    for(j=2;j<=n;j++)//依次将A[2]~ A[N]插入前面已经排好的顺序序列
    {
        A[0]=A[j];//复制为哨兵，防止覆盖
        low=1;high=j-1;
        while(low<=high)
      //得到high右边为low，其中high右边皆为大于A【0】的数，low左边都是小于等于A【0】的数
        {
            mid=(low+high)/2;
            if(A[mid]>A[0])high=mid-1;
            else low=mid+1;
        }
        for(i=j-1;i>=low;--i)A[i+1]=A[i];//把[low,i-1]都往后面移动一格
        A[low]=A[0];//赋值
    }
}


 
high 的右边都比目标大，low的左边都比目标小或者等于，插入在中间即是把 low往后面移动，插入到原来 low的位置上 
A[mid]==A[0]时，得让 low加 1使得该数字插入在A[mid]的右边来保证稳定性 
实例化 
#include 
using namespace std;

void binaryinsertsort(int A[],int n)
{
    int i,j,low,mid,high;
    for(j=2;j<=n;j++)//依次将A[2]~ A[N]插入前面已经排好的顺序序列
    {
        A[0]=A[j];//复制为哨兵，防止覆盖
        low=1;high=j-1;
        while(low<=high)
      //得到high右边为low，其中high右边皆为大于A【0】的数，low左边都是小于等于A【0】的数
        {
            mid=(low+high)/2;
            if(A[mid]>A[0])high=mid-1;
            else low=mid+1;
        }
        for(i=j-1;i>=low;--i)A[i+1]=A[i];//把[low,i-1]都往后面移动一格
        A[low]=A[0];//赋值
    }
}

int main()
{
	int n;
	cin>>n;
	int* A=new int[n+1];//0位作为标志位
	//i=0为空
	for (int i=1;i>A[i];
	}
	binaryinsertsort(A,n);
	for (int i=1;i原理 
 
 希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。 
 希尔排序又称缩小增量排序，它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法 
 的进行而减小，直到只比较相邻元素的最后一趟排序为止。 
 也就是先将待排序表分割成若千形如L[i,i+d,i+2d,…,i+kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止 
 
复杂度分析 
 
 时间 
 
和增量序列d的选择有关系，目前无法用数学手段证明确切的时间复杂度，最坏时间复杂度为
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2),当n在某个范围内时，时间复杂度可达
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         1.3
        
       
       
        )
       
      
      
       O(n^ {1.3})
      
     
    O(n1.3) 
 
 空间 
 

    
     
      
       
        O
       
       
        (
       
       
        1
       
       
        )
       
      
      
       O(1)
      
     
    O(1) 
伪代码 
for d<- length(A)/2 to 1 do
for i<-d+1 to n do
if A[i]0 do
A[j+d]=A[j];
j-=d;
end
A[j+d]=A[0];
end
end
end


 
代码c++实现 
void ShellSort(int A[],int n)
{
    int d,i,j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
     for(d=n/2;d>=1;d=d/2)//步长变化
     {
         for(i=d+1;i<=n;++i)
         {
             if(A[i]0&&A[0] 
实例化 
#include 
using namespace std;

void ShellSort(int A[],int n)
{
    int d,i,j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
     for(d=n/2;d>=1;d=d/2)//步长变化
     {
         for(i=d+1;i<=n;++i)
         {
             if(A[i]0&&A[0]>n;
	int* A=new int[n+1];//0位作为标志位
	//i=0为空
	for (int i=1;i>A[i];
	}
	ShellSort(A,n);
	for (int i=1;i根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置 
4. 冒泡排序 
原理 
 
 从前往后两两比较相邻元素的值，若为逆序则交换他们，直到序列比较完，这样子的一趟叫做冒泡排序，此时，序列的最大值已经确定位置，故下一趟冒泡，只需要到n-1位值即可，会使得第二大的元素归位 
 若其中的某一趟排序没有发生任何交换，说明该序列已经整体有序 
 
复杂度分析 
 
 时间 
 
the best case (array in order) uses n-1 compares and 0 exchanges so the whole is 
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n) 
while the worst case (array in reverse) uses 
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        /
       
       
        2
       
       
        )
       
      
      
       O(n^2/2)
      
     
    O(n2/2) compares and the same exchanges so the whole is 
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2) 
on the average ,the sort uses 
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2) 
and attention 每一次exchanges都会有三次的移动元素的次数 
 
 空间 
 

    
     
      
       
        O
       
       
        (
       
       
        1
       
       
        )
       
      
      
       O(1)
      
     
    O(1) 
伪代码 
for i<- 1 to n-1 do
flag = 0;
for j=1 to n-i do
if A[j+1] 
代码c++实现 
void swap(int&a,int&b)
{
    int temp=a;
    a=b;
    b=temp;
}

void BubbleSort(int A[],int n)
{
    for(int i=1;i实例化 
#include 
using namespace std;

void swap(int&a,int&b)
{
    int temp=a;
    a=b;
    b=temp;
}

void BubbleSort(int A[],int n)
{
    for(int i=1;in;
	int* A=new int[n+1];//0位作为标志位
	//i=0为空
	for (int i=1;i>A[i];
	}
	BubbleSort(A,n);
	for (int i=1;i原理 
 
 快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。快速排序和归并排序是互补的；归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也自然有序了。 
 算法思想：在待排序表[1…n]中任取一个元素pivot作为枢轴或者说是基准，通常是首元素，通过一趟排序将待排序表划分为独立的两个部分[1…k-1]和[k+1…n],使得[1…k-1]中元素都小于等于pivot，[k+1…n]都大于等于pivot，把pivot放到k位置上，这个过程为一次划分，确定了pivot的正确位置，然后对两个子表进行划分，直到每个部分仅有一个元素或为空。 
 
复杂度分析 
 
 时间 
 

    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        ∗
       
       
        (
       
       
        递
       
       
        归
       
       
        层
       
       
        数
       
       
        )
       
       
        )
       
      
      
       O(n*(递归层数))
      
     
    O(n∗(递归层数)) 每次递归进入Partition会进行不多于
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)的处理 
 
 空间 
 
这里的空间涉及到递归层数相关，
    
     
      
       
        O
       
       
        (
       
       
        递
       
       
        归
       
       
        层
       
       
        数
       
       
        )
       
      
      
       O(递归层数)
      
     
    O(递归层数) 
 
 分析递归层数 
 
在划分的时候和递归层数可以形象的转化成二叉树的层数来进行类比 
n个结点的二叉树，最小高度=
    
     
      
       
        (
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        )
       
       
        +
       
       
        1
       
      
      
       (log_2n) +1
      
     
    (log2n)+1,最大高度=n 
则时间复杂度 最好=
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        )
       
      
      
       O(nlog_2 n)
      
     
    O(nlog2n) 最坏=
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2) 
 空间复杂度 最好=
    
     
      
       
        O
       
       
        (
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        )
       
      
      
       O(log_2 n)
      
     
    O(log2n) 最坏=
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n) 
伪代码 
Partition(A,l,h) //l、h为数组下标
      p <= A[l]   //将第一个元素作为主元素
     while lp do --h
     end
     A[l]<=A[h];
     while l 
代码c++实现 
int Partition(int A[],int low,int high)
{
    int pivot=A[low];//第一个元素作为pivot
    while(low=pivot)--high;
        A[low]=A[high];//比pivot小的移动到左边
        while(low 
实例化 
#include 
using namespace std;

int Partition(int A[],int low,int high)
{
    int pivot=A[low];//第一个元素作为pivot
    while(low=pivot)--high;
        A[low]=A[high];//比pivot小的移动到左边
        while(low>n;
	int* A=new int[n+1];//0位作为标志位
	//i=0为空
	for (int i=1;i>A[i];
	}
	QuickSort(A,1,n);
	for (int i=1;i每一趟在待排序元素中选取关键字最小的元素加入有序子序列 
6. 简单选择排序 
原理 
 
 每一趟在待排序元素中选取关键字最小的元素加入有序子序列，n个元素需要n-1趟 
 
复杂度分析 
 
 时间 
 
无论什么顺序，都要进行
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        /
       
       
        2
       
       
        )
       
      
      
       O(n^2/2)
      
     
    O(n2/2)次的对比关键字 而元素的交换次数小于等于n-1次 
 
 空间 
 

    
     
      
       
        O
       
       
        (
       
       
        1
       
       
        )
       
      
      
       O(1)
      
     
    O(1) 
伪代码 
for i<- 1 to n-1 do
find min from A[i] to A[min]
exchange(A[i],A[min])
end
 
代码c++实现 
void swap(int&a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}
void SelectSort(int A[],int n)
{
    for(int i=1;i<=n-1;i++)
    {
        int min=i;
        for(int j=i+1;j<=n;j++)
        {
            if(A[j] 
实例化 
#include 
using namespace std;

void swap(int&a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}
void SelectSort(int A[],int n)
{
    for(int i=1;i<=n-1;i++)
    {
        int min=i;
        for(int j=i+1;j<=n;j++)
        {
            if(A[j]>n;
	int* A=new int[n+1];//0位作为标志位
	//i=0为空
	for (int i=1;i>A[i];
	}
	SelectSort(A,n);
	for (int i=1;i原理 
 
 L[i]>=L[2i]&&L[i]>=L[2i+1] 即根大于左右 
 非终端结点编号i<=n/2 
 利用大根堆的整理即可 
 
复杂度分析 
 
 时间 
 
建堆过程中，关键字的对比次数不超过4n，建堆时间复杂度=
    
     
      
       
        O
       
       
        （
       
       
        n
       
       
        ）
       
      
      
       O（n）
      
     
    O（n） 
然后每次把堆顶放到最后一个位置，对前面的再进行调整，这样进行n-1次，也就是排序的时间复杂度为
    
     
      
       
        O
       
       
        （
       
       
        n
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        ）
       
      
      
       O（nlog_2 n）
      
     
    O（nlog2n） 
则总的是
    
     
      
       
        O
       
       
        （
       
       
        n
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        ）
       
      
      
       O（nlog_2 n）
      
     
    O（nlog2n） 
 
 空间 
 

    
     
      
       
        O
       
       
        (
       
       
        1
       
       
        )
       
      
      
       O(1)
      
     
    O(1) 
伪代码 
 
代码c++实现 
void BuildMaxHeap(int A[],int len)
{
    for(int i=len/2;i>0;i--)
    HeadAdjust(A,i,len);
}
void HeapSort(int A[],int len)
{
    BuildMaxHeap(A,len);
    for(int i=len;i>1;i--)
    {
        swap(A[i],A[1]);
        HeadAdjust(A,1,i-1);
    }
}
void HeadAdjust(int A[],int k,int len)
{
    A[0]=A[k];
    for(int i=2*k;i<=len;i*=2)
    {
        if(i 
实例化 
#include 
using namespace std;

void BuildMaxHeap(int A[],int len)
{
    for(int i=len/2;i>0;i--)
    HeadAdjust(A,i,len);
}
void HeapSort(int A[],int len)
{
    BuildMaxHeap(A,len);
    for(int i=len;i>1;i--)
    {
        swap(A[i],A[1]);
        HeadAdjust(A,1,i-1);
    }
}
void HeadAdjust(int A[],int k,int len)
{
    A[0]=A[k];
    for(int i=2*k;i<=len;i*=2)
    {
        if(i>n;
	int* A=new int[n+1];//0位作为标志位
	//i=0为空
	for (int i=1;i>A[i];
	}
	HeapSort(A,n);
	for (int i=1;i原理 
 
复杂度分析 
 
 时间 
 
 
 空间 
 
伪代码 
 
代码c++实现 
 
实例化 
 
归并排序 
8. 二路归并排序 
原理 
 
 把两个已经有序的序列合并成一个 
 
复杂度分析 
2路归并的归并树实际上就是一棵形态倒立的二叉树 
 
 时间 
 
n个元素进行2路归并排序，归并趟数=上限（
    
     
      
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
      
      
       log_2 n
      
     
    log2n) ，每趟归并的时间复杂度为
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)，则算法的时间复杂度为
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        )
       
      
      
       O(nlog_2 n)
      
     
    O(nlog2n) 
 
 空间 
 

    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)来自于数组B，而递归深度
    
     
      
       
        O
       
       
        （
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        ）
       
      
      
       O（log_2 n）
      
     
    O（log2n）比较小，故为
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n) 
伪代码 
 
代码c++实现 
 
 递归版 
 
int *B=(int*)malloc(n*sizeof(int));//辅助数组B

//A[low...mid]和A[mid...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high)
{
    int i,j,k;
    for(k=low;k<=high;k++)
    B[k]=A[k];//将A中所有元素复制到B中
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)
    {
        if(B[i]<=B[j])A[k]=B[i++];//将较小值复制到A中
        else A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];
    while(j<=high)A[k++]=B[j++];
}

void MergeSort(int A[],int low,int high)
{
    if(low 
 
 迭代版 
 
void merge_sort(int arr[], int len) {
   int *a = arr;
    int *b = new int[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}
 
实例化 
#include 
using namespace std;
int n;
int *B=(int*)malloc(n*sizeof(int));//辅助数组B

//A[low...mid]和A[mid...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high)
{
    
    int i,j,k;
    for(k=low;k<=high;k++)
    B[k]=A[k];//将A中所有元素复制到B中
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)
    {
        if(B[i]<=B[j])A[k]=B[i++];//将较小值复制到A中
        else A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];
    while(j<=high)A[k++]=B[j++];
}

void MergeSort(int A[],int low,int high)
{
    if(low>n;
	int* A=new int[n+1];//0位作为标志位
	//i=0为空
	for (int i=1;i>A[i];
	}
	MergeSort(A,1,n);
	for (int i=1;i原理 
 
 把两个或多个已经有序的序列合并成一个 
 m路归并，每选出一个关键字需要对比关键字m-1次 
 
复杂度分析 
 
 时间 
 
 
 空间 
 
伪代码 
 
代码c++实现 
 
实例化 
 
非比较类算法 
10. 计数排序 
原理 
 
复杂度分析 
 
 时间 
 
 
 空间 
 
伪代码 
 
代码c++实现 
 
实例化 
 
11. 桶排序 
原理 
 
复杂度分析 
 
 时间 
 
 
 空间 
 
伪代码 
 
代码c++实现 
 
实例化 
 
12. 基数排序 
原理 
 
复杂度分析 
 
 时间 
 
 
 空间 
 
伪代码 
 
代码c++实现 
 
实例化 
 
制到B中
 for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)
 {
 if(B[i]<=B[j])A[k]=B[i++];//将较小值复制到A中
 else A[k]=B[j++];
 }
 while(i<=mid) A[k++]=B[i++];
 while(j<=high)A[k++]=B[j++];
 } 
void MergeSort(int A[],int low,int high)
 {
 if(low {
 int mid=(low+high)/2;
 MergeSort(A,low,mid);
 MergeSort(A,mid+1,high);
 Merge(A,low,mid,high);
 }
 }
 int main()
 { 
cin>>n;
int* A=new int[n+1];//0位作为标志位
//i=0为空
for (int i=1;i>A[i];
}
MergeSort(A,1,n);
for (int i=1;i 
} 


##### 9. 多路归并排序



原理

>把两个或多个已经有序的序列合并成一个
>
>m路归并，每选出一个关键字需要对比关键字m-1次

复杂度分析



> 时间



> 空间



伪代码

 


代码c++实现

```cpp

 
实例化 
 
非比较类算法 
10. 计数排序 
原理 
 
复杂度分析 
 
 时间 
 
 
 空间 
 
伪代码 
 
代码c++实现 
 
实例化 
 
11. 桶排序 
原理 
 
复杂度分析 
 
 时间 
 
 
 空间 
 
伪代码 
 
代码c++实现 
 
实例化 
 
12. 基数排序 
原理 
 
复杂度分析 
 
 时间 
 
 
 空间 
 
伪代码 
 
代码c++实现 
 
实例化 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: https://www.outofmemory.cn/zaji/5672852.html

排序算法新版（懒得继续

发表评论

评论列表（0条）