西电计科算法分析与设计第二章排序

算法复习

第二章 排序

判断有序的一些基本方法

//比较两个数大小的方法 v是否小于w
private static boolean less(Comparable v,Comparable w){//Comparable 是各种比较类型的通用类
//(int,char,double,float各种类型的综合类)
  return v.compare(w)<0;
  //compare方法：v<w return -1; v==w return 0; v>w return 1;
}

//交换数组中两个数的方法
private static void exch(Comparable[] a,int i,int j){
  Comparable temp=a[i];
  a[i]=a[j];
  a[j]=temp;
}
//判断该数组是否有序的方法
private static boolean isSorted(Comparable[] a){
  int N=a.length;
  for(int i=1;i<N;i++)
    if(less(a[i],a[i-1])) return false;
  return true;
}

选择排序（selection sort）

//思路：每次选择一个最小的插入到前面去，这样下来就有序
public class SelectionSort{
  public static void sort(Comparable[] a){
    int N=a.length;
    for(int i=0;i<N;i++){
      int min=i;//min是最小元素的下标
      for(int j=i+1;j<N;j++)
        if(less(a[j],a[min])) min=j;//找到当前最小的元素
      exch(a,i,min);//将元素放到其对应位置
    }
  }
}
//复杂度分析：比较次数为0+1+2+3+4...+N-1=(N-1)*N*(1/2)~(N^2)/2
//交换次数 N次
//稳定性：not stable

行为轨迹

插入排序(insertion sort)

//思路：扑克牌原理从左到右扫面，每回将第i个元素元前面i-1的元素比较，将其放在合适的位置
public class InsertionSort{
  public static void sort(Comparable[] a){
    int N=a.length;
    for(int i=0;i<N;i++)
      for(int j=i;j>0;j--)
        if(less(a[j],a[j-1])) exch(a,j,j-1);//排序时第i个位置前面的元素已经是有序的
        else break;//所以只需要跳过大于它的元素，即是其对应位置.不需要判断（a[j]<a[j+1]&&a[j]>a[j-1])
  }
}
//复杂度分析：比较的次数和交换的次数均与原数组的顺序有关，但其平均比较次数和交换次数为～(N^2)/4
//最坏情况：数组是按降序排列好的 则其平均比较次数和交换次数～(N^2)/2
//稳定性：stable

行为轨迹

归并排序(merge-sort)

1. 自顶向下

   //merge操作思路：两个数组（也可以是一个数组左右两部分均有序）合并成一个，两个数组的开头各一个指针，判断两指针元素大小
   //小的放到新数组aux里，其指针向后移动一位，再继续比较，直到两个数组合并成一个
   public static void merge(Comparable[] a,Comparable[] aux,int lo,int mid,int hi){
     //a数组分为两部分 左右两边各有序 以mid为中间点
     assert isSorted(a,lo,mid);//断言，确保mid左边的数全部有序
     assert isSorted(a,mid+1,hi);//确保mid右边的数全部有序
     //先将原数组复制到aux中，通过aux数组来改变a数组达到a数组merge的操作
     for(int k=lo;k<=hi;k++)
       aux[k++]=a[k++];
     //开始归并，定义两个指针
     int i=lo,j=mid+1;
     for(int k=0;k<hi;k++){
       //先处理两种极端情况 第一种、i指针所对应的全部元素已经放到a中去了，j指针有一部分没有放到a中去
       //第二种、与第一种情况相反
       if(i>mid) a[k]=aux[j++];
       else if(j>hi) a[k]=aux[i++];
       else if(less(aux[i],aux[j])) a[k]=aux[i++];//正常情况的判断
       else a[k]=aux[j++];
     }
     assert isSorted(a,lo,hi);
   }
   
   
   //整体归并排序思路：将一个数组左右分为两部分，不断拆分成两个数组，直到每个数组只有一个元素，然后进行merge操作
   //代码实现
   public static void sort(Comparable[] a,Comparable[] aux,int lo,int hi)
   {
     if(lo>=hi) return;//先判断结束拆分的条件
     int mid=(lo+hi)/2;
     sort(a,aux,lo,mid);
     sort(a,aux,mid+1,hi);
     merge(a,aux,lo,mid,hi);
   }
   
   public static void sort(Comparable[] a){
     Comparable aux=new Comparable[a.length];
     sort(a,aux,0,a.length);
   }
   //复杂度分析：自顶向下每次都是分为一半一半，所以是lgN,每次merge操作都是N(2*(N/2),4*(N/4),8*(N/8)...即每个状态下的复杂度都是N)
   //所以其时间复杂度为～NlgN，其用到了额外空间aux 所以其空间复杂度也不为常数
   //稳定性：stable
   

   自顶向下其行为轨迹

   

