Java排序算法详解及示例汇总——超详细

川长思鸟来 2022-05-23 11:19 225阅读 0赞

> 冒泡排序、选择排序、直接插入排序、二分法排序、希尔排序、快速排序、堆排序、归并排序、基数排序，共9中排序算法详解和代码示例。

![排序算法][1240]

> 示例中全部采用从小到大排序，编码方式为本人理解的思路，算法思想也是自己理解的口语表达方式，若想查看更准确的算法思想和代码示例可直接搜索各算法的百科
> 
> [示例源码地址][Link 1]

### 一、冒泡排序 ###

#### 1、算法思想 ####

1.  两两比较，如果后者比前者大则交换位置
2.  每遍历一圈最大的数就会冒到最后，则确定了本轮比较中的最大值放到最后不动
3.  循环1、2直至遍历完所有

#### 2、代码示例 ####

*  时间复杂度O（n²）

### 二、选择排序 ###

#### 1、算法思想 ####

1.  找到所有数中最大值下标
2.  找到最大值的下标与最后一个位置的数值交换位置，这样每次找到的最大值则固定到最后
3.  循环1、2操作直至遍历找到所有

#### 2、代码示例 ####

*  时间复杂度O（n²），但是由于选择排序每轮比较只交换一次，所以实际性能要优于冒泡

### 三、直接插入排序 ###

#### 1、算法思想 ####

1.  从位置1的数值n开始，将前面已经遍历过的数值集合看成数组m，则将n往m中插入
2.  n插入到集合m中时从后往前比较，如果比n大则往后移一位，如果比较到比n小，则当前位置就是插入n的位置
3.  通过1、2的操作则可以保证每次插入n后m的集合都是排好的序列
4.  循环1、2、3操作将集合中所有数值均插入一遍即排序完成

#### 2、代码示例 ####

*  时间复杂度O（n²）

### 四、二分法排序 ###

*  二分法排序是直接插入排序的改进版本，直接插入排序插入到前方集合中时采用的方式是逐个比较，二分法则是采用二分比较

#### 1、算法思想 ####

1.  从位置1的数值为n，将前面已经遍历过的数值集合看成数组m，则将n往m中插入
2.  n插入到集合m中时采用二分法，先比较m中中间的数值，如果比n大则继续比较后面一半集合的中间的数值，直至比较到拆分的集合中左边一半或者右边一半没有值为止，则当前中间值的位置即为n插入到m中的位置
3.  通过1、2的操作则可以保证每次插入n后m的集合都是排好的序列
4.  循环1、2、3操作将集合中所有数值均插入一遍即排序完成

#### 2、代码示例 ####

*  时间复杂度O(nlogn)

### 五、希尔排序 ###

#### 1、算法思想 ####

1.  定义一个增量m，集合的长度为n，则将集合拆分成n/m组，每组内部进行比较排序
2.  每组内比较的方法无要求，可以用插入或者二分法都行
3.  假如要排序一段集合为\{4，1，2，3\}，定义m为2，则拆分成两组两两比较，即为4和2比，1和3比
4.  因此按照1、2的思路每比较一次都可以将m组内的数值排序
5.  不断变化m的值，多次分组遍历之后即可排序

#### 2、代码示例 ####

*  m的变化方式有多种，不同的变化方式可能排序结果和效率不同。此处示例采用的方式是m=m/2

*  时间复杂度O(nlogn)

### 六、快速排序 ###

#### 1、算法思想 ####

1.  快速排序的思想主要是先设置一个基准点m，这里我们假设每次设置的基准点都是每一组的第一个数值
2.  拿着基准点m在集合中进行比较，找到它应该放置的位置
3.  比较方式主要是定义集合中最左边的下标left，最右边的下标right，从左边开始比较，比m小则left++，找到比m大的则停住，将left下标的值赋值成right下标的值，然后同理比较right，比m大的则right–，找到比m小的就赋值成left下标的值。当left==right之后则比较完成
4.  经过步骤3的比较之后则可以找到m点排序所在的位置，然后集合被分成前后两半，各自按照1、2、3的方式排序，递归至全部拆分比较完成后即排序完成

*  由于步骤3思想较复杂一点，特此引用《啊哈！算法》一书中的插图演示一下，图中以第一个点6为基准点，找到6排序后应该所在的位置

![快速排序][1240 1]

![快速排序][1240 2]

![快速排序][1240 3]

![快速排序][1240 4]

#### 2、代码示例 ####

<table style="border-spacing:0px;width:auto;border:none;margin:0px;"> 
 <tbody> 
 <tr style="height:35px;"> 
 <td style="padding:0px;height:35px;border-style:none;"><pre style="white-space:pre-wrap;font-family:Menlo, Monaco, 'Andale Mono', 'lucida console', 'Courier New', monospace;font-size:.9em;background:rgb(39,40,34);margin-bottom:0px;padding-right:20px;padding-left:0px;color:rgb(102,102,102);line-height:1.5;border:none;text-align:right;">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
