Java中数组高级之各种排序代码

简介: 1.冒泡排序 1 package cn.itcast; 2 3 /* 4 * 冒泡排序基本思路是: 5 * 依次比较相邻的两个数,将小数放在前面,大数放在后面。 6 * 即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。

1.冒泡排序

 1 package cn.itcast;
 2 
 3 /*
 4  * 冒泡排序基本思路是:
 5  *         依次比较相邻的两个数,将小数放在前面,大数放在后面。
 6  *         即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。
 7  *         然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,
 8  *         直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。
 9  *        在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),
10  *         将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数。(其实在整个数列中是第二大的数)。
11   *        如此下去,重复以上过程,直至最终完成排序。 
12  */
13 public class BubbleSort {
14     public static void sort(int[] data) {
15         for (int i = 0; i < data.length - 1; i++) {
16             for (int j = 0; j < data.length - 1 - i; j++) {
17                 if (data[j] > data[j + 1]) {
18                     SortTest.swap(data, j, j + 1);
19                 }
20             }
21         }
22     }
23 }
View Code

2.选择排序

 1 package cn.itcast;
 2 
 3 /*
 4  * 选择排序基本思路是:
 5  *         把第一个元素依次和后面的所有元素进行比较。
 6  *         第一次结束后,就会有最小值出现在最前面。
 7  *         其余依次类推。
 8  */
 9 public class SelectionSort {
10     public static void sort(int[] data) {
11         for (int x = 0; x < data.length - 1; x++) {
12             for (int y = x + 1; y < data.length; y++) {
13                 if (data[y] < data[x]) {
14                     SortTest.swap(data, x, y);
15                 }
16             }
17         }
18     }
19 }
View Code

3.插入排序

 1 package cn.itcast;
 2 
 3 /*
 4  * 插入排序基本思路是:
 5  *         将n个元素的数列分为已有序和无序两个部分,如插入排序过程示例下所示:   
 6  *         {{a1},{a2,a3,a4,…,an}}   
 7  *         {{a1⑴,a2⑴},{a3⑴,a4⑴ …,an⑴}} 
 8  *         {{a1(n-1),a2(n-1) ,…},{an(n-1)}}   
 9  *         每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,
10  *         找出插入位置,将该元素插入到有序数列的合适位置中。
11  */
12 public class InsertSort {
13     public static void sort(int[] data) {
14         for (int i = 1; i < data.length; i++) {
15             for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
16                 SortTest.swap(data, j, j - 1);
17             }
18         }
19     }
20 }
View Code

4.希尔排序

 1 package cn.itcast;
 2 
 3 /*
 4  * 希尔排序基本思路是:
 5         先取一个小于n的整数d1作为第一个增量,
 6  *         把文件的全部记录分成(n除以d1)个组。所有距离为d1的倍数的记录放在同一个组中。
 7  *         先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,
 8  *         直至所取的增量dt=1(dt < dt-l <…< d2 < d1),即所有记录放在同一组中进行直接插入排序为止。 
 9  *
10  * 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。   
11  *         排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,
12  *         组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1, 即所有记录放进一个组中排序为止 。   
13  * 初始:
14  * d=5   49 38 65 97 76 13 27 49 55 04    
15  * 49 13   |-------------|    
16  * 38 27       |-------------|    
17  * 65 49        |---------------|    
18  * 97 55             |---------------|    
19  * 76 04               |--------------|    
20  * 一趟结果   13 27 49 55 04 49 38 65 97 76  
21  *  
22  * d=3        13 27 49 55 04 49 38 65 97 76    
23  * 13 55 38 76  |--------|--------|--------|    
24  * 27 04 65        |--------|--------|    
25  * 49 49 97           |--------|--------|   
26  * 二趟结果  13 04 49 38 27 49 55 65 97 76 
27  *   
28  * d=1     13 04 49 38 27 49 55 65 97 76
29  *         |--|--|--|--|--|--|--|--|--|  
30  * 13 04 49 38 27 49 55 65 97 76
31  * 三趟结果  04 13 27 38 49 49 55 65 76 97
32  */
33 public class ShellSort {
34     public static void sort(int[] data) {
35         for (int i = data.length / 2; i > 2; i /= 2) {
36             for (int j = 0; j < i; j++) {
37                 insertSort(data, j, i);
38             }
39         }
40         insertSort(data, 0, 1);
41     }
42 
43     /**
44      * @param data
45      * @param j
46      * @param i
47      */
48     private static void insertSort(int[] data, int start, int inc) {
49         for (int i = start + inc; i < data.length; i += inc) {
50             for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
51                 SortTest.swap(data, j, j - inc);
52             }
53         }
54     }
55 }
View Code