2. 自底向上

   //思路 从最底下往上开始归并，与自顶向下刚好相反（从最底下开始两两merge）
   public static void sort(Comparable[] a){
     int N=a.length;
     for(int size=1;size<N;size+=size)//从最底部开始
       for(int lo=0;lo<N-1;lo=size+size){
         merge(a,aux,lo,lo+size-1,Math.min(N-1,lo+size+size-1));
       }
   }
   

   轨迹
   

快速排序（quick-sort）

//思路先找一个基准，一般以第一个为主，也可以随机一个基准
//设置两个指针，i是数组最左边的指针，j是最右边的指针
//从右边找小于该基准的值，找到后停止
//从最左边找到大于该基准的值，找到后停止
//两个指针的值交换
//i，j继续上述行为，直到i>=j则为止，则找到基准在数组中的位置，它的左边全是小于它的，右边全是大于它的
public static int partition(Comparable[] a,int lo,int hi)
{
  int i=lo+1,j=hi;//以第一个元素为基准，找其在数组中的位置
  while(true){
    while(less(a[lo],a[i++]))
      if(i==hi) break;
    while(less(a[j--],a[lo]))
      if(j==lo) break;
    if(i>=j) break;
    exch(a,i,j);//交换a[i]和a[j] 小于的放到左边，大于的放到右边
  }
  exch(a,lo,j);//j为a[lo]在数组对应位置，左边全部小于a[lo],右边全部大于a[lo]
  return j;//返回对应位置
}

//总思路 确定a[lo]的位置j后，对其左边的元素在进行partition操作，右边的也进行partition操作
//这样每个元素都可以在其对应位置上
public static void sort(Comparable[] a,int lo,int hi){
  if(hi<=lo) return;//递归终止条件
  int j=partiton(a,lo,hi);
  sort(a,lo,j-1);
  sort(a,j+1,hi);
}

public static void sort(Comparable[] a){
  Std.Random.shuffle(a);//随机打乱该数组，方便后面排序，避免最坏情况
  sort(a,0,a.length-1);
}
//平均复杂度分析 每次拆分成j左右两边，则一共拆lgN次，共有N个元素操作计算后最终平均复杂度为~2NlgN
//最坏情况 数组已经有序 ～N^2/2 最好情况NlgN 平均2NlgN
//比mergesort快的原因，没有用额外的空间
//not stable



//quick-select选择出在一个数组中第k个大小的元素
//partition下的二分查找
public static Comparable select(Comparable[] a,int k){
  int lo=0,hi=a.length-1;
  while(lo<=hi){
    int j=partition(a,lo,hi);
    if(j>k) hi=j-1;
    else if(j<k) lo=j+1;
    else return a[k];
  }
  return a[k];
}

运行轨迹：

三路快排序（three-way quick sort)

三路快拍是提升普通快速排序中与基准元素相同过多元素的情况，加快其效率。

//思路 ：需要一个指针，从左往右扫描，设置两个边界，当元素小于基准元素v时，将其放在lt左边，大于时，放在gt的右边
//每次找的是与基准元素相同的，找完之后再基准元素左右两边再进行该操作到结束
//代码：
public static void sort(Comparable[] a,int lo,int hi){
  if(hi<=lo) return;
  //从左往右扫描的指针
  int i=lo;
  int lt=lo,gt=hi;
  Comparable v=a[lo];//基准作为比较值
  while(i<=gt){
    int cmt=a[i].compare(v);
    if(cmt<0) exch(a,lt++,i++);
    else if(cmt>0) exch(a,i,gt--);
    else i++;//与基准元素相等
  }
  sort(a,lo,lt-1);
  sort(a,gt+1,hi);
}

轨迹图

优先队列

以二叉堆的形式实现优先队列，主要是以大根堆的形式，叶子节点的值均比其父节点的值小

