排序
排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定排序方式排列的算法。基本上，排序算法的输出必须遵守下列两个原则：
- 输出结果为递增序列（递增是针对所需的排序顺序而言）
- 输出结果是原输入的一种排列、或是重组
在本文中，相关算法将用于处理一组随机整数，并将这串整数整理为非递增序列，所有数据将维护在一个ArrayList<Integer>中．对于每个排序算法仅仅讨论其实现及基本原理，不涉及复杂度／稳定性分析．
测试类
为了方便的测试我们写的排序是否能够正确运行，在正式开始写各个算法前不妨写一个测试类以帮助我们快速检查是否排序完成，在该类中我们期望实现以下功能：
- 生成一个长度随机的乱序集合作为测试用例
- 检查给定集合是否为非递增的
randomList()
该方法生成一个长度随机的乱序的ArrayList
为了实现随机长度以及数据，我们需要用到随机数．一般的，首先想到会使用Math类中的random()方法或者是java.util.Random类中的方法来获取，但为了保证测试用例的质量，在这里建议使用java.security.SecureRandom类来实现这一需求，该方法生成的随机数是加密安全的．
关于该类的详细内容不妨参见：SecureRandom 此处不多赘述．
为了防止数据量过大从而导致运行时间太长，因而指定数据量我选择在1 ~ 10^4之间随机取得．
对于运行时间一般只与数据量有关，因而与每个数据的值域范围基本无关，为了数据分布均匀，我选择每个值在1 ~ 10^6中随机取得．
方法实现如下：
public static ArrayList randomList() throws NoSuchAlgorithmException {
SecureRandom randomGetter = SecureRandom.getInstance("SHA1PRNG");
ArrayList result = new ArrayList<>();
for (int random = randomGetter.nextInt(10000); random > 0; random--) {
result.add(randomGetter.nextInt(1000000));
}
return result;
} checkSorted()
该方法遍历集合中的所有数据来判断其是否呈非递增排列
要检查序列是否呈非递增的，只需按序检验相邻两数是否符合规则即可，为了避免多余的遍历，在发现异常相邻数后则会返回False，该方法实现如下：
public static boolean checkSorted(ArrayList list) {
if (list.isEmpty()) {
return true;
}
int key = list.get(0);
for (int i = 1; i < list.size(); i++) {
int num = list.get(i);
if (num < key) {
return false;
}
key = num;
}
return true;
} test()
测试方法
该方法需要使用JUnit包
根据循环数对i个测试用例进行测试，并输出基本信息，实现如下：
@Test
public void test() throws NoSuchAlgorithmException {
for (int i = 1; i <= 3; i++) {
System.out.println("Test Case " + i + " :");
ArrayList list = SortTest.randomList();
long startTime = System.currentTimeMillis();
//此处调用方法对list进行排序
long endTime = System.currentTimeMillis();
System.out.println("\tTime: " + (endTime - startTime) + "ms");
System.out.print("\tList length: " + list.size() + " | ");
try {
TestCase.assertTrue(SortTest.checkSorted(selectSort(list)));
} catch (AssertionError e) {
System.out.println("\tFail!");
}
System.out.println("\tPASS");
System.out.print("\t>> ");
int count = 0;
for (int num : list) {
if (count == 10) {
break;
}
System.out.print(num + " ");
count++;
}
System.out.println("\n");
}
}
插入排序
稳定性：是
时间复杂度：O(n^2)（平均）
插入排序的操作与我们打扑克时理顺手牌进行的操作是基本类似的
不妨将操作分为以下几步：
- 拿取一张牌
- 检查已有序列
- 非递增的插入到手牌中
- 以此类推
每当我们从原序列中选取第i个元素，其前i - 1个元素被认为已被排序，因此我们从位置i处逆序遍历，只需找到一小于该元素的值，再将当前值插入目标索引位置即可．
插入元素时，可以看作将原位置元素摘出，并将原索引位置到目标位置中间的所有值后移一位，最后将当前值置入目标位置即实现一次插入．
如果我们在找到索引位置时再通过遍历集合进行插入操作显然是浪费时间的，简单分析可知只要需要进行插入操作，说明当前值及其前一值必定符合非递增规则．因此，在遍历检查序列的时候就可以进行移位操作，即将前一元素覆盖后一元素，由于我们将要插入的元素摘除并交由外部变量维护，因此每次进行移位空若当前索引空位符合条件直接覆盖即可．
对于遍历条件，由于不需要同待插入元素自身比较，因而从其前一位元素开始遍历即可，每次遍历检查一次相邻数是否符合要求，否则直接退出遍历即可．
基于上述分析，下面给出实现：
public static ArrayList insertSort(ArrayList nums) {
for (int i = 1; i < nums.size(); i++) {
//选取要插入的值
int value = nums.get(i);
int j = i - 1;
//插入前移动操作
for (; j >= 0 && nums.get(j) > value; j--) {
//当前位置值后移
nums.set(j + 1, nums.get(j));
}
//插入值
nums.set(j + 1, value);
}
return nums;
} 动画图示：
冒泡排序
稳定性：是
时间复杂度：O(n^2)（平均）
冒泡排序正如其名，较大的元素逐渐上浮到集合最后端，从而完成其排序过程．
为了实现这一过程，可以理解为要做的事就是不断将乱序序列中的最大值移动至该序列顶端，每次移动完成后，该元素及其之前的元素可认为是有序的，不断对于乱序序列进行如上操作即为冒泡排序的操作进程．
操作可分为以下几步：
- 从头开始，比较两相邻数是否以非递增排列
- 若是则交换两数位置，否则将索引位置后移
- 重复上述过程，直到遍历完整个集合
- 重复遍历过程，直至其有序
对于每次遍历，都应从首位开始进行检查，但由于每完成一次遍历，可认为已被处理后的元素已经有序，因此不必每次都检查已经有序的位置，只需要检查其之外的元素即可．
在完成至多n (n = list.size - 1)次遍历后，即可使序列有序．
下面给出实现：
public static ArrayList bubbleSort(ArrayList nums) {
for (int i = 1; i < nums.size(); i++) {
//每次遍历完成末尾值已经有序
//故仅需遍历 nums.size() - i 次
for (int j = 1; j < nums.size() - i; j++) {
//检查前后两值顺序是否为非递增的
if (nums.get(j) < nums.get(j - 1)) {
//交换两值
Collections.swap(nums, j, j - 1);
}
}
}
return nums;
} 动画图示：
参考文章：
https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
https://oi-wiki.org/basic/sort-intro/
动画图示来自：
https://visualgo.net/zh