</pre></td> 
 <td style="padding:0px;height:35px;border-style:none;"><pre style="white-space:pre-wrap;font-family:Menlo, Monaco, 'Andale Mono', 'lucida console', 'Courier New', monospace;font-size:.9em;background:rgb(39,40,34);margin-bottom:0px;padding-right:0px;padding-left:0px;color:rgb(101,123,131);line-height:1.5;border:none;">private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 快速排序：找到某个点排序之后它应该所在的位置
 */
private void quickSort() {
 
 quickSort(0, array.length - 1);
}

/**
 * 找到开始和结束位置之间以第一个数为基数，这个基数应该所在的位置
 * 找到之后以基数为中心点拆分成前后两段，依次递归进行本操作，直至最后遍历完所有基数为止
 *
 * @param low 开始的点下标
 * @param high 结束的点下标
 */
private void quickSort(int low, int high) {
 
 if (low &gt;= high) {
 
 return;
 }
 int mid = getMiddle(low, high);
 quickSort(low, mid - 1);
 quickSort(mid + 1, high);
}

/**
 * 通过比较获取最开始基数最后所在的位置
 *
 * @param low 最开始的位置
 * @param high 结束的位置
 * @return 最后基数所在的位置
 */
private int getMiddle(int low, int high) {
 
 int temp = array[low];
 while (low &lt; high) {
 
 while (low &lt; high &amp;&amp; array[high] &gt;= temp) {
 
 high--;
 }
 array[low] = array[high];

 while (low &lt; high &amp;&amp; array[low] &lt;= temp) {
 
 low++;
 }
 array[high] = array[low];
 }
 array[low] = temp;
 return low;
}
</pre></td> 
 </tr> 
 </tbody> 
</table>

*  时间复杂度O(nlogn)

### 七、堆排序 ###

#### 1、算法思想 ####

1.  将数组构建成大堆二叉树，即所有节点的父节点的值都大于叶子节点的完全二叉树
2.  若叶子节点比父节点大，则交换位置
3.  根节点即为最大值，则将根节点与最后的的一个叶子节点交换位置
4.  重复1，2操作，每次都找最大值则放置最后即可排序完成

*  由于堆排序运用到了完全二叉树的数据结构，较难理解，特地在网上找了个算法演示的图片参考

![堆排序][strip]

#### 2、代码示例 ####

<table style="border-spacing:0px;width:auto;border:none;margin:0px;"> 
 <tbody> 
 <tr style="height:35px;"> 
 <td style="padding:0px;height:35px;border-style:none;"><pre style="white-space:pre-wrap;font-family:Menlo, Monaco, 'Andale Mono', 'lucida console', 'Courier New', monospace;font-size:.9em;background:rgb(39,40,34);margin-bottom:0px;padding-right:20px;padding-left:0px;color:rgb(102,102,102);line-height:1.5;border:none;text-align:right;">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
</pre></td> 
 <td style="padding:0px;height:35px;border-style:none;"><pre style="white-space:pre-wrap;font-family:Menlo, Monaco, 'Andale Mono', 'lucida console', 'Courier New', monospace;font-size:.9em;background:rgb(39,40,34);margin-bottom:0px;padding-right:0px;padding-left:0px;color:rgb(101,123,131);line-height:1.5;border:none;">private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 堆排序，将数组构建成大堆二叉树，即父节点比叶子节点大的二叉树
 * 从小到大排序的话则每次直接将根节点放置到最后一位，循环往复直至遍历完所有为止
 */
private void heapSort() {
 

 // 先构建一次大堆二叉树，做一个基本的排序
 buildMaxHeap();

 for (int i = array.length - 1; i &gt; 0; i--) {
 
 // 将最大值与最后一个位置的数交换
 exchangeValue(0, i);

 // 重新构建大堆二叉树，从0开始往下检测是否需要重新构建大堆
 maxHeap(i, 0);
 }

}


/**
 * 构建大堆二叉树，从最底层开始往上构建，最底层的父节点则是总长度的一半
 */
private void buildMaxHeap() {
 
 int length = array.length;
 for (int i = length / 2 - 1; i &gt;= 0; i--) {
 
 maxHeap(length, i);
 }
}


/**
 * 构建大堆二叉树的节点，若修改了顺序，则递归重新构建下一层
 *
 * @param length 构建数据数组长度
 * @param node 构建堆排序的父节点
 */
private void maxHeap(int length, int node) {
 
 int left = 2 * node + 1;
 int right = 2 * node + 2;
 // 找到一个节点和他的孩子节点中的最大值下标
 int maxIndex = node;
 if (left &lt; length &amp;&amp; array[left] &gt; array[maxIndex]) {
 
 maxIndex = left;
 }
 if (right &lt; length &amp;&amp; array[right] &gt; array[maxIndex]) {
 
 maxIndex = right;
 }

 // 如果不是父节点最大，则跟最大的孩子节点交换
 if (maxIndex != node) {
 
 exchangeValue(node, maxIndex);
 maxHeap(length, maxIndex);
 }
}