由图中可以看到，第k个节点的父节点为k/2，第k个节点的子节点为2k和2k+1

//为了消除不和大根堆概念的一些操作以及队列中插入和删除操作
//交换操作
private void exch(int i,int j){
  Key temp=pq[i];
  pq[i]=pq[j];
  pq[j]=temp;
}
//比较操作
private boolean less(int i,int k){//若要实现小根堆则改该操作为greater()
  return pq[i].compare(pq[j])<0;
}
//是否为空
public boolean isEmpty(){
  return N==0;
}
//1、子节点比父节点大
private void swim(int k)//子节点比父节点大，需要上浮操作
{
  while(k>1&&less(k/2,k)){//子节点比父节点大
    exch(k,k/2);
    k=k/2;
  }//~lgN
}
//向队列中添加元素
public void insert(Key x){//Key 为数据通用类，类比上面的Comparable
  pq[++N]=x;//N为后一个元素的位置
  swim(N);//添加元素至末尾，然后上浮
}
//2、父节点比子节点小
private void sink(int k)//父节点比子节点小，则需要下沉操作
{
  while(2*k<=N){
    //先去找到其子节点中最大的，然后父节点与子节点中较大的进行交换
    int j=2*k;
    if(less(j,j+1)) j++;//选择子节点中较大的
    if(!less(k,j)) break;
    exch(k,j);
    k=j;
  }//~lgN
}
//删除最大的元素 即根节点元素 
//思路：将最大的元素与最末尾的元素交换位置，N--，然后对根节点sink操作
public Key delMax()
{
  Key max=pq[1];//0号位置一直是空的，1号是根节点见上述图
  exch(1,N--);//N减的原因是下面要sink，否则sink后最大元素会被带进来
  sink(1);
  pq[N++]=null;
  return max;
}

//总实现代码，不过多解释
public class MaxPQ<Key extends Comparable<Key>>
{
  private Key[] pq;
  private int N;
  
  //初始化
  public MaxPQ(int capcity){
    pq=new Key[capcity];
  }
  public boolean isEmpty(){
    return N==0;
  }
  public void insert(Key x){
    pq[N++]=x;
    swim(N);
  }
  public Key delMax(){
    Key max=pa[1];
    exch(1,N--);
    sink(N);
    pq[N++]=null;
    return max;
  }
  private void swim(int k){
    while(k>1&&less(k/2,k)){
      exch(k/2,k);
      k=k/2;
    }
  }
  private void sink(int k){
    while(2*k<=N){
      int j=2*k;
      if(less(j,j+1)) j++;
      if(!less(j,k)) break;
      exch(j,k);
      k=j;
    }
  }
  private boolean less(int i,int j){
    return pq[i].compare(pa[j])<0;
  }
  private void exch(int i,int j){
    Key temp=pq[i];
    pq[i]=pq[j];
    pq[j]=temp;
  }
}

堆排序（heapsort）

思路：建立根堆后每次将根节点（最大元素）移动到后面，这样不断移动后就是排好序的堆

//实现代码
public class Heap{
  public static void sort(Comparable[ ] a){
    int N=a.length;
    //先建立大根堆,方法：从第一个非叶子节点开始，sink下沉操作（将叶子节点与父节点对比，选择大的放大父节点）
    //不断重复至根节点
    for(int k=N/2;k>=1;i--){
      sink(a,k,N);//下沉操作 数组a的第k个元素
    }
    //开始排序
    while(N>1){
      exch(a,1,N--);//交换后N向前移动一位以接受下一个最大元素
      sink(a,1,N);  
    }
    //～2NlgN
    //not stable
  }
  public static void sink(Comparable[] a,int k,int N){
    while(2*k<=N){
      int j=2*k;
      if(less(a,j,j+1)) j++;
      if(!less(a,k,j)) break;
      exch(a,k,j);
      k=j;
    }
  }
  public static boolean less(Comparable[] a,int i,int j){
    return a[i].compare(a[j])<0;
  }
  public static void exch(Comparable[] a,int i,int j){
    Comparable temp=a[i];
    a[i]=a[j];
    a[j]=temp;
  }
}
//相较于mergesort其不用花费额外线性空间，相较于quicksort其最坏也是NlgN
//是对空间和时间最佳的，缺点内循环比快排长，缓存内存利用率低，不稳定

行为轨迹

各个排序总结