十大基础排序算法[java源码+动静双图解析+性能分析] - 只会一点java
一、概述
作为一个合格的程序员，算法是必备技能，特此总结十大基础排序算法。java版源码实现，强烈推荐《算法第四版》非常适合入手，所有算法网上可以找到源码下载。
PS：本文讲解算法分三步：1.思想2.图示3.源码4.性能分析
1.1 时间复杂度
算法的运行时间，在这里主要考量：比较和交换的成本。
常见的时间复杂度排序：常数阶O(1)<对数阶O(
log2n)<线性阶O(n)<线性对数阶O(nlog2n)<平方阶O(n^2)<立方阶O(n^3)<指数阶O(2^n)
1.2 空间复杂度
使用的内存，是否需要额外的存储空间。
1.3 稳定性
相等元素排序前后相对位置保持不变，就认为是稳定的。
稳定性何时有意义？
1）排序对象包含多个属性
2) 原始序列其它属性有序
3）期望最终排序后原来有序的属性还有序，原来没序的字段有序了。
二、常见排序算法
通用函数封装
由于排序算法都用到一些相同源码，所以提炼出来作为一个父类，算法只需要继承这个类即可使用通用方法：
1.less()比较元素大小
2.exch()交换元素
3.show()打印排序后数组
4.isSorted()校验排序是否正确
1 package algorithm;2
3 /**
4 *
5 * @ClassName:MySort
6 * @Description:自定义排序基类，封装常用方法
7 * @author denny.zhang
8 * @date 2018年2月5日下午3:12:03
9 */
10 public class MySort {
11 protected static String[] a = new String[]{"a","d","c","b"};
12
13 /**
14 *
15 * @Description 打印排序后结果
16 * @param a
17 * @author denny.zhang
18 * @date 2018年2月5日下午3:11:46
19 * @since JDK1.8
20 */
21 protected static void show(Comparable[] a){
22 for(int i=0;i<a.length;i++){
23 System.out.print(a[i]+" ");
24 }
25 System.out.println();
26 }
27
28 /**
29 *
30 * @Description 比较是否v小于w
31 * @param v
32 * @param w
33 * @return
34 * @author denny.zhang
35 * @date 2018年2月5日下午3:11:14
36 * @since JDK1.8
37 */
38 protected static boolean less(Comparable v,Comparable w){
39 return v.compareTo(w)<0;
40 }
41
42 /**
43 *
44 * @Description 对于数组a,交换a[i]和a[j]。
45 * @param a
46 * @param i
47 * @param j
48 * @author denny.zhang
49 * @date 2018年2月5日下午3:09:41
50 * @since JDK1.8
51 */
52 protected static void exch(Comparable[] a,int i,int j){
53 Comparable temp= a[i];
54 a[i]=a[j];
55 a[j]=temp;
56 //System.out.println("交换a["+i+"]"+",a["+j+"]");
57 }
58
59 /**
60 *
61 * @Description 用于校验是否升序
62 * @param a
63 * @return
64 * @author denny.zhang
65 * @date 2018年2月5日下午3:10:57
66 * @since JDK1.8
67 */
68 protected static boolean isSorted(Comparable[] a){
69 //只要有一个后数<前数，返回失败
70 for(int i=0;i<a.length;i++){
71 if(less(a[i], a[i-1])) return false;
72 }
73 //都没问题，返回成功
74 return true;
75 }
76
77 /**
78 *
79 * @Description 用于校验是否升序
80 * @param a
81 * @param lo 起始下标
82 * @param hi 结束下标
83 * @return
84 * @author denny.zhang
85 * @date 2018年2月6日下午5:19:43
86 * @since JDK1.8
87 */
88 protected static boolean isSorted(Comparable[] a, int lo, int hi) {
89 for (int i = lo + 1; i <= hi; i++)
90 if (less(a[i], a[i-1])) return false;
91 return true;
92 }
93 }
2.1 冒泡排序
思想：
最简单的排序，内外两遍循环。外循环简单遍历a[n-1]~a[1]，内循环一遍确定一个最大值,类似"冒泡"。
1.外循环遍历a[n-1]~a[1]。例如选定a[n-1]
2.内循环，从a[0]-a[n-1] 从左往右，比较相邻的元素对。如果第一个比第二个大，就交换它们两个，一直到最后一对，这样在最后的元素a[n-1]是最大的数；
2.重复以上的步骤，一直到外循环遍历到a[1]，内循环会比较a[0],a[1],至此排序完毕。
优化点：添加一个标记，当内循环一遍不交换，排序完毕。
动态图：
源码：
1 /**2 * @author denny
3 * @Description 冒泡排序
4 * @date 2019/7/2 下午6:19
5 */
6 public class Bubble extends MySort {
7
8 public static void sort(Comparable[] a) {
9 int n = a.length;
10 // 标记内层遍历是否交换过
11 int flag = 0;
12 // 外层遍历n-1次，每次确定一个最大值 a[i]
13 for (int i = n - 1; i > 0; i--) {
14 // 内层遍历:比较a[0]a[1]...a[n-1-1]a[n-1]
15 for (int j = 0; j < i; j++) {
16 // 相邻元素两两对比，如果后<前，交换
17 if (less(a[j + 1], a[j])) {
18 // 元素交换
19 exch(a, j + 1, j);
20 flag = 1;
21 }
22 }
23 // flag=0，说明数列已有序不需要再交换了！！！
24 if(flag==0){
25 break;
26 }
27 }
28 }
29
30 public static void main(String[] args) {
31 Bubble.sort(a);
32 show(a);
33 }
34 }
分析：
时间复杂度：外部循环O(n) * 内部循环O(n) -->O(n²)
空间复杂度：不需要借助外部空间-->O(1)
是否稳定：相等元素不交换-->是。
2.2 选择排序
思想：
最简单的排序，内外两遍循环。外循环简单遍历a[0]~a[n-1]，内循环每次确定一个最小值
1.外循环假设第一个数是最小值
2.内循环拿后面所有元素和第一个元素比较，找到最小值，放在第一位（如果第一位不是最小值就交换）,第一小的元素确定。
3.外循环从第一个元素遍历到最后，重复1,2操作，排序完毕。
图示：
动态图：
源码：
1 package algorithm;2
3 /**
4 *
5 * @ClassName:Selection
6 * @Description:选择排序：对于数组长度为N的数组<br>
7 * <ul>
8 * <li>比较次数：(n-1)+(n-2)+...2+1=n(n-1)/2,大约N²/2次</li>
9 * <li>交换次数：N次</li>
10 * </ul>
11 * @author denny.zhang
12 * @date 2018年2月5日上午11:13:26
13 */
14 public class Selection extends MySort{
15
16 @SuppressWarnings("rawtypes")
17 public static void sort(Comparable[] a){
18 int n = a.length;
19 //遍历n次，每次确定一个最小值
20 for(int i=0 ; i<n ; i++){
21 int min=i;//初始化最小值下标为i
22 //把i之后的每一项都和a[min]比较，求最小项
23 for(int j=i+1;j<n;j++){
24 if (less(a[j], a[min])) min = j;
25 }
26 //a[i]和a[min]交换，第i位排序完毕
27 exch(a, i, min);
28 }
29 }
30
31 public static void main(String[] args) {
32 Selection.sort(a);
33 show(a);
34 }
35 }
分析：
时间复杂度：外部循环O(n) * 内部循环O(n) = O(n²)
空间复杂度：O(1)不需要借助外部空间
是否稳定：否。只要遇到小的就交换，被交换对象如果有等值元素存在且在交换元素之前，打破相对顺序了。列子：58529-》第一个5和2交换，2个5的相对顺序变了。
2.3 插入排序
思想：
类似扑克牌抓牌一样，一次插入一张牌保证当前牌有序。
从第二张牌开始，插入第一张牌；第三张牌插入前两张牌...一直到最后一张牌。插入牌时，两两比较，遇到逆序交换。
外循环i++,内循环a[j]和a[j-1]比较，逆序交换。j--往左移动，两两比较。
图示：
动态图：
源码：
1 package algorithm;2
3 /**
4 *
5 * @ClassName:Insertion
6 * @Description:插入排序：对于数组长度为N的数组<br>就像扑克牌插纸牌一样
7 * <ul>
8 * <li>比较次数：N-1~N²/2 平均N²/4 </li>
9 * <li>交换次数：0~N²/2 平均N²/4</li>
10 * </ul>
11 * @author denny.zhang
12 * @date 2018年2月5日上午11:13:26
13 */
14 public class Insertion extends MySort{
15
16 @SuppressWarnings("rawtypes")
17 public static void sort(Comparable[] a){
18 int n = a.length;
19 //遍历n-1次，a[i]插入前i个数
20 for(int i=1 ; i<n ; i++){
21 //System.out.println("i="+i);
22 //i之前的每两项比较，出现逆序，立即交换
23 for(int j=i;j>0 && less(a[j], a[j-1]);j--){
24 exch(a, j, j-1);
25 }
26 }
27 }
28
29 public static void main(String[] args) {
30 Insertion.sort(a);
31 show(a);
32 }
33 }
分析：
时间复杂度：O（n~n²）如果元素有序就是n, 元素逆序就是n²
空间复杂度：O（1）
是否稳定：是
2.4 希尔排序
思想：
希尔排序又称缩小增量排序，是插入排序的升级版。核心思想是使数组中任意间隔为h的元素有序，针对每个h，取出间隔h的子数组并插入排序，h越来越小一直到1，即排序完成。这个间隔h的选择有考究。
图示：
动态图：
步长：3-2-1
源码：
递增序列有很多，只要满足最后一个数为1即可。即最少有间隔为1的插入排序即可保证排序。至于这个数列具体最优不在本文讨论范围内。
下图展示了2种序列，sort()方法是复杂序列，sort2()是简单序列。如果只是理解算法的话sort2()足矣。
1 package algorithm;2
3 /**
4 *
5 * @ClassName:Shell
6 * @Description:希尔排序:改进自插入排序，交换不相邻元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序<br>
7 *
8 * @author denny.zhang
9 * @date 2018年2月5日上午11:13:26
10 */
11 public class Shell extends MySort{
12
13 /**
14 *
15 * @Description 更加符合要求的算法
16 * @param a
17 * @author denny.zhang
18 * @date 2018年3月7日下午5:35:07
19 * @since JDK1.8
20 */
21 @SuppressWarnings("rawtypes")
22 public static void sort(Comparable[] a){
23 int n = a.length;
24
25 // 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...
26 int h = 1;
27 while (h < n/3) {//这里确保了每个子数组有>=3个元素,h间隔过大，每个子数组元素太少就没有排序的意义了
28 h = 3*h + 1; //1.如果小于n/3,h变大,直到h>=n/3为止
29 }
30 while (h >= 1) {
31 // h-sort the array 2.遍历从h->n
32 for (int i = h; i < n; i++) {
33 //3.从j开始往左每h间隔比较一次，逆序就交换
34 for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
35 exch(a, j, j-h);
36 }
37 }
38 assert isHsorted(a, h);
39 h /= 3;//排完序再把h降低回来
40 }
41 assert isSorted(a);
42 }
43
44 /**
45 *
46 * @Description d=n/2序列（向上取整）简单算法
47 * @param a
48 * @author denny.zhang
49 * @date 2018年3月7日下午5:33:38
50 * @since JDK1.8
51 */
52 @SuppressWarnings("rawtypes")
53 public static void sort2(Comparable[] a){
54 int n = a.length;
55 int h = n;
56 //1.第一层循环 是h值计算
57 while (h >= 1) {
58 h=(int) Math.ceil(h/2);//向上取整
59 //2.第二层循环i++ 从h->n-1
60 for (int i = h; i < n; i++) {
61 //3.第三层循环 从j开始往左每h间隔比较一次，逆序就交换,做到局部有序
62 for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
63 exch(a, j, j-h);
64 }
65 }
66 assert isHsorted(a, h);
67 }
68 assert isSorted(a);
69 }
70
71 // is the array h-sorted?
72 private static boolean isHsorted(Comparable[] a, int h) {
73 for (int i = h; i < a.length; i++)
74 if (less(a[i], a[i-h])) return false;
75 return true;
76 }
77
78 public static void main(String[] args) {
79 Shell.sort(a);
80 show(a);
81 }
82 }
分析：
时间复杂度：O（n的1~2次方，暂无法证明最优递增数列）
空间复杂度：O（1）
是否稳定：否
2.5 归并排序
思想：
将数组拆分为两部分（递归）分别排序，再将结果归并排序。
图示：
动态图：
源码：
1 package algorithm;2
3 /**
4 *
5 * @ClassName:Merge
6 * @Description:归并排序：自顶向下+自底向上。性能差不多：比较次数：1/2NlgN-NlgN 访问次数6NlgN
7 * @author denny.zhang
8 * @date 2018年2月6日下午5:09:57
9 */
10 public class Merge extends MySort{
11
12
13 /**
14 *
15 * @Description 归并
16 * @param a
17 * @param aux
18 * @param lo
19 * @param mid
20 * @param hi
21 * @author denny.zhang
22 * @date 2018年2月6日下午4:55:25
23 * @since JDK1.8
24 */
25 private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
26
27 // 复制数组a->aux
28 for (int k = lo; k <= hi; k++) {
29 aux[k] = a[k];
30 }
31
32 // 归并进a数组
33 int i = lo, j = mid+1;
34 //从aux数组找到小值并赋值给数组a
35 for (int k = lo; k <= hi; k++) {
36 if (i > mid) a[k] = aux[j++];//左半边用尽，取右半边元素aux[j]->赋值给a[k],并j++
37 else if (j > hi) a[k] = aux[i++];//右半边用尽，取左半边元素aux[i]->赋值给a[k],并i++
38 else if (less(aux[j], aux[i])) a[k] = aux[j++];//aux[j]小->赋值给a[k],并j++
39 else a[k] = aux[i++];//aux[i]小->赋值给a[k],并i++
40 }
41 }
42
43 // 自顶向下归并排序 a[lo..hi] 使用辅助数组 aux[lo..hi]
44 private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
45 if (hi <= lo) return;
46 int mid = lo + (hi - lo) / 2;
47 sort(a, aux, lo, mid);//左半边排序
48 sort(a, aux, mid + 1, hi);//右半边排序
49 merge(a, aux, lo, mid, hi);//归并结果
50 }
51
52 /**
53 *
54 * @Description 自底向上归并排序
55 * @param a
56 * @author denny.zhang
57 * @date 2018年2月6日下午6:46:01
58 * @since JDK1.8
59 */
60 public static void sortBU(Comparable[] a,Comparable[] aux) {
61 int n = a.length;
62 for (int len = 1; len < n; len *= 2) {//len子数组大小，有多少个子数组遍历多少回
63 //子数组从2个元素开始自己归并：22归并->44归并->88归并...最后一个大归并
64 for (int lo = 0; lo < n-len; lo += len+len) {//lo子数组起始下标
65 int mid = lo+len-1;
66 int hi = Math.min(lo+len+len-1, n-1);//最后一个数组可能小于len,即不能按照2的倍数分小数组，最后一个取最小值
67 merge(a, aux, lo, mid, hi);
68 }
69 }
70 }
71
72 /**
73 *
74 * @Description 归并排序
75 * @param a
76 * @author denny.zhang
77 * @date 2018年2月6日下午4:52:45
78 * @since JDK1.8
79 */
80 public static void sort(Comparable[] a) {
81 //定义一个辅助数组
82 Comparable[] aux = new Comparable[a.length];
83 //自顶向下归并
84 sort(a, aux, 0, a.length-1);
85 //自底向上归并
86 //sortBU(a,aux);
87 //校验是否排序成功
88 assert isSorted(a);
89 }
90
91 public static void main(String[] args) {
92 Merge.sort(a);
93 show(a);
94 }
95 }
分析：
时间复杂度：O（NlogN）简单理解：看上图源码44行sort(),把数组拆分2个有序数组，然后再归并2个小数组。长度为N的数组递归“折半拆分成2个有序数组”需要logN步（二叉排序树的树高），每一步的归并耗时N，相乘得到NlogN即是时间复杂度。
空间复杂度：O（N）不用多说使用了额外的辅助数组aux[N]
是否稳定：是
2.6 快速排序
思想：
两向切分：取数组第一个元素作为切分元素，左边子数组全部小于等于切分元素，右边子数组全部大于等于切分元素，这样每切分一次就可以确定一个元素的位置。左右子数组再分别递归排序。
三向切分：对于数组中重复元素多的数组，更适合三向切分。也是第一个元素作为切分元素值=v,三向切分：第一段：lo~lt元素<v，第二段：lt~gt元素=v，第三段：gt~hi元素>v。递归给第一段和第三段排序。
注意：对于小数组（<=15），插入排序更适合。
图示：
下图是一个两向切分
动态图
源码：
1 package algorithm;2
3 import edu.princeton.cs.algs4.StdRandom;
4
5 /**
6 *
7 * @ClassName:Quick
8 * @Description:快速排序
9 * <ul>
10 * <li>两向切分</li>
11 * <li>三向切分：重复元素多的时候</li>
12 * </ul>
13 * @author denny.zhang
14 * @date 2018年2月7日下午5:50:56
15 */
16 @SuppressWarnings("rawtypes")
17 public class Quick extends MySort{
18
19
20 public static void sort(Comparable[] a) {
21 StdRandom.shuffle(a);//随机排列，避免数组有序出现最差排序
22 show(a);
23 sort(a, 0, a.length - 1);//两向切分
24 //sort3Way(a, 0, a.length - 1);//三向切分
25 assert isSorted(a);
26 }
27
28 /**
29 *
30 * @Description 两向切分快排
31 * @param a
32 * @param lo
33 * @param hi
34 * @author denny.zhang
35 * @date 2018年2月7日下午4:36:48
36 * @since JDK1.8
37 */
38 private static void sort(Comparable[] a, int lo, int hi) {
39 if (hi <= lo) return;//
40 int j = partition(a, lo, hi);//拆分，找到拆分下标
41 System.out.println("j="+j);
42 show(a);
43 sort(a, lo, j-1);//左边排序，递归
44 sort(a, j+1, hi);//右边排序，递归
45 assert isSorted(a, lo, hi);
46 }
47
48 // 两向切分数组，找到拆分下标并返回，保证a[lo..j-1] <= a[j] <= a[j+1..hi]
49 private static int partition(Comparable[] a, int lo, int hi) {
50 System.out.println("lo="+lo+",hi="+hi);
51 int i = lo;//左指针
52 int j = hi + 1;//右指针
53 Comparable v = a[lo];//初始化一个切分元素
54 //一个大的自循环
55 while (true) {
56
57 // 分支1：如果左指针元素小于v,++i，一直到右边界退出，或者左边有不小于v的元素停下，执行分支2
58 while (less(a[++i], v))
59 if (i == hi) break;
60
61 // 分支2：如果右指针元素大于v,j--,一直到到左边界退出，或者右边有不大于v的元素为止，执行分支3
62 while (less(v, a[--j]))
63 if (j == lo) break;
64
65 // 分支3：如果左右指针碰撞，甚至左指针大于右指针，退出
66 if (i >= j) break;
67 // 交换需要交换的a[i]>=v>=a[j],使得a[i]<a[j]
68 System.out.println("交换 a[i] a[j] i="+i+",a[i]="+a[i]+",j="+j+",a[j]="+a[j]);
69 exch(a, i, j);
70
71 }
72 System.out.println("i="+i+",j="+j+",设置 a[j]="+a[j]+",替换为a[lo]="+a[lo]);
73 十大基础排序算法[java源码+动静双图解析+性能分析] - 只会一点java 的全部内容， 来源链接： utcz.com/z/392375.html
