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

2024-01-08 21:21:00

算法复习

第二章 排序

判断有序的一些基本方法

//比较两个数大小的方法 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
//是对空间和时间最佳的,缺点内循环比快排长,缓存内存利用率低,不稳定

行为轨迹在这里插入图片描述

各个排序总结在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_61605995/article/details/135422966
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。