排序算法汇总总结

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

一、插入排序

直接插入排序（Insertion Sort）的算法描写叙述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到对应位置并插入。插入排序在实现上，通常採用in-place排序（即仅仅需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，须要重复把已排序元素逐步向后挪位，为最新元素提供插入空间。

代码实现：

#include <stdio.h>
#include <stdlib.h>

void swap(int *p1, int *p2)
{
      int temp;
      temp=*p1;
      *p1=*p2;
      *p2=temp;
}

void insertSort(int *a,int len)
{
      int i,j;
      for(i=0;i<len;i++)
      {
          for(j=i+1;j>=1;j--)
          {
              if(a[j]<a[j-1])
                   swap(&a[j],&a[j-1]);              
          }
      }
}

希尔排序，也称递减增量排序算法，是插入排序的一种快速而稳定的改进版本号。它的基本思想是先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。全部距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1反复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即全部记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

代码实现：

#include <stdio.h>
#include <stdlib.h>

void swap(int *p1, int *p2)
{
      int temp;
      temp=*p1;
      *p1=*p2;
      *p2=temp;
}

void shell(int *a,int d,int len)
{
       int i,j;
       
       for(i=d+1;i<len;i++)
       {   
           for(j=i+d;j>=i && j<len;j--) 
           {
                 if(a[j]<a[j-d])
                      swap(&a[j],&a[j-d]);
            } 

        }
}

void shellSort(int *a,int d,int len)
{
       while(d>=1)
       {
            shell(a,d,len);
            d=d/2;
       }
}

二、交换排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它反复地走訪过要排序的数列，一次比較两个元素，假设他们的顺序错误就把他们交换过来。走訪数列的工作是反复地进行直到没有再须要交换，也就是说该数列已经排序完毕。这个算法的名字由来是由于越小的元素会经由交换慢慢“浮”到数列的顶端。

代码实现：(swap函数同前以后同)

void bubbleSort(int *a,int len)
{
        int i,j,change;

        for(i=0;i<len;i++)
        {
               change=0;
               for(j=len-1;j>i;j--)
               {
                        if(a[j]<a[j-1])
                        {
                                change=1;
                                swap(&a[j],&a[j-1]);
                         }
               } 
               if(!change)
                        break;
        }
}

高速排序是由东尼·霍尔所发展的一种排序算法基本思想是：通过一趟排序将要排序的数据切割成独立的两部分，当中一部分的全部数据都比另外一部分的全部数据都要小，然后再按此方法对这两部分数据分别进行高速排序，整个排序过程能够递归进行，以此达到整个数据变成有序序列。

代码实现：

int partition(int *a,int s,int e)
{
    int roll=a[s],i,j;

    for(i=s+1,j=i;i<=e;i++)
    {
        if(a[i]<roll)
        {
            swap(&a[i],&a[j]);
            j++;
        }
    }
    
    swap(&a[s],&a[j-1]);
    return j-1;
}

void quickSort(int *a, int start,int end)
{
    if(start<=end)
    {
         int split=partition(a,start,end);
         quickSort(a,start,split-1);
         quickSort(a,split+1,end);
    }
}

三、选择排序

直接选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理例如以下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾(眼下已被排序的序列)。以此类推，直到全部元素均排序完成。

代码实现：

void selectSort(int *a, int len)
{
     int i,j,min,mark;
   
     for(i=0;i<len;i++)
     {
        min=a[i];
        for(j=i+1;j<len;j++)
        {
             if(a[j]<min)
             {
                    min=a[j];
                    mark=j
             }
        }
        if(min!=a[i])
             swap(&a[i],&a[mark]);
     }
}

堆排序（Heapsort）是指利用堆这样的数据结构所设计的一种排序算法。堆是一个近似全然二叉树的结构，并同一时候满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点

代码实现：

void shift(int *a,int r,int len)
{
     int j,maxid;
     for(j=r;j<=len/2;)
     {
         maxid=j;
         if(2*j<len && a[2*j]>a[j])
              maxid=2*j;

         if(2*j+1<len && a[2*j+1]>a[maxid])
              maxid=2*j+1;
         
         if(maxid!=j)
         {
              swap(&a[maxid],&a[j]);
         }
     
     }
     
}


