排序——初级排序算法

た入场券 2022-05-14 00:35 187阅读 0赞

## I. Compare接口 ##

Java中提供了 `Compare` 接口来给我们自定义的数据类型定义排序规则，`Compare` 接口的定义如下，实现该接口需要重写 `compareTo` 方法来定义目标类型对象的自然次序。

public interface Comparable<T> { 
 public int compareTo(T o);
 }

Java中封装的数字类型 `Integer`、`Double` 以及 `String` 和其他许多高级数据类型（如 `File`、`URL`）都实现了 `Compare` 接口。

对于v < w，v = w 和 v > w 三种情况，一般习惯在 `v.compareTo(w)` 被调用时返回一个负整数、零和一个正整数（通常是-1，0 和 1）。如果 v 和 w 无法比较或者两者之一是 *null*，`v.compareTo(w)` 将会抛出一个异常。此外，`compareTo()` 必须实现一个**全序关系**。

<table> 
 <thead> 
 <tr> 
 <th align="center">全序关系</th> 
 <th align="center">描述</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">自反性</td> 
 <td align="center">对于所有v，v=v</td> 
 </tr> 
 <tr> 
 <td align="center">反对称性</td> 
 <td align="center">对于所有vv；且v=w时w=v</td> 
 </tr> 
 <tr> 
 <td align="center">传递性</td> 
 <td align="center">对于所有v、w和x，如果v&lt;=w且w&lt;=x，则v&lt;=x</td> 
 </tr> 
 </tbody> 
</table>

总之，`compareTo()` 实现了我们的主键抽象——它给出了实现了 `Comparable` 接口的任意数据类型的对象的大小顺序关系的定义。举个简单的可比较的自定义类。

import java.util.Arrays;
 
 public class Book implements Comparable<Book> { 
 
 private String name;
 private int page;
 private int price;
 
 public Book(String name, int page, int price) {
 this.name = name;
 this.page = page;
 this.price = price;
 }
 
 @Override
 public int compareTo(Book o) {
 if (this.price < o.price) {
 return -1;
 }
 if (this.price > o.price) {
 return 1;
 }
 if (this.page < o.page) {
 return -1;
 }
 if (this.page > o.page) {
 return 1;
 }
 return 0;
 }
 
 @Override
 public String toString() {
 return "Book{" +
 "name='" + name + '\'' +
 ", page=" + page +
 ", price=" + price +
 '}';
 }
 
 public static void main(String[] args) {
 Book book1 = new Book("book1", 200, 10);
 Book book2 = new Book("book2", 230, 30);
 Book book3 = new Book("book3", 400, 30);
 Book book4 = new Book("book4", 400, 50);
 Book[] books = {book2, book3, book1, book4};
 Arrays.sort(books);
 for (Book book : books) {
 System.out.println(book);
 }
 }
 }

排序结果：  
![排序结果][20180830172801812]

## II. 冒泡排序 ##

#### 冒泡排序思想 ####

1.  比较相邻的元素。如果第一个比第二个大，就交换两个位置；
2.  对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。比较交换完一趟，最后的元素应该是最大的数；
3.  走完一趟确定末尾最大，进行下一趟从第一个元素往后，走到上一趟的最后一个前面结束；
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

#### 动态图演示 ####

![冒泡排序][20180830172837573]

#### 算法实现 ####

public static int[] sort(int[] array) {
 // 外层循环表示所有趟，定义每一趟的终点
 for (int i = array.length - 1; i > 0 ; i--) {
 // 内层循环定义每一趟起点，以及比换的过程
 for (int j = 0; j < i; j++) {
 if (array[j] > array[j + 1]) {
 int temp = array[j];
 array[j] = array[j + 1];
 array[j + 1] = temp;
 }
 }
 }
 return array;
 }

#### 算法评价 ####

<table> 
 <thead> 
 <tr> 
 <th align="center">排序方法</th> 
 <th align="center">平均时间复杂度</th> 
 <th align="center">最坏时间复杂度</th> 
 <th align="center">最好时间复杂度</th> 
 <th align="center">空间复杂度</th> 
 <th align="center">稳定性</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">冒泡排序</td> 
 <td align="center"> O(n2) O ( n 2 ) </td> 
 <td align="center"> O(n2) O ( n 2 ) </td> 
 <td align="center"> O(n) O ( n ) </td> 
 <td align="center"> O(1) O ( 1 ) </td> 
 <td align="center">稳定</td> 
 </tr> 
 </tbody> 
</table>

## III. 选择排序 ##

#### 选择排序思想 ####

1.  找到数组中最小的元素；
2.  将最小的元素与第一个位置上的元素进行交换，这样能够保证首位元素的正确；
3.  找到除第一个以外最小的元素，与第二个位置的元素进行交换；
4.  如此反复，直到与倒数第二个位置上的元素交换完毕，数组排序完成。

#### 动态图演示 ####

![选择排序][20180830172906310]

#### 算法实现 ####

public static int[] sort(int[] array) {
 // 外层循环控制着每一次数组最小值的寻找范围，也就是定义了起点
 for (int i = 0; i < array.length - 1; i++) {
 int minIndex = i;
 // 内存循环寻找最小值所在位置
 for (int j = i; j < array.length; j++) {
 if (array[j] < array[minIndex]) {
 minIndex = j;
 }
 }
 // 交换位置
 int temp = array[i];
 array[i] = array[minIndex];
 array[minIndex] = temp;
 }
 return array;
 }

#### 算法评价 ####

