十大经典排序方法目录

十大经典排序算法一、冒泡排序二、选择排序三、插入排序四、希尔排序五、桶排序

十大经典排序算法

一、冒泡排序

       算法步骤：

       比较相邻的元素。如果第一个比第二个大，就交换他们两个。

       对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

       针对所有的元素重复以上的步骤，除了最后一个。

       持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

       动图演示：        代码演示：（在20个范围在1~100的整数里进行排序）

import java.util.Random; public class Practice { public static void main(String[] args){ Random rand = new Random(); int[] arr = new int[20]; for (int i = 0; i < arr.length; i++) { arr[i]=1+rand.nextInt(100); } for (int i : arr) { System.out.print(i+"\t"); } System.out.println(); //冒泡排序 for (int i = 0,t; i < arr.length-1; i++) { for (int j = 0; j < arr.length-1-i; j++) { if(arr[j]>arr[j+1]){ t=arr[j]; arr[j]=arr[j+1]; arr[j+1]=t; } } } for (int i : arr) { System.out.print(i+"\t"); } } }

       代码结果：

70 10 9 15 97 61 26 69 75 19 66 57 79 12 30 65 44 96 94 63 9 10 12 15 19 26 30 44 57 61 63 65 66 69 70 75 79 94 96 97

---

二、选择排序

       算法步骤：

       首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

       再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

       重复第二步，直到所有元素均排序完毕。

       动图演示：

       代码演示：（在20个范围在1~100的整数里进行排序）

import java.util.Random; public class Practice { public static void main(String[] args){ Random rand = new Random(); int[] arr = new int[20]; for (int i = 0; i < arr.length; i++) { arr[i]=1+rand.nextInt(100); } for (int i : arr) { System.out.print(i+"\t"); } System.out.println(); //选择排序 for (int i = 0,maxIx=0,maxVarIx=0,t,j; i < arr.length; i++) { maxIx=arr.length-i-1; maxVarIx=0; for ( j = 1; j <=maxIx ; j++) { if(arr[j]>arr[maxVarIx]){ maxVarIx=j; } } if(maxIx!=maxVarIx){ t=arr[maxIx]; arr[maxIx]=arr[maxVarIx]; arr[maxVarIx]=t; } } for (int i : arr) { System.out.print(i+"\t"); } } }

       代码结果：

82 23 3 54 57 70 43 10 17 76 35 89 64 59 69 89 74 12 85 96 3 10 12 17 23 35 43 54 57 59 64 69 70 74 76 82 85 89 89 96

---

三、插入排序

       算法步骤：

       将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

       从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

       动图演示：        代码演示：（在20个范围在1~100的整数里进行排序）

import java.util.Random; public class Practice { public static void main(String[] args){ Random rand = new Random(); int[] arr = new int[20]; for (int i = 0; i < arr.length; i++) { arr[i]=1+rand.nextInt(100); } for (int i : arr) { System.out.print(i+"\t"); } System.out.println(); //插入排序 for (int i = 1,t,j; i < arr.length; i++) { t=arr[i]; for (j = i-1; j >=0 && arr[j]>t ; j--) { arr[j+1]=arr[j]; } arr[j+1]=t; } for (int i : arr) { System.out.print(i+"\t"); } } }

       代码结果：

21 81 93 55 76 28 56 78 20 73 33 68 66 2 67 32 78 31 52 85 2 20 21 28 31 32 33 52 55 56 66 67 68 73 76 78 78 81 85 93

---

四、希尔排序

       希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本

       在进行插入排序之前，先按照不同的间隔进行两个之间的比较，间隔为数组长度的一半，比完一次按照顺序还是降序的要求交换位置，间隔再减半，直至间隔小于等于2；

       代码演示：（在20个范围在1~100的整数里进行排序）

import java.util.Random; public class Practice { public static void main(String[] args){ Random rand = new Random(); int[] arr = new int[20]; for (int i = 0; i < arr.length; i++) { arr[i]=1+rand.nextInt(100); } for (int i : arr) { System.out.print(i+"\t"); } System.out.println(); //希尔排序 int step =arr.length; for (step = arr.length/2; step >=2 ; step/=2) { for (int i = 0,t; i < arr.length/2; i++) { if(arr[i]>arr[i+step]){ t=arr[i]; arr[i]= arr[i+step]; arr[i+step]=t; } } } for (int i = 1,j,t; i < arr.length; i++) { t=arr[i]; for (j = i-1; j >=0 && arr[j]>t ; j--) { arr[j+1]=arr[j]; } arr[j+1]=t; } for (int i : arr) { System.out.print(i+"\t"); } } }

       代码结果：

99 19 11 1 77 39 44 16 24 92 97 56 25 69 30 72 22 53 51 82 1 11 16 19 22 24 25 30 39 44 51 53 56 69 72 77 82 92 97 99

---

五、桶排序

       演示图：

       先把元素分布在桶中：        然后元素在每个桶中排序，最后再依次从桶里拿回元素

       代码演示：（在20个范围在1~100的整数里进行排序）

       此时用的桶排序思想为先按照每个数的个位数进行排序，取出之后再按照每个数的十位数进行排序后取出，最后达到顺序排列

import java.util.Random; public class Practice { public static void main(String[] args){ Random rand = new Random(); int[] arr = new int[20]; for (int i = 0; i < arr.length; i++) { arr[i]=1+rand.nextInt(100); } for (int i : arr) { System.out.print(i+"\t"); } System.out.println(); //桶排序 final int U=10; int[][] bucket= new int[U][arr.length]; int[] ixs = new int[U]; for (int i=1,t, count;; i*=10) { //每个位数放之前都要初始化计数 count = 0; //把数组的元素丢入对应的桶内 for (int j = 0; j <arr.length ; j++) { count=(t=arr[j]/i)>=1?++count:count; bucket[t%=U][ixs[t]++]=arr[j]; } //判断对应位数是否存在 if(count==0){break;} //把对应位数排序好之后的数依次放回数组中 for (int j = 0,k,ix=0; j < U; j++) { for ( k = 0; k <ixs[j] ; k++) { arr[ix++]=bucket[j][k]; } } //计数清零 for (int j = 0; j < ixs.length; j++) { ixs[j]=0; } } for (int i : arr) { System.out.print(i+"\t"); } } }

       代码结果：

25 48 42 68 73 35 14 96 91 43 74 94 9 6 83 83 34 11 55 77 6 9 11 14 25 34 35 42 43 48 55 68 73 74 77 83 83 91 94 96

---

PS：作者是一枚刚入编程的小白，如果有写错或者写的不好的地方，欢迎各位大佬在评论区留下宝贵的意见或者建议，敬上！如果这篇博客对您有帮助，希望您可以顺手帮我点个赞！不胜感谢！

原创作者：wsjslient

作者主页：https://blog.csdn.net/wsjslient

参考文档：https://www.runoob.com/java/java-tutorial.html

---