void buildHeap(int *a, int len)   //为廉价计算 a的下标从1開始 构建大顶堆
{
     int i;
     for(i=len/2;i>0;i--)
         shift(a,i,len);
}


void heapSort(int *a, int len)
{
     int clen;
     
     buildHeap(a,len);
     swap(&a[1],&a[len]);
     for(clen=len-1;clen>0;clen--)
     {
          shift(a,1,clen);
          swap(&a[1],&a[clen]);
     }
     
}

四、归并排序

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是採用分治法（Divide and Conquer）的一个很典型的应用。

算法描写叙述

归并操作的步骤例如以下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比較两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
反复步骤3直到某一指针达到序列尾
将还有一序列剩下的全部元素直接拷贝到合并序列尾

代码实现：

void merge(int *a,int start,int mid,int end)
{

     if(start>mid || mid >end ) return;

     int i=start,j=mid+1,k=0;
     int *L=(int *)malloc((end-start+1)*sizeof(int));
 
     while(i<=mid && j<=end)
     {
          if(a[i]<a[j])
          {
              L[k++]=a[i++];
          }else
          {
              L[k++]=a[j++];
          }
     }
       
     while(i<=mid)
          L[k++]=a[i++];

     while(j<=end)
          L[k++]=a[j++];


    for(i=start,j=0;i<=end;i++,j++)
    {
          a[i]=L[j];
    }
      
    free(L);
}

void mergeSort(int *a, int start,int end)
{
     if(start<end)
     {
          int mid=(start+end)/2;
          mergeSort(a,start,mid);
          mergeSort(a,mid+1,end);
          merge(a,start,mid,end);
     }
}

五、基数排序

基数排序(Radix sort)是一种非比較型整数排序算法，其原理是将整数按位数分割成不同的数字，然后按每一个位数分别比較。因为整数也能够表达字符串（比方名字或日期）和特定格式的浮点数，所以基数排序也不是仅仅能使用于整数。

算法实现（未验证正确性）：

struct DNode
{
     int data;
     DNode *next;
}

struct Table
{
     int id;
     DNode *fisrt;
}



int digit(int num,int loc)
{
     for(int i=1;i<loc;i++)
           num/=10;
     int res=num%10;

     return res;
}

int maxCount(int *a,int len)
{
    int max=0,n,num;
    for(int i=0;i<len;i++)
    { 
          n=0;
          num=a[i];
          while(num)
          {
             num/=10;
             n++;
          }
          if(n>max)  max=n;
    }
    return max;
}

void radixSort(int *a,int len)
{
     
     int maxloc=maxcount(a,len);
     DNode *ptemp;
     Table *t=(Table *)malloc(10 * sizeof(Table));

     for(int i=0;i<10;i++)
     {
            t[i]->id=i;
            t[i]->first=NULL;
     } 

     for(int j=1;j<maxcount;j++)
     {
            for(int k=0;k<len;k++)
            {
                   int idm=digit(a[k],j);
                   DNode *p=t[idm]->first;
                   while(pt->next!=NULL)  p=p->next;

                   DNode *d=(DNode *)malloc(sizeof(DNode));
                   d->data=a[k];
                   d->next=p->next;
                   p->next=d;
            }
            for(int i=0,k=0;i<=9;i++)
            {
                    while(t[i]->first!=NULL)
                    {
                         a[k--]=t[i]->first->data;
                         ptemp=t[i]->first;
                         t[i]->first=t[i]->first->next;
                         free(ptemp);
                    }
            }
     }
}

六、排序算法特点，算法复杂度和比較

直接插入排序

假设目标是把n个元素的序列升序排列，那么採用直接插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这样的情况下，须要进行的比較操作需(n-1)次就可以。最坏情况就是，序列是降序排列，那么此时须要进行的比較共同拥有n(n-1)/2次。直接插入排序的赋值操作是比較操作的次数减去(n-1)次。平均来说直接插入排序算法复杂度为O(n²)。因而，直接插入排序不适合对于数据量比較大的排序应用。可是，假设须要排序的数据量非常小，比如，量级小于千，那么直接插入排序还是一个不错的选择。插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为高速排序的补充，用于少量元素的排序（通常为8个或下面）。

