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

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 }

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 }

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 }

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 }

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 }

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 }

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 }

排序测试类

 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Fish

内存对齐(Memory Alignment)

最近读文档,发现对内存对齐的概念不太明白。 内存对齐的原则: 数据成员对齐规则:结构(struct)(或联合(union))的数据成员,第一个数据成员放在o...

209100
来自专栏武培轩的专栏

剑指Offer-合并两个排序的链表

题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 思路 思路一(迭代): 首先处理空链表,当其中一个为空链...

26940
来自专栏chenjx85的技术专栏

leetcode-680-Valid Palindrome II

20950
来自专栏LeetCode

LeetCode SingleNumber I,II,III

Given a non-empty array of integers, every element appears twice except for one....

20500
来自专栏程序员的SOD蜜

在C++中反射调用.NET(三) 使用非泛型集合的委托方法C++中的列表对象list C++传递集合数据给.NET创建泛型List实例反射静态方法反射调用索引器当委托遇到协变和逆变C++/CLI

在.NET与C++之间传输集合数据 上一篇《在C++中反射调用.NET(二)》中,我们尝试了反射调用一个返回DTO对象的.NET方法,今天来看看如何在.NET与...

321100
来自专栏Java帮帮-微信公众号-技术文章全总结

Java案例-判断随机整数是否是素数

Java案例-判断随机整数是否是素数 ? 判断随机整数是否是素数 产生 100 个0-999 之间的随机整数,然后判断这100 个随机整数哪些是素数,哪些不是?...

57440
来自专栏小筱月

嵌套数组的合并,扁平化数组

对于 [ [], [], [], ...] 数组里嵌套数组,有个需求:将里面的数组元素都放到外层数组,变成 , , , ...

30430
来自专栏hbbliyong

LINQ查询操作符 LINQ学习第二篇

一、投影操作符 1. Select Select操作符对单个序列或集合中的值进行投影。下面的示例中使用select从序列中返回Employee表的所有列: ...

38550
来自专栏恰童鞋骚年

.NET中那些所谓的新语法之三:系统预定义委托与Lambda表达式

开篇:在上一篇中,我们了解了匿名类、匿名方法与扩展方法等所谓的新语法,这一篇我们继续征程,看看系统预定义委托(Action/Func/Predicate)和超爱...

12730
来自专栏mukekeheart的iOS之旅

判断两个单链表是否相交(有环、无环两种)

题目描述:   给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回false。   给定两个链表的头结...

37870

扫码关注云+社区

领取腾讯云代金券