顺序表和链式表的比较

为什么链式表插入或删除操作比顺序表效率高？时间复杂度不都是O（n）吗？链式表在插入或删除的时候不是要先移动指针找到位置吗？

寻找的时候的确都是O(n)，但是链表的插入和删除只需要更改几个指针的指向，而顺序表的话，插入和删除要移动大量元素，比如你要在长度为10万的顺序表中的第五万个位置插入一个元素，那么后面5万个元素就要一个个地后移，才能腾出位置给新元素。顺序表删除元素也是要对大量元素进行移动操作

• 你可以看下这个问题的回答https://ask.csdn.net/questions/690440
• 你也可以参考下这篇文章：冒泡排序的最优时间复杂度为什么是O(n)
• 除此之外, 这篇博客: 9大排序实现以及各自特点中的 时间复杂度为O(n) 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• /**
   * 计数排序，时间复杂度O(n),空间复杂度O(m)
   * 稳定排序
   * @author weifucheng
   *
   */
  public class CountingSort {
      public int[] countingSort(int[] A, int n) {
          int max=A[0];
          for(int i=0;i<n;i++){
              if(max<A[i]) max=A[i]; 
          }
          int min=A[0];
          for(int i=0;i<n;i++){
              if(min>A[i]) min=A[i]; 
          }
          int c=max-min+1;
          int[] t=new int[c];
          for(int i=0;i<n;i++){
              t[A[i]-min]++;
          }
          int j=0;
          for(int i=0;i<c;i++){
              while(t[i]>0){
                  A[j]=min+i;
                  t[i]--;
                  j++;
              }
          }
          return A;
      }
  }
  

  /**
   * 基数排序，时间复杂度为O(n),空间复杂度为O(m)
   * 稳定排序
   * @author weifucheng
   *
   */
  public class RadixSort {
      public int[] radixSort(int[] A, int n) {
          if(null==A ||n<2) return A;
          int[] bucket=new int[n];
          int[] count=new int[10];
          for(int i=1;i<=4;i++){
              for(int j=0;j<10;j++){
                  count[j]=0;
              }
              for(int j=0;j<n;j++){
                 count[getNum(A[j],i)]++;
              }
              for(int k=1;k<10;k++){
                  count[k]=count[k]+count[k-1];
              }
              for(int m=n-1;m>=0;m--){
                  int num=getNum(A[m],i);
                  bucket[count[num]-1]=A[m];
                  count[num]--;
              }
              for(int c=0;c<n;c++){
                  A[c]=bucket[c];
              }
  
          }
          return A;
      }
      private int getNum(int x,int d){
          int[] a={1,1,10,100,1000};
          return (x/a[d]%10);
      }
  }
  

链式表插入、删除时:
查找复杂度O（n） （寻址操作）
执行插入、删除操作 O（1）

顺序表插入、删除时：
查找复杂度O（1）
执行插入、删除操作 O（n） （拷贝操作）

拷贝是比寻址费时间的。（不难理解，拷贝操作当中的一部分就是寻址操作）