5.快速排序

 1 package cn.itcast;
 2 
 3 /*
 4  * 快速排序基本思路是:
 5  *         一趟快速排序的算法是:   
 6  *             1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;   
 7  *             2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];   
 8  *             3)从j开始向前搜索,即由后开始向前搜索(j=j-1即j--),
 9  *                 找到第一个小于key的值A[j],A[i]与A[j]交换;   
10  *             4)从i开始向后搜索,即由前开始向后搜索(i=i+1即i++),
11  *                 找到第一个大于key的A[i],A[i]与A[j]交换;   
12  *             5)重复第3、4、5步,直到 i=j。 
13  *             (3,4步是在程序中没找到时候,j=j-1,i=i+1,直至找到为止。
14  *             找到并交换的时候i,j指针位置不变。
15  *             另外当i=j这过程一定正好是i++或j--完成的,最后令循环结束。)
16  */
17 public class QuickSort {
18     public static void sort(int[] data) {
19         quickSort(data, 0, data.length - 1);
20     }
21 
22     private static void quickSort(int[] data, int i, int j) {
23         int pivotIndex = (i + j) / 2;
24         // swap
25         SortTest.swap(data, pivotIndex, j);
26 
27         int k = partition(data, i - 1, j, data[j]);
28         SortTest.swap(data, k, j);
29         if ((k - i) > 1)
30             quickSort(data, i, k - 1);
31         if ((j - k) > 1)
32             quickSort(data, k + 1, j);
33 
34     }
35 
36     /**
37      * @param data
38      * @param i
39      * @param j
40      * @return
41      */
42     private static int partition(int[] data, int l, int r, int pivot) {
43         do {
44             while (data[++l] < pivot)
45                 ;
46             while ((r != 0) && data[--r] > pivot)
47                 ;
48             SortTest.swap(data, l, r);
49         } while (l < r);
50         SortTest.swap(data, l, r);
51         return l;
52     }
53 }
View Code

6.归并排序

 1 package cn.itcast;
 2 
 3 /*
 4  * 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。   
 5  *         如设有数列{6,202,100,301,38,8,1}   
 6  *         初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数   
 7  *                i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]     3   
 8  *                i=2 [ 6 100 202 301 ] [ 1 8 38 ]         4   
 9  *                i=3 [ 1 6 8 38 100 202 301 ]             4 
10  */
11 public class MergeSort {
12     public static void sort(int[] data) {
13         int[] temp = new int[data.length];
14         mergeSort(data, temp, 0, data.length - 1);
15     }
16 
17     private static void mergeSort(int[] data, int[] temp, int l, int r) {
18         int mid = (l + r) / 2;
19         if (l == r)
20             return;
21         mergeSort(data, temp, l, mid);
22         mergeSort(data, temp, mid + 1, r);
23 
24         for (int i = l; i <= r; i++) {
25             temp[i] = data[i];
26         }
27         int i1 = l;
28         int i2 = mid + 1;
29         for (int cur = l; cur <= r; cur++) {
30             if (i1 == mid + 1)
31                 data[cur] = temp[i2++];
32             else if (i2 > r)
33                 data[cur] = temp[i1++];
34             else if (temp[i1] < temp[i2])
35                 data[cur] = temp[i1++];
36             else
37 
38                 data[cur] = temp[i2++];
39         }
40     }
41 }
View Code

7.堆排序

 1 package cn.itcast;
 2 
 3 /*
 4  * 堆排序基本思路是:        
 5  *         堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。   
 6  *         (1)用大根堆排序的基本思想:    
 7  *            ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区;  
 8  *            ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个 记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key;  
 9  *            ③ 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。
10  *              然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],
11  *               且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。   
12  *         (2)大根堆排序算法的基本操作:    
13  *            ① 初始化操作:将R[1..n]构造为初始堆;    
14  *            ② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
15  */
16 public class HeapSort {
17     public static void sort(int[] data) {
18         MaxHeap h = new MaxHeap();
19         h.init(data);
20         for (int i = 0; i < data.length; i++)
21             h.remove();
22         System.arraycopy(h.queue, 1, data, 0, data.length);
23     }
24 
25     private static class MaxHeap {
26 
27         void init(int[] data) {
28             this.queue = new int[data.length + 1];
29             for (int i = 0; i < data.length; i++) {
30                 queue[++size] = data[i];
31                 fixUp(size);
32             }
33         }
34 
35         private int size = 0;
36 
37         private int[] queue;
38 
39         public int get() {
40             return queue[1];
41 
42         }
43 
44         public void remove() {
45             SortTest.swap(queue, 1, size--);
46             fixDown(1);
47         }
48 
49         // fixdown
50         private void fixDown(int k) {
51             int j;
52             while ((j = k << 1) <= size) {
53                 if (j < size && queue[j] < queue[j + 1])
54                     j++;
55                 if (queue[k] > queue[j]) // 不用交换
56 
57                     break;
58                 SortTest.swap(queue, j, k);
59                 k = j;
60             }
61         }
62 
63         private void fixUp(int k) {
64             while (k > 1) {
65                 int j = k >> 1;
66                 if (queue[j] > queue[k])
67                     break;
68                 SortTest.swap(queue, j, k);
69 
70                 k = j;
71             }
72         }
73 
74     }
75 }
View Code

