1. 排序
下面逐一写上述的排序算法。
注意：稳定和不稳定的依据是，相同的两个值，比如4*（*是为了区分后者的4，没其他特殊含义）， 4，如果在排序前，4*在4的前面，排序后，4*依然在4的前面，则该排序是稳定的排序；否则是不稳定的。
1). 改进的冒泡排序
要点：
- 每轮冒泡不断比较相邻的两个元素，如果它们是逆序的，则交换它们的位置。
- 下一轮冒泡，可以调整未排序的右边界（即边界右边的部分是已经排序了的），减少了不必要的比较。
以数组3，2，1的冒泡排序为例，
第一轮冒泡：
第二轮冒泡：
未排序区域就剩下一个元素，结束。
优化手段：每次循环时，若能确定更合适的右边界，则可以减少很多冒泡轮数。
以数组3， 2， 1，4， 5为例，第一轮结束后记录的x即为右边界：
代码：
public void BubbleSort(int[] nums) {int j = nums.length - 1;int x = 0;while (true) {for (int i = 0; i < j; i++) {if (nums[i] > nums[i + 1]) {int temp = nums[i];nums[i] = nums[i+1];nums[i+1] = temp;x = i;}}// 更新未排序的右边界j = x;// 此时说明已经全部排序完了if (j == 0) {break;}}}2). 选择排序
要点：从数组中选出最大（最小）的元素，交换到合适的位置
public void SelectionSort(int[] nums) {// 从索引nums.length - 1开始比较，如果遇到比它还大的元素就交换// 一共比较nums.length - 1,索引0处不需要比较了// 每次将最大的元素放在后面for (int i = nums.length - 1; i > 0; i--) {int max = i;for (int j = 0; j < i; j++) {if (nums[max] < nums[j]) {max = j;}}swap(nums, max, i);}}private void swap(int[] nums, int i, int j) {int temp;temp = nums[i];nums[i] = nums[j];nums[j] = temp;}3). 堆排序
4). 插入排序
要点：
- 将数组分为两部分[0, low-1], [low, a.length-1]，左边[0, low-1]是已经排序的部分，右边[low, a.length-1]是未排序的部分。
- 每次从未排序区域取出low位置的元素，插入到已经排序区域。
public void InsertSort(int[] nums) {for (int low = 1; low < nums.length; low++) {int t = nums[low];int i = low - 1;// 如果满足条件，即不断把小于low的元素右移while (i >= 0 && t < nums[i]){nums[i+1] = nums[i];i--;}// 找到了插入位置，插入其中if (i != low - 1){nums[i+1] = t;}}}5). 希尔排序（改进的插入排序）
要点：
- 简单的说，就是分组实现插入，每组元素间隙为gap。
- 每轮排序后gap逐渐减小，直至gap为1完成排序。
- 对插入排序的优化，让元素更快速的交换到最终的位置。
推演：
gap = nums.length/2等于4开始，low为4，将5和9进行插入排序，继续将3和8进行插入排序...
gap=gap/2等于2，low为2，1， 5， 9， 7进行插入排序，继续将3， 2， 8， 4进行插入排序....
gap=gap/2等于1，low为1，即普通的插入排序。
图：
代码：
public void ShellSort(int[] nums) {for (int gap = nums.length >> 1; gap >= 1; gap = gap >> 1){for (int low = gap; low < nums.length; low += gap) {int t = nums[low];int i = low - gap;// 如果满足条件，即不断把小于low的元素右移while (i >= 0 && t < nums[i]){nums[i+gap] = nums[i];i -= gap;}// 找到了插入位置，插入其中if (i != low - gap){nums[i+gap] = t;}}}}
