Java 常用 8 大排序算法图解与源码实现

季宁

发布时间：2026-10-14| 5人浏览过

原创

在 Java 开发中，掌握常见的排序算法对于提升程序性能和解决数据处理问题至关重要。本文详细解析了八种主流排序算法的实现逻辑与核心代码，包括直接插入、希尔、简单选择、堆排序、冒泡、快速、归并和基数排序。

算法分类与特性概览

排序算法通常按比较策略分为五类：插入排序（直接插入、希尔）、交换排序（冒泡、快速）、选择排序（简单选择、堆）、归并排序和分配排序（基数）。不同算法在时间复杂度、空间复杂度和稳定性上各有优劣：

平均速度最快：快速排序。
辅助空间需求：归并排序最多，堆排序最少。
不稳定的排序：快速排序、希尔排序、堆排序。

这八种算法的关系与层级结构可参考下图：

插入类排序：直接插入与希尔排序

第 1 步：直接插入排序

基本思想：将待排序数组视为两部分，前半部分已有序。从第二个元素开始，将其逐个与前一个元素比较，若顺序相反则向后移动已有序元素，直到找到合适位置插入。

Java 实现要点：使用外层循环控制遍历次数，内层循环负责寻找插入位置并移动元素。当 `temp`（当前元素）小于前一个元素时，发生移位操作。

package com.njue;
 
