排序的定义: 对一序列对象根据某个关键字进行排序。
术语说明:
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
- 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
- 内排序：所有排序操作都在内存中完成；
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
- 时间复杂度： 一个算法执行所耗费的时间。
- 空间复杂度：运行完一个程序所需内存的大小。
排序从大的方便可以分为内部排序和外部排序。我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
- 比较排序: 时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
- 非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。 下表给出了常见比较排序算法的性能：
通常有一点我们很容易忽略的是排序算法的稳定性。
排序算法稳定性的简单形式化定义为：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。
对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
例如，对于冒泡排序，原本是稳定的排序算法，如果将记录交换的条件改成A[i] >= A[i + 1]，则两个相等的记录就会交换位置，从而变成不稳定的排序算法。
其次，说一下排序算法稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位排序后元素的顺序在高位也相同时是不会改变的。
本章的所有排序实现类都实现了以下接口:
public interface ISort {
//核心接口
int[] sort(int []data);
//交换
default void swap(int[] data, int i, int j){
data[i] = data[i] ^ data[j];
data[j] = data[i] ^ data[j];
data[i] = data[i] ^ data[j];
}
// 打印数组
default void print(int [] data){
System.out.println("");
for(int i = 0; i < 50; i++){
System.out.print(data[i]);
System.out.print(", ");
}
System.out.println("");
}
}测试代码如下:
public class Main {
public static void main(String[] args) {
// 初始化一个排序类
ISort sort = new MergeSort();
//初始化数组
int[] data = {42, 41, 14, 14, 27, 24, 0, 3, 25, 2, 42, 11, 20, 9, 41, 37, 9, 1, 10, 16, 28, 19, 12, 39, 11, 19, 6, 26, 44, 4, 21, 10, 40, 27, 43, 35, 41, 42, 17, 17, 9, 32, 35, 0, 30, 40, 16, 32, 32, 48};
//排序
sort.sort(data);
//打印排序结果
sort.print(data);
}
}