十大排序算法（Java）

article/2025/10/12 22:01:31

1.冒泡排序

2.快速排序

3.插入排序

4.希尔排序

5.选择排序

6.堆排序

7.归并排序

8.计数排序：速度快，一般用于整数排序

9.桶排序

10.基数排序

1.冒泡排序

在这里插入图片描述

冒泡排序思路：（两层for循环）

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码：


public class Demo01 {public static void main(String[] args) {int[] arr=new int[]{1,5,7,4,8,9};Demo01.sort(arr);}public static void sort(int arr[]){for( int i = 0 ; i < arr.length - 1 ; i++ ) {for (int j = 0; j < arr.length - 1 - i; j++) {int temp = 0;if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}System.out.println(Arrays.toString(arr));}}

2.快速排序

首先选取一个基准数

快速排序思路：

选取第一个数为基准
将比基准小的数交换到前面，比基准大的数交换到后面
对左右区间重复第二步，直到各区间只有一个数

代码：

public class Demo02 {public static void main(String[] args) {int[] arr=new int[]{1,5,3,6,7,4,8};Demo02.sort(arr,0,6);System.out.println(Arrays.toString(arr));}public static int potation(int[] nums,int low,int high){int point=nums[low];while(low<high){while(low < high &&nums[high]>=point) high--;nums[low]=nums[high];while(low < high &&nums[low]<=point) low++;nums[high]=nums[low];}nums[low]=point;return low;}public static void sort(int[] nums,int low,int high){if(low<high){int pivotpos=potation(nums,low,high);sort(nums,low,pivotpos-1);sort(nums,pivotpos+1,high);}}
}

3.插入排序

插入排序思路：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

代码：

public static void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; ++i) {int value = arr[i];int j = 0;//插入的位置for (j = i-1; j >= 0; j--) {if (arr[j] > value) {arr[j+1] = arr[j];//移动数据} else {break;}}arr[j+1] = value; //插入数据}}

4.希尔排序

在这里插入图片描述

希尔排序思路：

基本思想：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。
希尔排序法(缩小增量法) 属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

代码：

public int[] shellSort(int[] A, int n) {//要插入的纸牌int temp,j,i;//设定增量D,增量D/2逐渐减小for(int D = n/2;D>=1;D=D/2){//从下标d开始，对d组进行插入排序for(j=D;j<n;j++){temp = A[j];for(i=j;i>=D&&A[i-D]>temp;i-=D){A[i]=A[i-D];}A[i]=temp;}}return A;}

5.选择排序

每次挑出最小的元素

代码：

public static void sort(int arr[]){for( int i = 0;i < arr.length ; i++ ){int min = i;//最小元素的下标for(int j = i + 1;j < arr.length ; j++ ){if(arr[j] < arr[min]){min = j;//找最小值}}//交换位置int temp = arr[i];arr[i] = arr[min];arr[min] = temp;}}

6.堆排序

代码：

public int[] heapSort(int[] A, int n) {//堆排序算法int i;//先把A[]数组构建成一个大顶堆。//从完全二叉树的最下层最右边的非终端结点开始构建。for(i=n/2-1;i>=0;i--){HeapAdjust(A,i,n);}//开始遍历for(i=n-1;i>0;i--){swap(A,0,i);//每交换一次得到一个最大值然后丢弃HeapAdjust(A,0,i);}return A;}//A[i]代表的是下标为i的根结点private void HeapAdjust(int[] A,int i,int n){int temp;temp = A[i];for(int j=2*i+1;j<n;j=j*2+1){if(j<n-1&&A[j]<A[j+1]){++j;}if(temp>=A[j]){break;}//将子节点赋值给根结点A[i] = A[j];//将子节点下标赋给ii = j;}//将存储的根结点的值赋给子节点A[i] = temp;}private void swap(int[] A,int i,int j){int temp = A[i];A[i]=A[j];A[j] = temp;}

7.归并排序

将其分成两路，每路再分两路，依次排序

8.计数排序：速度快，一般用于整数排序

计数排序步骤：

找出待排序的数组中最大和最小的元素
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
对所有的计数累加（从 C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去1

代码：

public static void sort(int[] arr) {//找出数组中的最大值int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}//初始化计数数组int[] countArr = new int[max + 1];//计数for (int i = 0; i < arr.length; i++) {countArr[arr[i]]++;arr[i] = 0;}//排序int index = 0;for (int i = 0; i < countArr.length; i++) {if (countArr[i] > 0) {arr[index++] = i;}}}

9.桶排序

类似于计数排序，将桶分好类，一定范围，再对桶内元素排序

public int[] countingSort(int[] A, int n) {if(A==null ||n<2){return A;}//找出桶的范围,即通过要排序的数组的最大最小值来确定桶范围int min=A[0];int max=A[0];for(int i=0;i<n;i++){min=Math.min(A[i],min);max=Math.max(A[i],max);}//确定桶数组，桶的下标即为需排序数组的值，桶的值为序排序数同一组值出现的次数int[] arr = new int[max-min+1];//往桶里分配元素for(int i=0;i<n;i++){arr[A[i]-min]++;}//从桶中取出元素int index=0;for(int i=0;i<arr.length;i++){while(arr[i]-->0){A[index++]=i+min;}}return A;}