/**
 * 交换两个下标的数值
 *
 * @param first 第一个下标
 * @param second 第二个下标
 */
private void exchangeValue(int first, int second) {
 
 int temp = array[first];
 array[first] = array[second];
 array[second] = temp;
}
</pre></td> 
 </tr> 
 </tbody> 
</table>

*  时间复杂度O(nlogn)

### 八、归并排序 ###

#### 1、算法思想 ####

1.  将数据集合两分拆开
2.  循环拆分至每组只剩一个为止
3.  将拆分的数组进行排序组合
4.  两两合并，直至合并成一个数组即排序完成

*  算法思想参考下图  
    ![归并排序][1240 5]

#### 2、代码示例 ####

<table style="border-spacing:0px;width:auto;border:none;margin:0px;"> 
 <tbody> 
 <tr style="height:35px;"> 
 <td style="padding:0px;height:35px;border-style:none;"><pre style="white-space:pre-wrap;font-family:Menlo, Monaco, 'Andale Mono', 'lucida console', 'Courier New', monospace;font-size:.9em;background:rgb(39,40,34);margin-bottom:0px;padding-right:20px;padding-left:0px;color:rgb(102,102,102);line-height:1.5;border:none;text-align:right;">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
</pre></td> 
 <td style="padding:0px;height:35px;border-style:none;"><pre style="white-space:pre-wrap;font-family:Menlo, Monaco, 'Andale Mono', 'lucida console', 'Courier New', monospace;font-size:.9em;background:rgb(39,40,34);margin-bottom:0px;padding-right:0px;padding-left:0px;color:rgb(101,123,131);line-height:1.5;border:none;">private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 归并排序：将数据集合两分拆开，直至最小之后两两排序合并
 */
private void mergeSort() {
 
 int[] temp = new int[array.length];
 mergeSort(temp, 0, array.length - 1);
}


/**
 * 查分数组，如果数组不能拆分了，则直接返回，拆分之后合并
 */
private void mergeSort(int[] temp, int start, int end) {
 

 if (start &gt;= end) {
 
 return;
 }

 int mid = (start + end) / 2;
 mergeSort(temp, start, mid);
 mergeSort(temp, mid + 1, end);
 mergeArray(temp, start, mid + 1, end);
}


/**
 * 将数组array，以mid为中心，前后两个数组进行合并
 */
private void mergeArray(int[] temp, int start, int mid, int end) {
 

 // 定义指针下标，记录前后段是够可以继续移动
 int minA = start, minB = mid;
 for (int i = start; i &lt;= end; i++) {
 
 if (minA &gt;= mid || minB &gt; end) {
 
 // 如果a或者b用完了，则直接用对方的
 if (minA &gt;= mid) {
 
 temp[i] = array[minB];
 minB++;
 } else {
 
 temp[i] = array[minA];
 minA++;
 }
 } else {
 
 // 都没用完则比较大小
 if (array[minA] &lt; array[minB]) {
 
 temp[i] = array[minA];
 minA++;
 } else {
 
 temp[i] = array[minB];
 minB++;
 }
 }
 }

 System.arraycopy(temp, start, array, start, end - start + 1);
}
</pre></td> 
 </tr> 
 </tbody> 
</table>

*  时间复杂度O(nlogn)

### 九、基数排序 ###

#### 1、算法思想 ####

1.  基数排序又称桶排序，具体思想就是将数值当成数组的下标保存
2.  将所有数值拿出个位来比较，例如值为m的就存入下标为m的数组中
3.  将比较后的数组拿出即为按个位排序好的数组，再将这个排序好的数组按十位排序
4.  比较完个十百千所有位数以后即排序完成

*  步骤一思想参考图  
    ![基数排序][1240 6]

#### 2、代码示例 ####

*  基数排序的时间复杂度为O(d(n+r))，r为基数，d为位数

我有一个微信公众号，经常会分享一些Java技术相关的干货；如果你喜欢我的分享，可以用微信搜索“Java团长”或者“javatuanzhang”关注。

[1240]: /images/20220523/840ea5e5556349ef9d4b33e9d48962c8.png
[Link 1]: https://github.com/lilei644/datastructure-learning-example
[1240 1]: /images/20220523/b881a218aa43443db82d9f815be08fd1.png
[1240 2]: /images/20220523/5156c0364aeb4e0b9846f6d1701c7e5c.png
[1240 3]: /images/20220523/a813c9e70dd643d084b795c47be4ced1.png
[1240 4]: /images/20220523/a2c33ee1f28440d3a462241369f3c45d.png
[strip]: /images/20220523/f8d61dc5273540ef828b50aa1948241d.png
[1240 5]: /images/20220523/4de74617a6634111967fa45ba3acee39.png
[1240 6]: /images/20220523/b476e298c0e54367b06334885323aaba.png