欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

十大排序算法(Java)

程序员文章站 2022-03-12 09:50:08
...

十大排序算法(Java)

小猴子自定义口诀(瞎编的,哈哈):冒泡两个两个对比,选择最大的排在最后,插入前面有序列表,归并先分区后合并,快速将一列数划分小于pivot在左边大于pivot在右边再依次递归左右子列,希尔分列排序每列排序算法借用插入;以上是基于比较的排序算法

以下不是基于比较的排序算法,(以空间换时间),计数计算每个数出现的次数然后从小到大排序,基数非常适合非负整数个十百分别比较,桶是把每个数分到相应的桶再排序

各个排序图片归纳:

十大排序算法(Java)

一、冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

//原始排序(无优化)
public void bubbleSort(Integer[] array){
  for(int end=array.length-1;end>0;end++){
    for(int begin=1;begin<=end;begin++){
      if(array[begin] < array[begin-1]){
        int temp = array[begin];
        array[begin] = array[begin-1];
        array[begin-1] = temp;
      }
    }
  }
}

//优化方案1(当数组完全有序或者数组在循环少量次数后就有序时)
public void bubbleSort1(Integer[] array){
  for(int end=array.length-1;end>0;end++){
    boolean sorted = true;
    for(int begin=1;begin<=end;begin++){
      if(array[begin] < array[begin-1]){
        int temp = array[begin];
        array[begin] = array[begin-1];
        array[begin-1] = temp;
        sorted = false;
      }
    }
    if(sorted){
      break;
    }
  }
}

//优化方案2(当数组中后面部分完全有序)
public void bubbleSort2(Integer[] array){
  for(int end=array.length-1;end>0;end++){
    //sortedIndex的初始值在数组完全有序的时候有用
    int sortedIndex = 1;
    for(int begin=1;begin<=end;begin++){
      if(array[begin] < array[begin-1]){
        int temp = array[begin];
        array[begin] = array[begin-1];
        array[begin-1] = temp;
        sortedIndex = begin;
      }
    }
    end = sortedIndex;
  }
}

二、选择排序(Selection Sort)

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

public void selectionSort(Integer[] arr){
   for(int end=arr.length-1;end>0;end++){
     int maxIndex = 0;
     for(int begin=1;begin<=end;begin++){
       if(arr[maxIndex] <= arr[begin]){ //增加其稳定性(=)
         maxIndex = begin;
       }
     }
     int temp = arr[maxIndex];
     arr[maxIndex] = arr[end];
     arr[end] = temp;
  }
}

三、堆排序(Heap Sort)

(可以看做对选择排序的优化)