希尔排序

希尔排序是基于插入排序的一种算法，在此算法基础之上添加�了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)，没有高速排序算法快
O(N*(logN))，因此中等大小规模表现良好，对规模很大的数据排序不是最优选择。可是比O(N2）复杂度的算法快得多。而且希尔排序很easy实现，算法代码短而简单。此外，希尔算法在最坏的情况下和平均情况下运行效率相差不是许多，与此同一时候高速排序在最坏的情况下运行的效率会很差。专家们提倡，差点儿不论什么排序工作在開始时都能够用希尔排序，若在实际使用中证明它不够快，再改成高速排序这样更高级的排序算法.

希尔排序是依照不同步长对元素进行插入排序，当刚開始元素非常无序的时候，步长最大，所以插入排序的元素个数非常少，速度非常快；当元素基本有序了，步长非常小，插入排序对于有序的序列效率非常高。所以，希尔排序的时间复杂度会比o(n^2)好一些。因为多次插入排序，我们知道一次插入排序是稳定的，不会改变同样元素的相对顺序，但在不同的插入排序过程中，同样的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的

冒泡排序

时间复杂度为O（n^2），尽管不及堆排序、高速排序的O（nlogn，底数为2），可是有两个长处：1.“编程复杂度”非常低，非常easy写出代码；2.具有稳定性。

当中若记录序列的初始状态为”正序”，则冒泡排序过程仅仅需进行一趟排序，在排序过程中仅仅需进行n-1次比較，且不移动记录；反之，若记录序列的初始状态为”逆序”，则需进行n(n-1）/2次比較和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

高速排序

在最好的情况，每次我们运行一次切割，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递回调用处理一半大小的数列。因此，在到达大小为一的数列前，我们仅仅要作 log n 次巢状的调用。这个意思就是调用树的深度是O(log n)。可是在同一阶层的两个程序调用中，不会处理到原来数列的同样部份；因此，程序调用的每一阶层总共所有仅须要O(n)的时间（每一个调用有某些共同的额外耗费，可是由于在每一阶层仅仅仅仅有O(n)个调用，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。

另外一个方法是为T(n)设立一个递回关系式，也就是须要排序大小为n的数列所须要的时间。在最好的情况下，由于一个单独的高速排序调用牵涉了O(n)的工作，加上对n/2大小之数列的两个递回调用，这个关系式能够是：

T(n) = O(n) + 2T(n/2)

解决这样的关系式型态的标准数学归纳法技巧告诉我们T(n) = O(n log n)。

其实，并不须要把数列如此精确地切割；即使假设每一个基准值将元素分开为 99% 在一边和 1% 在还有一边，调用的深度仍然限制在 100log n，所以所有运行时间依旧是O(n log n)。

然而，在最坏的情况是，两子数列拥有大各为 1 和 n-1，且调用树（call tree）变成为一个 n 个巢状（nested）呼叫的线性连串（chain）。第 i 次呼叫作了O(n-i)的工作量，且 $\sum_{i=0}^n (n-i) = O(n^2)$ 递回关系式为：

T(
n) = O(
n) + T(1) + T(
n – 1) = O(
n) + T(
n – 1)

这与插入排序和选择排序有同样的关系式，以及它被解为T(n) = O(n²)。

讨论平均复杂度情况下，即使假设我们无法随机地选择基准数值，对于它的输入之全部可能排列，高速排序仍然仅仅须要O(n log n)时间。由于这个平均是简单地将输入之全部可能排列的时间加总起来，除以n这个因子，相当于从输入之中选择一个随机的排列。当我们这样作，基准值本质上就是随机的，导致这个算法与乱数高速排序有一样的运行时间。

更精确地说，对于输入顺序之全部排列情形的平均比較次数，能够借由解出这个递回关系式能够精确地算出来。

$C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1)) = 2n \ln n = 1.39n \log_2 n.$

在这里，n-1 是切割所使用的比較次数。由于基准值是相当均匀地落在排列好的数列次序之不论什么地方，总和就是全部可能切割的平均。