<table> 
 <thead> 
 <tr> 
 <th align="center">排序方法</th> 
 <th align="center">平均时间复杂度</th> 
 <th align="center">最坏时间复杂度</th> 
 <th align="center">最好时间复杂度</th> 
 <th align="center">空间复杂度</th> 
 <th align="center">稳定性</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">选择排序</td> 
 <td align="center"> O(n2) O ( n 2 ) </td> 
 <td align="center"> O(n2) O ( n 2 ) </td> 
 <td align="center"> O(n2) O ( n 2 ) </td> 
 <td align="center"> O(1) O ( 1 ) </td> 
 <td align="center">不稳定</td> 
 </tr> 
 </tbody> 
</table>

*  选择排序的时间复杂度都是 O(n2)  O ( n 2 ) ，这意味着无论是否是已经排好序的数组，这种算法处理时间一样；
 *  选择排序算法的数据移动是最少的，等于数组的长度；
 *  选择排序的不稳定性，在于隔空交换位置时很可能破坏了相同元素间的相对位置，比如 \[12, 20, 16, 12, 1\] 。

## IV. 插入排序 ##

#### 插入排序思想 ####

1.  从第一个元素开始，该元素可以认为已经被排序；
2.  取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.  如果该元素大于扫描的元素，将该元素移到下一位置；
4.  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.  将新元素插入到该位置。过程十分类似扑克牌摸牌插入动作；
6.  重复步骤2~5。

#### 动态图演示 ####

![插入排序][20180830172937119]

#### 算法实现 ####

public static int[] sort(int[] array) {
 // 外层循环选择插入的牌，第一张已经排好
 for (int i = 1; i < array.length; i++) {
 int temp = array[i];
 int j = i;
 // 内存循环从后向前扫描，寻找正确的插入位置
 for (; j > 0 && temp < array[j - 1]; j--) {
 // 元素向后移动腾出位置
 array[j] = array[j - 1];
 }
 array[j] = temp;
 }
 return array;
 }

#### 算法评价 ####

<table> 
 <thead> 
 <tr> 
 <th align="center">排序方法</th> 
 <th align="center">平均时间复杂度</th> 
 <th align="center">最坏时间复杂度</th> 
 <th align="center">最好时间复杂度</th> 
 <th align="center">空间复杂度</th> 
 <th align="center">稳定性</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">插入排序</td> 
 <td align="center"> O(n2) O ( n 2 ) </td> 
 <td align="center"> O(n2) O ( n 2 ) </td> 
 <td align="center"> O(n) O ( n ) </td> 
 <td align="center"> O(1) O ( 1 ) </td> 
 <td align="center">稳定</td> 
 </tr> 
 </tbody> 
</table>

当数组部分有序时，插入排序较快。

## V. 希尔排序 ##

#### 希尔排序思想 ####

1.  选择一个增量序列 *t1，t2，…，tk*，其中 *ti >tj*，***tk=1***；
2.  将数组按照增量 *t1* 进行切分数组，对对应的子数组分别进行排序，最终原数组部分有序；
3.  选择增量为 *t2* 继续重复步骤 2，进一步形成有序数组；
4.  最终增量为 1，相当于执行一次插入排序，排序完成。

#### 动态图演示 ####

![希尔排序][2018083017300098]

#### 算法实现 ####

public static int[] sort(int[] array) {
 // 生成增量序列 1, 4, 7, 10...
 int t = 1;
 while (t < array.length / 3) {
 t = t * 3 + 1;
 }
 
 // 最外层循环控制所有的增量执行一遍，直到为1
 while (t >= 1) {
 // 对于每一个增量形成的子序列进行排序，可以采用之前的排序算法：插入排序
 // 插入排序假设第一个元素是排好的，则从t开始插入
 for (int i = t; i < array.length; i++) {
 int j = i;
 int temp = array[i];
 // 内层循环寻找插入位置，注意j的递减增量和j的结束
 for (; j >= t && array[j - t] > temp; j -= t) {
 array[j] = array[j - t];
 }
 array[j] = temp;
 }
 t /= 3;
 }
 return array;
 }

#### 算法评价 ####

<table> 
 <thead> 
 <tr> 
 <th align="center">排序方法</th> 
 <th align="center">平均时间复杂度</th> 
 <th align="center">最坏时间复杂度</th> 
 <th align="center">最好时间复杂度</th> 
 <th align="center">空间复杂度</th> 
 <th align="center">稳定性</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">希尔排序</td> 
 <td align="center"> O(n1.3) O ( n 1.3 ) </td> 
 <td align="center"> O(n2) O ( n 2 ) </td> 
 <td align="center"> O(n) O ( n ) </td> 
 <td align="center"> O(1) O ( 1 ) </td> 
 <td align="center">不稳定</td> 
 </tr> 
 </tbody> 
</table>

*  由于先进性部分有序的处理，导致希尔排序不稳定；
 *  希尔排序，在大数组排序表现比插入和选择排序要更好；
 *  递增序列的选择，一定程度上影响着希尔排序的性能；
 *  由插入排序到希尔排序，先部分排序的策略使得突破了平方级的运算时间，平均为 O(n1.3)  O ( n 1.3 ) 。

## 参考文章 ##

*  [十大经典排序算法（动图演示）][Link 1]
 *  《算法 第四版》

[20180830172801812]: /images/20220514/9829e7ad1a4d4a4083aa2c8d284d7218.png
[20180830172837573]: /images/20220514/53cf7c3a0dcd4424a69388d279af33dd.png
[20180830172906310]: /images/20220514/25834e525d25484685304c1077dc24cd.png
[20180830172937119]: /images/20220514/f24b562f0d3644b59326b23199ba8cad.png
[2018083017300098]: /images/20220514/44e9ce6e5e644279b7b95c7c177d6dd6.png
[Link 1]: https://www.cnblogs.com/onepixel/p/7674659.html