堆排序(Heap-sort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

//重构代码,写一个父类,其他排序都继承这个抽象类,重写sort方法
public abstract class Sort{
  protected Integer[] arr;
  protected int cmpCount; //比较的次数 
  protected int swapCount; //交换的次数 
  private long time;
  
  public void sort(Integer[] arr){
    if(arr == null || arr.length < 2) return;
    this.arr = arr;
    long begin = System.currentTimeMillis();
    sort();
    time = System.currentTimeMillis() - begin;//运行时间
  }
  
  protected abstract void sort();
  
  //比较:等于0 arr[i] == arr[j]
  //小于0 arr[i] < arr[j]
  //大于0 arr[i] > arr[j]
  protected int cmp(int i,int j){
    cmpCount++;
    return arr[i] - arr[j];
  }
  
  //比较元素大小
  protected int compare(Integer v1,Integer v2){
    return v1 - v2;
  }
  
  //交换
  protected void swap(int i,int j){
    swapCount++;
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  
  @Override
  public String toString(){
    String string = getClass().getSimpleName()+" "+"耗时:"+(time/1000.0)+"s("+time+"ms)";
    return string;
  }
}
//注:上面两个排序的代码可重写,这里我就不写了
//交换堆顶元素与尾元素
//堆的元素数量减1
//对0位置进行1次shiftDown操作
public class HeapSort extends Sort{
  private int heapSize;
  
  @Override
  protected void sort(){
    heapSize = arr.length; 
    //原地建堆
    //heapSize>>1表示把heapSize右移1位,相当于heapSize/2
    for(int i = (heapSize >> 1)-1;i >= 0;i--){ 
      shiftDown(i);
    }
    
    while(heapSize > 1){
      //交换堆顶元素与尾元素
      //swap(0,heapSize-1);
      //heapSize--;
      swap(0,--heapSize);//合并以上两步
      
      //对0位置进行1次shiftDown操作(恢复堆的性质)
      shiftDown(0);
    }
  }
  
  private void shiftDown(int index){
    Integer element = arr[index];
    
    int half = heapSize >> 1;
    while(index < half){ //index必须是非叶子节点
      //默认是左边跟父节点比
      int childIndex = (index << 1)+1;
      Integer child = arr[childIndex];
      //右子节点比左子节点大
      int rightIndex = childIndex + 1;
      if(rightIndex < heapSize && compare(arr[rightIndex],child) > 0){
        child = arr[childIndex = rightIndex];
      }
      
      //大于等于子节点
      if(compare(element,child) >= 0) break;
      
      arr[index] = child;
      index = childIndex;
    }
    arr[index] = element;
  }
}

四、插入排序(Insertion Sort)

类似扑克牌的排序

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

public class InsertionSort extends Sort{
  
    @Override
    protected void sort(){
      for(int begin=1;begin<arr.length;begin++){
        int cur = begin;//要把当前begin记录下来,不能改变,所以用cur来代替begin变化
        while(cur > 0 && cmp(cur,cur-1) < 0){
           swap(cur,cur-1);
           cur--;
        }
      }
    }
  
  
  	//优化后的代码1
    @Override
    protected void sort(){
      for(int begin=1;begin<arr.length;begin++){
        int cur = begin;//要把当前begin记录下来,不能改变,所以用cur来代替begin变化
        Integer v = arr[cur];
        while(cur > 0 && cmp(cur,cur-1) < 0){
           arr[cur] = arr[cur-1]; //逐个往右移一个位置
           cur--;
        }
        arr[cur] = v; //最后前面空出来的那个位置,v直接插入进去
      }
    }  
  
  
  //利用二分搜索优化代码2(见下面方法search)
   @Override
    protected void sort(){
      for(int begin=1;begin<arr.length;begin++){
        int v = arr[begin];
        int searchIndex = search(begin);
        //将searchIndex到begin位置的元素往右边挪动一位
        //for(int i=begin-1;i>=searchIndex;i--){
        //  arr[i+1] = arr[i];
        //}
        for(int i=begin;i>searchIndex;i--){
          arr[i] = arr[i-1];
        }
        arr[searchIndex] = v;
      }
    }  
  //利用二分搜索找到index位置元素的待插入位置
  //已经排好序数组的区间范围值[0,index)
  private int search(int index){
    int v = arr[index];
    int begin = 0;
    int end = index-1; //左闭右开区间 
    while(begin < end){
      int mid = (begin+end) >>1;
      if(v <arr[mid]){ //compare(v,arr[mid])<0
        end = mid;
      }else{
        begin = mid+1;
      }
    }
    return begin;
  }
  
}


//写一下二分搜索(可参考学习)
public class BinarySearch{
  //查找v在有序数组array中的位置
  public static int indexOf(int[] array,int v){ //返回索引
    if(array == null ||array.length == 0){
      return -1;
    }
    int begin = 0;
    int end = array.length; //左闭右开区间 
    while(begin < end){
      int mid = (begin+end)/2;
      if(v<array[mid]){
        end=mid;
      }else if(v>array[mid]){
        begin=mid+1;
      }else{
        return mid;
      }
    }
    return -1;
  }
  
  //查找v在有序数组array中的插入位置,第一个比v大的位置的索引
  public static int search(int[] array,int v){
    if(array == null ||array.length == 0){
      return -1;
    }
    int begin = 0;
    int end = array.length; //左闭右开区间 
    while(begin < end){
      int mid = (begin+end) >>1;
      if(v <array[mid]){
        end = mid;
      }else{
        begin = mid+1;
      }
    }
    return begin;
  }
  
}

五、归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

public class MergeSort extends Sort{
  private Integer[] leftArray;
  
  @Override
  protected void sort(){
    leftArray = new Integer[arr.length >> 1];
    sort(0,arr.length);
  }
  
  //对[begin,end)范围内的数据进行归并排序
  private void sort(int begin,int end){
    if(end - begin < 2) return;//只有一个元素的情况
    int mid = (begin+end) >> 1;
    sort(begin,mid); //都是左闭右开区间
    sort(mid,end); //都是左闭右开区间
    merge(begin,mid,end);
  }
  
  //合并
  //将[begin,end)与[mid,end)范围内的序列合并成一个有序的序列
  private void merge(int begin,int mid,int end){
    int li = 0,le = mid -begin;
    int ri = mid,re = end;
    int ai = begin;
    
    //备份左边数组
    for(int i=li;i<le;i++){
      leftArray[i] = arr[begin+i];
    }
    
    while(li<le){ //如果左边还没有结束
      if(ri<re && leftArray[li] > arr[ri]){
        arr[ai] = arr[ri];
        ri++;
        ai++;
      }else{
        arr[ai++] = leftArray[li++];
      }
    }
  }
  
}

六、快速排序(Quick Sort)

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

/*快速排序的本质:
	逐渐将每一个元素都转换成轴点元素(递归的过程)*/

public class QuickSort extends Sort{

	@Override
    protected void sort(){
    	sort(0,arr.length);
    }
    
    //对[begin,end)范围的元素进行快速排序
    private void sort(int begin,int end){
    	if(end-begin<2) return;
    	
    	//确定轴点位置
    	int mid = pivotIndex(begin,end);
    	//对子序列进行快速排序
    	sort(begin,mid);
    	sort(mid+1,end);
    }
    //确定[begin,end)范围的轴点位置,return begin=end的位置pivot
    private int pivotIndex(int begin,int end){
    	//备份begin位置的元素
    	Integer v = arr[begin];  //arr[pivot] = v
    	//end指向最后一个元素
    	end--;
        while(begin < end){
          while(begin < end){
			if(arr[end] > v){
		    	end--;
            }else{
            	arr[begin] = arr[end];
            	begin++;
            	break; //只退出当前循环,掉头了(本来是从右到左查找对比,只要arr[end]<v了就掉头,从begin方向往end方向查找)
            }
          }
           while(begin < end){
			if(arr[begin] < v){
            	begin++;
            }else{
				arr[end] = arr[begin];
            	 end--;
            	 break;
            }
          }
        }
        //将轴点元素放入最终的位置
        arr[begin] = v;
        return begin;//或者end,因为begin=end=pivot轴点元素的位置
    }
}

七、希尔排序(Shell Sort)

1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

public class ShellSort extends Sort{
	
  
	@Override
    protected void sort(){
      List<Integer> stepSequence = myStepSequence(); //步长序列{8,4,2,1}	
      
      for(Integer step:stepSequence){
        sort(step);
      }
    }
  
  //分成step列进行排序
  private void sort(int step){
    //col:第几列   
    //对第col列进行排序
    for(int col = 0;col < step;col++){
      //col,col+step,col+2*step,col+3*step
      for(int begin=col+step;begin<arr.length;begin+=step){
        int cur = begin;//要把当前begin记录下来,不能改变,所以用cur来代替begin变化
        while(cur > 0 && cmp(cur,cur-step) < 0){
           swap(cur,cur-step);
           cur-=step;
        }
      }
    }
  }
  
  private List<Integer> myStepSequence(){
    List<Integer> stepSequence = new ArrayList<>();
    int step = arr.length;
    
    while((step >> 1) > 0){
      stepSequence.add(step);
    }
    return stepSequence;
  }
}

八、计数排序(Counting Sort)

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数

public class CountingSort extends Sort{
  @Override
    protected void sort(){
      //找出最大值
      int max = arr[0];
      for(int i=1;i<arr.length;i++){
        if(arr[i] > max){
          max = arr[i];
        }
      }
      
      //开辟内存空间,存储每个整数出现的次数
      int[] counts = new int[1+max];
      //统计每个整数出现的次数
      for(int i=0;i<arr.length;i++){
        counts[arr[i]]++;
      }
      
      //根据整数的出现次数,对整数进行排序
      int index=0;
      for(int i=0;i<counts.length;i++){
        while(conuts[i]-- >0){
          arr[index++] = i;
        }
      }
      
    }
}


//优化(内存浪费,无负数,不稳定)
public class CountingSort extends Sort{
  @Override
    protected void sort(){
      //找出最大值、最小值
        int max = arr[0];
        int min = arr[0];
        for(int i=1;i<arr.length;i++){
          if(arr[i] > max){
            max = arr[i];
        }
        for(int i=1;i<arr.length;i++){
          if(arr[i] < min){
            min = arr[i];
        }
        //开辟内存空间 存储次数
        int[] counts = new int[max-min+1];
        //统计每个整数出现的次数
        for(int i=0;i<arr.length;i++){
          counts[arr[i] - min]++;
        }
        //累加次数  
        for(int i=1;i<counts.length;i++){
          counts[i] += counts[i-1];
        }
        
        //从后往前遍历元素,将其放到有序数组中的合适位置
        int[] newArr = new int[arr.length];
        for(int i=arr.length;i>0;i--){
          //--counts[arr[i]-min] arr[i]-min就是这个数,counts[arr[i]-min]就是次数(前面次数和)要先减一才是新数组的索引
          newArr[--counts[arr[i]-min]] = arr[i]; //理解
        } 
        
        //将有序数组赋值到arr
        for(int i=0;i<arr.length;i++){
          arr[i]=newArr[i];
        }
          
     }
}

九、基数排序(Radix Sort)

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。(非常适合非负整数)

public class RadixSort extends Sort{
  @Override
    protected void sort(){
      //找出最大值
      int max = arr[0];
      for(int i=1;i<arr.length;i++){
        if(arr[i] > max){
          max = arr[i];
        }
      }
      
      //max=593  593%10=3  593/10%10=9 593/100%10=5
      for(int divider = 1;divider <= max;divider *= 10){
        countingSort(divider);
      }
      
    }
  
  //基于计数排序
  protected void countingSort(int divider){ //divider=1、10、100、1000、... 
        //开辟内存空间 存储次数
        int[] counts = new int[10];  //0-9
        //统计每个整数出现的次数
        for(int i=0;i<arr.length;i++){
          counts[arr[i] / divider % 10]++;
        }
        //累加次数  
        for(int i=1;i<counts.length;i++){
          counts[i] += counts[i-1];
        }
        
        //从后往前遍历元素,将其放到有序数组中的合适位置
        int[] newArr = new int[arr.length];
        for(int i=arr.length;i>0;i--){
          //--counts[arr[i]-min] arr[i]-min就是这个数,counts[arr[i]-min]就是次数(前面次数和)要先减一才是新数组的索引
          newArr[--counts[arr[i] / divider % 10] = arr[i]; //理解
        } 
        
        //将有序数组赋值到arr
        for(int i=0;i<arr.length;i++){
          arr[i]=newArr[i];
        }
          
     }
}

十、桶排序(Bucket Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。(当数是小数时)

public class BucketSort extends Sort{
  @Override
    protected void sort(){
      //桶数组
      List<Double>[] buckets = new List[arr.length];
      for(int i=0;i<arr.length;i++){
        int bucketIndex = (int) (arr[i] * arr.length);
        List<Double> bucket = buckets[bucketIndex];
        if(bucket == null){
          bucket = new LinkedList<>();
          buckets[bucketIndex] = bucket;
        }
        bucket.add(arr[i]);
      }
      
      //对每个桶进行排序
      int index = 0;
      for(int i=0;i<buckets;i++){
        if(buckets[i] == null) continue;
        buckets[i].sort(null);//java内部的排序方法
        for(Double d:buckets[i]){
          arr[index++] = d;
        }
      }
    }
}

扩展:十一、史上“最强”排序-休眠排序666(仅供参考,不要用!!)

private static class SortThread extends Thread{
  private int value;
  public SortThread(int value){
    this.value = value;
  }
  public void run(){
    try{
      Thread.sleep(value);
      System.out.println(value);
    }catch(IntereuptedException e){
      e.printStackTrace();
    }
  }
}

public class SortThreadTest{
  public static void main(String[] args){
    int[] array = [10,100,50,60,30];
    for(int i=0;i<array.length;i++){
      new SortThread(array[i]).start();
    }
  }
}

主要是理解某个算法本身的意义和思想,再根据代码联系思考。

这篇博客是自己在学习的时候跟着老师一起敲的,如有错误或不足之处还请多指教,以下是几个参考学习的链接。

可视化算法结构

前端JS实现十大排序算法可参见博文

学习视频bilibili

相关标签: Java面经题解