这个意思是，平均上高速排序比理想的比較次数，也就是最好情况下，仅仅大约比較糟39%。这意味着，它比最坏情况较接近最好情况。这个高速的平均运行时间，是高速排序比其它排序算法有实际的优势之还有一个原因。

讨论空间复杂度时被高速排序所使用的空间，按照使用的版本号而定。使用原地（in-place）切割的高速排序版本号，在不论什么递回呼叫前，仅会使用固定的額外空間。然而，假设须要产生O(log n)巢状递回呼叫，它须要在他们每个储存一个固定数量的资讯。由于最好的情况最多须要O(log n)次的巢状递回呼叫，所以它须要O(log n)的空间。最坏情况下须要O(n)次巢状递回呼叫，因此须要O(n)的空间。

然而我们在这里省略一些小的细节。假设我们考虑排序随意非常长的数列，我们必须要记住我们的变量像是left和right，不再被觉得是占领固定的空间；也须要O(log n)对原来一个n项的数列作索引。由于我们在每个堆栈框架中都有像这些的变量，实际上高速排序在最好跟平均的情况下，须要O(log²n)空间的位元数，以及最坏情况下O(n log n)的空间。然而，这并不会太可怕，由于假设一个数列大部份都是不同的元素，那么数列本身也会占领O(nlog n)的空间字节。

非原地版本号的高速排序，在它的不论什么递回呼叫前须要使用O(n)空间。在最好的情况下，它的空间仍然限制在O(n)，由于递回的每一阶中，使用与上一次所使用最多空间的一半，且

$\sum_{i=0}^{\infty} \frac{n}{2^i} = 2n.$

它的最坏情况是非常恐怖的，须要

$\sum_{i=0}^n (n-i+1) = \Theta (n^2)$

空间，远比数列本身还多。假设这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，假设数列元素的大部份都是不同的，每个将会须要大约O(log n)为原来储存，导致最好情况是O(n log n)和最坏情况是O(n² log n)的空间需求。

直接选择排序

选择排序的交换操作介于0和(n-1)次之间。选择排序的比較操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。

比較次数O(n^2),比較次数与keyword的初始状态无关，总的比較次数N=(n-1)+(n-2)+…+1=n*(n-1)/2。交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。交换次数比冒泡排序少多了，因为交换所需CPU时间比比較所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

堆排序

堆排序的平均时间复杂度为Ｏ(nlogn)，空间复杂度为Ｏ(1)。

因为它在直接选择排序的基础上利用了比較结果形成。效率提高非常大。它完毕排序的总比较次数为Ｏ(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将须要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。

归并排序

归并排序是一种非就地排序，将须要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度不管是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。

基数排序

基数排序的时间复杂度是 O(k·n)，当中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n))，由于k的大小通常会受到 n 的影响。以排序n个不同整数来举例，假定这些整数以B为底，这样每位数都有B个不同的数字，k就一定不小于log_B(n)。由于有B个不同的数字，所以就须要B个不同的桶，在每一轮比較的时候都须要平均n·log₂(B) 次比較来把整数放到合适的桶中去，所以就有：

k 大于或等于 log_B(n)
每一轮(平均)须要 n·log₂(B) 次比較

所以，基数排序的平均时间T就是：

T ≥ log
_B(
n)·
n·log
₂(
B) = log
₂(
n)·log
_B(
2)·
n·log
₂(
B) = log
₂(n)·n·log
_B(2)·log
₂(
B) =
n·log
₂(
n)

所以和比較排序相似，基数排序须要的比較次数：T ≥ n·log₂(n)。故其时间复杂度为 Ω(n·log₂(n)) = Ω(n·log n) 。

七、不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可採用直接插入或直接选择排序。　

当记录规模较小时，直接插入排序较好；否则由于直接选择移动的记录数少于直接插入，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的高速排序为宜；

(3)若n较大，则应採用时间复杂度为O(nlgn)的排序方法：高速排序、堆排序或归并排序。　

高速排序是眼下基于比較的内部排序中被觉得是最好的方法，当待排序的keyword是随机分布时，高速排序的平均时间最短；　

堆排序所需的辅助空间少于高速排序，而且不会出现高速排序可能出现的最坏情况。这两种排序都是不稳定的。　

若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常能够将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。由于直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