排序测试类

 1 package cn.itcast;
 2 
 3 import java.util.Arrays;
 4 
 5 public class SortTest {
 6 
 7     public static void main(String[] args) {
 8         int[] arr = { 2, 5, 3, 1, 4 };
 9         System.out.println("排序前:" + Arrays.toString(arr));
10         // BubbleSort.sort(arr);
11         // SelectionSort.sort(arr);
12         // InsertSort.sort(arr);
13         // ShellSort.sort(arr);
14         // QuickSort.sort(arr);
15         // MergeSort.sort(arr);
16         // HeapSort.sort(arr);
17         System.out.println("排序后:" + Arrays.toString(arr));
18     }
19 
20     /*
21      * 交换数组中的两个元素
22      */
23     public static void swap(int[] data, int i, int j) {
24         int temp = data[i];
25         data[i] = data[j];
26         data[j] = temp;
27     }
28 }

 

我的GitHub地址: https://github.com/heizemingjun
我的博客园地址: http://www.cnblogs.com/chenmingjun
我的蚂蚁笔记博客地址: http://blog.leanote.com/chenmingjun
Copyright ©2018 黑泽明军
【转载文章务必保留出处和署名,谢谢!】
相关文章
|
13天前
|
Java
Java 数组学习笔记
本文整理Java数组常用操作:遍历、求和、查找、最值及二维数组行求和等典型练习,涵盖静态初始化、元素翻倍、去极值求平均等实例,帮助掌握数组基础与应用。
|
19天前
|
Java API 开发工具
【Azure Developer】Java代码实现获取Azure 资源的指标数据却报错 "invalid time interval input"
在使用 Java 调用虚拟机 API 获取指标数据时,因本地时区设置非 UTC,导致时间格式解析错误。解决方法是在代码中手动指定时区为 UTC,使用 `ZoneOffset.ofHours(0)` 并结合 `withOffsetSameInstant` 方法进行时区转换,从而避免因时区差异引发的时间格式问题。
115 3
|
28天前
|
缓存 Java 开发者
Java 开发者必看!ArrayList 和 LinkedList 的性能厮杀:选错一次,代码慢成蜗牛
本文深入解析了 Java 中 ArrayList 和 LinkedList 的性能差异,揭示了它们在不同操作下的表现。通过对比随机访问、插入、删除等操作的效率,指出 ArrayList 在多数场景下更高效,而 LinkedList 仅在特定情况下表现优异。文章强调选择合适容器对程序性能的重要性,并提供了实用的选择法则。
102 3
|
2月前
|
人工智能 监控 安全
智慧工地解决方案,java智慧工地程序代码
智慧工地系统融合物联网、AI、大数据等技术,实现对施工现场“人、机、料、法、环”的全面智能监控与管理,提升安全、效率与决策水平。
|
2月前
|
存储 缓存 Java
Java数组全解析:一维、多维与内存模型
本文深入解析Java数组的内存布局与操作技巧,涵盖一维及多维数组的声明、初始化、内存模型,以及数组常见陷阱和性能优化。通过图文结合的方式帮助开发者彻底理解数组本质,并提供Arrays工具类的实用方法与面试高频问题解析,助你掌握数组核心知识,避免常见错误。
|
2月前
|
算法 IDE Java
Java 项目实战之实际代码实现与测试调试全过程详解
本文详细讲解了Java项目的实战开发流程,涵盖项目创建、代码实现(如计算器与汉诺塔问题)、单元测试(使用JUnit)及调试技巧(如断点调试与异常排查),帮助开发者掌握从编码到测试调试的完整技能,提升Java开发实战能力。
261 0
|
3月前
|
安全 Java 测试技术
Java 项目实战中现代技术栈下代码实现与测试调试的完整流程
本文介绍基于Java 17和Spring技术栈的现代化项目开发实践。项目采用Gradle构建工具,实现模块化DDD分层架构,结合Spring WebFlux开发响应式API,并应用Record、Sealed Class等新特性。测试策略涵盖JUnit单元测试和Testcontainers集成测试,通过JFR和OpenTelemetry实现性能监控。部署阶段采用Docker容器化和Kubernetes编排,同时展示异步处理和反应式编程的性能优化。整套方案体现了现代Java开发的最佳实践,包括代码实现、测试调试
133 0
|
13天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案