十大排序算法（Java）

深藏阁楼爱情的钟 2022-11-27 05:24 223阅读 0赞

### 文章目录 ###

*  十大排序算法（Java）
 *   *   *  一、冒泡排序（Bubble Sort）
         *  二、选择排序（Selection Sort）
         *  三、堆排序（Heap Sort）
         *  四、插入排序（Insertion Sort）
         *  五、归并排序（Merge Sort）
         *  六、快速排序（Quick Sort）
         *  七、希尔排序（Shell Sort）
         *  八、计数排序（Counting Sort）
         *  九、基数排序（Radix Sort）
         *  十、桶排序（Bucket Sort）
         *  扩展：十一、史上“最强”排序-休眠排序666（仅供参考，不要用！！）

# 十大排序算法（Java） #

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

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

各个排序图片归纳：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center]

### 一、冒泡排序（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);
        	sort2(0,arr.length-1);
        }
    
    	//对[begin,end)范围的元素进行快速排序
        private void sort2(int begin,int end){ 
        	if(end-begin<2) return;
        	
        	//确定轴点位置
        	int mid = partition(begin,end);
        	//对子序列进行快速排序
        	sort(begin,mid-1);
        	sort(mid+1,end);
        }
    	private int partition(int begin,int end){ 
    		int privot = begin,index = privot+1;
    		for(int i=index;i<=end;i++){ 
    			if(arr[privot] > arr[i]){ 
    				swap(i,index);
    				index++;
    			}
    		}
    		swap(privot,index-1);
    		return index-1;
    	}
    	private void swap(int a,int b){ 
    		int temp = arr[a];
    		arr[a] = arr[b];
    		arr[b] = temp;
    	}
        
        //对[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();
        }
      }
    }

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

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

[可视化算法结构][Link 1]

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

[学习视频bilibili][bilibili]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/f666a5db70b648c8857559831f42ca3b.png
[Link 1]: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[JS]: https://blog.csdn.net/xiaoxiaojie12321/article/details/81380834
[bilibili]: https://www.bilibili.com/video/BV1WK4y1b7Ee