(4)在基于比較的排序方法中，每次比較两个keyword的大小之后，只出现两种可能的转移，因此能够用一棵二叉树来描写叙述比較判定过程。　

当文件的n个keyword随机分布时，不论什么借助于”比較”的排序算法，至少须要O(nlgn)的时间。　

箱排序和基数排序仅仅需一步就会引起m种可能的转移，即把一个记录装入m个箱子之中的一个，因此在普通情况下，箱排序和基数排序可能在O(n)时间内完毕对n个记录的排序。可是，箱排序和基数排序仅仅适用于像字符串和整数这类有明显结构特征的keyword，而当keyword的取值范围属于某个无穷集合(比如实数型keyword)时，无法使用箱排序和基数排序，这时仅仅有借助于”比較”的方法来排序。　

若n非常大，记录的keyword位数较少且能够分解时，採用基数排序较好。尽管桶排序对keyword的结构无要求，但它也仅仅有在keyword是随机分布时才干使平均时间达到线性阶，否则为平方阶。同一时候要注意，箱、桶、基数这三种分配排序均假定了keyword若为数字时，则其值均是非负的，否则将其映射到箱(桶)号时，又要添加�对应的时间。

(5)有的语言(如Fortran，Cobol或Basic等)没有提供指针及递归，导致实现归并、高速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其他排序。

(6)本章给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，能够用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之降低记录的移动次数。但有的排序方法，如高速排序和堆排序，在链表上却难于实现，在这样的情况下，能够提取keyword建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交换R[i]和R[j]，则仅仅需交换t[i]和t[j]就可以；排序结束后，向量t就指示了记录之间的顺序关系：

R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key

若要求终于结果是：

R[0].key≤R[1].key≤…≤R[n-1].key

则能够在排序结束后，再按辅助表所规定的次序重排各记录，完毕这样的重排的时间是O(n)。

经常使用的排序算法的时间复杂度和空间复杂度

排序法	最差时间分析	平均时间复杂度	稳定度	空间复杂度
冒泡排序	O(n²)	O(n²)	稳定	O(1)
高速排序	O(n²)	O(n*log₂n)	不稳定	O(log₂n)~O(n)
选择排序	O(n²)	O(n²)	稳定	O(1)
二叉树排序	O(n²)	O(n*log₂n)	不一顶	O(n)
插入排序	O(n²)	O(n²)	稳定	O(1)
堆排序	O(n*log₂n)	O(n*log₂n)	不稳定	O(1)
希尔排序	O	O	不稳定	O(1)

1、时间复杂度
（1）时间频度一个算法运行所耗费的时间，从理论上是不能算出来的，必须上机运行測试才干知道。但我们不可能也没有必要对每一个算法都上机測试，仅仅需知道哪个算法花费的时间多，哪个算法花费的时间少就能够了。而且一个算法花费的时间与算法中语句的运行次数成正比例，哪个算法中语句运行次数多，它花费时间就多。一个算法中的语句运行次数称为语句频度或时间频度。记为T(n)。
（2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。普通情况下，算法中基本操作反复运行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句运行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不同样时，时间复杂度有可能同样，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度同样，都为O(n2)。按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的运行效率越低。 2、空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内运行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。
（3）渐进时间复杂度评价算法时间性能　　主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

2、类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也经常简称为空间复杂度。
空间复杂度(Space Complexity)是对一个算法在执行过程中暂时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包含存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在执行过程中暂时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过參数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在执行过程中暂时占用的存储空间随算法的不同而异，有的算法仅仅须要占用少量的暂时工作单元，并且不随问题规模的大小而改变，我们称这样的算法是“就地/”进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法须要占用的暂时工作单元数与解决这个问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，比如将在第九章介绍的高速排序和归并排序算法就属于这样的情况。

如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形參为数组，则仅仅须要为它分配一个存储由实參传送来的一个地址指针的空间，即一个机器字长空间；若形參为引用方式，则也仅仅须要为其分配存储一个地址的空间，用它来存储相应实參变量的地址，以便由系统自己主动引用实參变量。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/118672.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权正版激活】： 官方授权正版激活支持Jetbrains家族下所有IDE 使用个人JB账号...