publicclass insertSort {
 
public insertSort() {
 int a[] = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
 int temp=0;
 for(int i=1;i<a.length;i++) {
  int j=i-1;
  temp=a[i];
  for(;j>=0&&temp<a[j];j--) {
   a[j+1]=a[j]; //将大于temp的值整体后移一个单位
  }
  a[j+1]=temp;
 }
 
 for(int i=0;i<a.length;i++) {
  System.out.println(a[i]);
 }
}

执行实例示意：

第 2 步：希尔排序（最小增量排序）

基本思想：是直接插入排序的改进版。先将整个待排元素序列分割成若干子序列分别进行直接插入排序，待整个序列中的元素“基本有序”时，再对全体元素进行一次直接插入排序。增量 `d` 从 `n/2` 开始，每次减半，直到 `d=1`。

Java 实现要点：通过 `Math.ceil(d1/2)` 计算增量，分 `d` 组进行插入排序，直到增量为 1 结束。

publicclass shellSort {
 
publicshellSort() {
 
 int a[]={1,54,6,3,78,34,12,45,56,100};
 double d1=a.length;
 int temp=0;
 
 while(true) {
  d1= Math.ceil(d1/2);
  int d=(int) d1;
  for(int x=0;x<d;x++) {
 
   for(int i=x+d;i<a.length;i+=d) {
   int j=i-d;
   temp=a[i];
   for(;j>=0&&temp<a[j];j-=d) {
    a[j+d]=a[j];
   }
   a[j+d]=temp;
   }
  }
 
  if(d==1) {
   break;
  }
 
  for(int i=0;i<a.length;i++) {
  System.out.println(a[i]);
  }
}

执行实例示意：

选择类排序：简单选择与堆排序

第 3 步：简单选择排序

基本思想：第一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，然后放到已排序序列的末尾。

Java 实现要点：外层循环确定位置，内层循环遍历剩余元素找出最小值索引 `position`，最后交换当前位置与最小值的位置。

public class selectSort {
 public selectSort() {
  int a[]={1,54,6,3,78,34,12,45};
  int position=0;
  for(int i=0;i<a.length;i++) {
   int j=i+1;
   position=i;
   int temp=a[i];
   for(;j<a.length;j++) {
    if(a[j]<temp) {
     temp=a[j];
     position=j;
    }
   }
   a[position]=a[i];
   a[i]=temp;
  }
 
  for(int i=0;i<a.length;i++)
   System.out.println(a[i]);
 }
}

执行实例示意：

第 4 步：堆排序

基本思想：利用堆这种数据结构设计的一种排序算法。建堆的过程是将数组看作完全二叉树，调整为大顶堆（父节点大于等于子节点）。将堆顶元素（最大值）与末尾元素交换，然后重新调整堆顶，重复此过程直到所有元素有序。

Java 实现要点：包含 heapSort、buildMaxHeap 和 swap 三个关键函数。buildMaxHeap 从最后一个非叶子节点开始向上调整。

import java.util.Arrays;
 
publicclass HeapSort {
 inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
 public HeapSort() {
  heapSort(a);
 }
 
 public void heapSort(int[] a) {
  System.out.println("开始排序");
  int arrayLength=a.length;
  //循环建堆
  for(int i=0;i<arrayLength-1;i++) {
   //建堆
   buildMaxHeap(a,arrayLength-1-i);
   //交换堆顶和最后一个元素
   swap(a,0,arrayLength-1-i);
   System.out.println(Arrays.toString(a));
  }
 }
 
 
 
 private void swap(int[] data, int i, int j) {
  int tmp=data[i];
  data[i]=data[j];
  data[j]=tmp;
 }
 
 //对data数组从0到lastIndex建大顶堆
 privatevoid buildMaxHeap(int[] data, int lastIndex) {
  //从lastIndex处节点（最后一个节点）的父节点开始
 
  for(int i=(lastIndex-1)/2;i>=0;i--) {
   //k保存正在判断的节点
   int k=i;
   //如果当前k节点的子节点存在
   while(k*2+1<=lastIndex) {
    //k节点的左子节点的索引
    int biggerIndex=2*k+1;
    //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
    if(biggerIndex<lastIndex) {
     //若果右子节点的值较大
     if(data[biggerIndex]<data[biggerIndex+1]) {
      //biggerIndex总是记录较大子节点的索引
      biggerIndex++;
     }
    }
 
    //如果k节点的值小于其较大的子节点的值
    if(data[k]<data[biggerIndex]) {
     //交换他们
     swap(data,k,biggerIndex);
     //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
     k=biggerIndex;
    }else {
     break;
    }
   }
  }
 }
}

建堆与交换示意：

交换类排序：冒泡排序与快速排序

第 5 步：冒泡排序

基本思想：重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

Java 实现要点：双重循环，外层控制趟数，内层进行比较和相邻元素交换。每趟结束后，最大的元素会“沉”到最后。

public class bubbleSort {
 
publicbubbleSort() {
 inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
 int temp=0;
 for(int i=0;i<a.length-1;i++) {
  for(int j=0;j<a.length-1-i;j++) {
   if(a[j]>a[j+1]) {
    temp=a[j];
    a[j]=a[j+1];
    a[j+1]=temp;
   }
  }
 }
 
 for(int i=0;i<a.length;i++) {
  System.out.println(a[i]);
 }
}

执行实例示意：

第 6 步：快速排序

基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。关键是选择基准元素（pivot）并分区。

Java 实现要点：getMiddle 方法负责分区，返回基准元素的最终位置；_quickSort 递归调用处理左右两个子区间。

publicclass quickSort {
 inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
publicquickSort() {
 quick(a);
 for(int i=0;i<a.length;i++) {
  System.out.println(a[i]);
 }
}
 publicint getMiddle(int[] list, int low, int high) {
  int tmp =list[low]; //数组的第一个作为中轴
  while (low < high){
   while (low < high&& list[high] >= tmp) {
    high--;
   }
 
   list[low] =list[high]; //比中轴小的记录移到低端
   while (low < high&& list[low] <= tmp) {
    low++;
   }
 
   list[high] =list[low]; //比中轴大的记录移到高端
  }
  list[low] = tmp;  //中轴记录到尾
  return low;   //返回中轴的位置
 }
 
publicvoid _quickSort(int[] list, int low, int high) {
  if (low < high){
   int middle =getMiddle(list, low, high); //将list数组进行一分为二
   _quickSort(list, low, middle - 1); //对低字表进行递归排序
   _quickSort(list,middle + 1, high); //对高字表进行递归排序
  }
}
 
publicvoid quick(int[] a2) {
  if (a2.length > 0) {
   _quickSort(a2,0, a2.length - 1);
  }
}
}

分区过程示意：

归并排序与基数排序

第 7 步：归并排序

基本思想：采用分治法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。

Java 实现要点：sort 递归拆分区间直到长度为 1；merge 将两个有序子区间合并为一个新有序区间，需借助临时数组。

import java.util.Arrays;
 
publicclass mergingSort {
 
inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
 
publicmergingSort() {
 sort(a,0,a.length-1);
 for(int i=0;i<a.length;i++)
  System.out.println(a[i]);
}
 
publicvoid sort(int[] data, int left, int right) {
 if(left<right){
  int center=(left+right)/2;
  sort(data,left,center);
  sort(data,center+1,right);
  merge(data,left,center,right);
 }
 
}
 
publicvoid merge(int[] data, int left, int center, int right) {
 int [] tmpArr=newint[data.length];
 int mid=center+1;
 int third=left;
 int tmp=left;
 while(left<=center&&mid<=right){
  if(data[left]<=data[mid]){
   tmpArr[third++]=data[left++];
  }else{
   tmpArr[third++]=data[mid++];
  }
 }
 
 while(mid<=right){
  tmpArr[third++]=data[mid++];
 }
 
 while(left<=center){
  tmpArr[third++]=data[left++];
 }
 
 while(tmp<=right){
  data[tmp]=tmpArr[tmp++];
 }
 System.out.println(Arrays.toString(data));
}
}

合并过程示意：

第 8 步：基数排序

基本思想：一种非比较型整数排序算法。将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。从最低位开始，依次进行一次排序（分配与收集），直至最高位，序列即变为有序。

Java 实现要点：首先需要确定最大值的位数，决定排序趟数。使用 List<ArrayList> 模拟 10 个桶（队列），根据每一位数字进行分配和收集。

import java.util.ArrayList;
import java.util.List;
 
public class radixSort {
 inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51};
 public radixSort() {
  sort(a);
  for(inti=0;i<a.length;i++){
   System.out.println(a[i]);
  }
 }
 public void sort(int[] array){
  int max=array[0];
  for(inti=1;i<array.length;i++){
   if(array[i]>max){
    max=array[i];
   }
  }
  int time=0;
  while(max>0){
   max/=10;
   time++;
  }
 
  List<ArrayList> queue=newArrayList<ArrayList>();
  for(int i=0;i<10;i++){
   ArrayList<Integer>queue1=new ArrayList<Integer>();
   queue.add(queue1);
  }
 
  for(int i=0;i<time;i++){
   for(intj=0;j<array.length;j++){
    int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
    ArrayList<Integer>queue2=queue.get(x);
    queue2.add(array[j]);
    queue.set(x, queue2);
   }
   int count=0;
   for(int k=0;k<10;k++){
    while(queue.get(k).size()>0){
     ArrayList<Integer>queue3=queue.get(k);
     array[count]=queue3.get(0);
     queue3.remove(0);
     count++;
    }
   }
  }  
 }
}

分配与收集示意：