一、希尔排序
希尔排序是对插入排序的优化。希尔排序的思想：先使用数组中任间隔为h的元素有序，然后对全局进行排序。
h该怎么取值呢？如果数组长度比较小，则可设置 h=3，h=1。若数组长度比较大，可以取 h=4，但最终还是得对全局进行排序：h=1。但如果数组很长呢？则可以设置 h=10，h=4，h=1。那如果再来一个数组更加大的呢？则可以对h=22，h=10，h=4，h=1（全局排序）进行排序。所以说h的取值是一个递增序列。
我们要对一个大规模的数组进行间隔排序，再全局排序（h=1），最终得到有序的数组。
递增序列的取值：
我们用其中最常用的这个。对应的时间复杂度是： 。（不推倒了，记一下）
希尔排序的详细步骤：
data数组有16个元素，下面是对data中的元素进行排序：
h=4时，
开始：i从i=4，即i从数组第5个元素开始；j=i 比较j和j-4，如果是升序的，就不做任何交换了。
下一个元素：i=5，j从i开始，比较j和j-4，看是否需要交换。
...
i=8，j从i开始，将j，j-4，j-8，(间隔为4的元素)的进行排序。排序过程：先将j和j-4比较，看是否需交换；再将j-4和j-8进行比较，看是否需要交换。
....
h=1时，
开始：i从i=1，j从i开始，比较j和j-1，看是否需要交换。
i=2，j从i开始，将j，j-1，j-2，(间隔为1的元素)的进行排序。排序过程：先将j和j-1比较，看是否需交换；再将j-1和j-2进行比较，看是否需要交换。
....
i=13，j从i开始，将j，j-1，j-2，... (间隔为1的元素)的进行排序。排序过程：先将j和j-1比较，看是否需交换；再将j-1和j-2进行比较，看是否需要交换...
代码实现：
public void ShellSort(int[] data) {
if (data == null || data.length <= 1) return;
// 1.计算递增序列：
int n = data.length;
ArrayList<Integer> list = new ArrayList<>();
int k = 1;
int h;
do {
h = ((int)Math.pow(3, k) - 1) / 2;
if (h > n / 3) break;
list.add(h); // 1, 4, 13, 40, 121......
k++;
} while (h <= n / 3);
// 2. 希尔排序
for (k = list.size() - 1; k >= 0; k--) { // 倒叙遍历，
h = list.get(k);
// 将数组变成 h 有序
for (int i= h; i < n; i++) {
// 对j进行操作
for(int j=i; j>=h; j=j-h) {
if (data[j] < data[j - h]) {
swap(data, j , j - h);
} else {
break;
}
}
}
}
}
为了降低空间复杂度，也可以这样写：
public void ShellSort(int[] data) {
if (data == null || data.length <= 1) return;
//1.计算递增序列
int n = data.length;
int h = 1;
while( h < n / 3) h = 3 * h + 1; // 1, 4, 13
// 可能会有一个大于 n/3 的，这里也没关系，不是严格小于 n/3。
//2.希尔排序
while (h >= 1) {
// 将数组变为 h 有序
for (int i = h; i < n; i++) {
for (int j = i; j >= h; j = j - h) {
if (data[j] < data[j - h]) {
swap(data, j , j - h);
} else {
break;
}
}
}
h = h / 3;
}
}
希尔排序的特点：
- 空间复杂度：O(1)，原地排序算法。
- 希尔排序是不稳定的排序。
二、归并排序
什么是归并排序：
讲一个数组从中间分成左右两个部分，
把这两部分中的每部分再分别拆成两部分，直至拆到每个部分只剩一个元素。这时，就可以进行合并了。合并就是从小到大排序。
最后将排序后的部分再排序，并合并在一起。
归并排序的递归性质：
- 每个大问题拆成两个子问题，子问题解决了，大问题就解决了。
- 子问题的求解方式和大问题求解方式一样。
- 存在最小子问题。
- 拆解完，则合并。（将两个有序的数组归并成一个有序的数组）
归并排序基本实现：
public class MergeSorter{
public void MergeSort(int[] data) {
if (data == null || data.length <= 1) return;
//一次性 申请一个和data大小相等的临时数组
// 后面合并的话就不做申请了。
int[] tmp = new int[data.length];
sort(data,0,data.length - 1, tmp);// 大问题
}
// 给子数组进行排序，子问题
private void sort(int[] data, int left,int right,int[] tmp) {
// 终止递归的条件
if (left == right) return;
// 分别对两个子问题求解
int mid = (left + right) / 2;
sort(data, left, mid, tmp);
sort(data, mid + 1, right, tmp);
// 合并两个有序的数组，即合并 [left...mid] 和 [mid + 1, right]
merge2(data, left, mid, right, tmp);
}
// 合并数组：
private void merge (int[] data, int left, int mid, int right,int[] tmp) {
int tmpPos = left;
int i = left;
int j = mid + 1;
// 将左边和右边的元素按照顺序拷贝到临时的数组中
while (i <= mid && j <= right) {
if (data[i] <= data[j]) {
tmp[tmpPos++] = data[i++];
} else { // data[i] > data[j]
tmp[tmpPos++] = data[j++];
}
}
// 如果左边还有元素，则直接将左边的元素拷贝到临时数组
while (i <= mid) {
tmp[tmpPos++] = data[i++];
}
// 如果右边还有元素，则直接将右边的元素拷贝到临时数组
while (j <= right) {
tmp[tmpPos++] = data[j++];
}
// 拷贝，该区间有多少个元素，就拷贝多少个元素。
for (tmpPos = left; tmpPos <= right; tmpPos++) {
data[left++] = tmp[tmpPos];
}
}
}
另一种写法，开始时，将data中元素拷贝到tmp中，再对data中的元素进行操作。
private void merge2(int[] data,int left,int mid,int right,int[] tmp){
for (int i = left; i <= right; i++) {
tmp[i] = data[i];
}
int i = left;
int j = mid + 1;
// k 是对data数组中的元素遍历修改：
for (int k = left; k <= right; k++){
if (i == mid + 1) {
// i为mid+1说明左边部分都遍历完了
// 左边没有元素，右边有元素
data[k] = tmp[j++];
} else if (j == right + 1) {
// j为right+1 说明右边部分都遍历完了
// 左边有元素，右边没有元素
data[k] = tmp[i++];
} else if (tmp[i] <= tmp[j]) {
// 这种情况是左边右边都有元素：
data[k] = tmp[i++];
} else {
// bug 修复：这个是 tmp[j++]
data[k] = tmp[j++];
}
}
}
时间复杂度
归并排序总时间=子序列排好序时间+合并时间
归并排序的特点：
归并排序的空间复杂度是O(n)，不是原地排序算法。
-
归并排序是稳定的排序算法。
因为在合并的时候，如果i和j指向的元素指相同依然是先i后j，这样保证了元素的相对顺序没有变。
自底向上的排序算法：
自底朝上并归排序实现
public void sortBU(int[] data) {
if (data == null || data.length <= 1) return;
int len = data.length;
int[] tmp = new int[len];
for (int size=1; size < len; size += size) {
// size 表示子数组的长度，1,2,4
// 左指针 一定小于 数组的长度 减去 子数组的长度
for (int left = 0;left<len - size; left+=2*size) {
int mid = left + size - 1;
int right = Math.min(left + 2 * size - 1, len - 1);
merge(data, left, mid, right, tmp);
}
}
}
自底向上的归并排序不是重点，把之前的那个自顶向下的归并排序弄精通了就行啦。
三、快速排序
什么是快速排序：
找到一个pivot分区点，将小于分区点的排到pivot前面，将大于分区点的排到pivot后面。
那么，如何将左边的子数组排序？还是在子数组里选择一个分区点，将小于分区点的放到前面，大于分区点的放到后面。
快速排序符合递归的三个条件：
- 每个大问题可拆成两个子问题，子问题解决了，大问题就解决了
- 子问题的求解方式和大问题求解方式一样。
- 存在最小子问题：当子数组只有一个元素的时候。
递推公式：sort(data, lo, hi)
- 分区：int j = partition(data, lo, hi) 其中j 为排序后pivot返回的位置。
- sort(data, lo, j-1) ，sort(data, j+1, hi)
- 递归终止条件：lo>=hi。意思是子数组中没有元素，或子数组中只有一个元素。
快排的代码实现：
public class QuickSorter {
public void sort(int[] data) {
if (data == null || data.length < 2) return;
sort(data, lo, data.length - 1);
}
// 子问题
private void sort(int[] data, int lo, int hi) {
if (lo >= hi) return;
// 分区
int j = partition(data, lo, hi);
// 对左边数组进行排序
sort(data, lo, j-1);
// 对右边数组进行排序
sort(data, j+1, hi);
}
private int partition (int[] data, int lo, int hi) {
int pivot = data[hi];
int less = lo; // less 永远指向小于pivot的下一个元素
int great = lo;
for (; great <= hi - 1; great++) {
if (data[great] < pivot) {
swap(data,less,great);
less++;
}
}
swap(data,less,hi);
return less;
}
public static void main(String[] args) {
int[] data = new int[]{34,33,12,78,21,1,98,100};
new QuickSorter().sort(data);
System.out.println(Arrays.toString(data));
}
}
快速排序的特点：
时间复杂度：
-
空间复杂度是：
，原地排序算法。
注意，并不是原地排序算法的空间复杂度就是O(1)；空间复杂度为O(1)的排序算法，肯定是原地排序算法。
在分区排序中没有申请任何的额外的空间，所以快速排序是原地的排序算法。但因为我们使用递归来进行快速排序，递归调用是需要消耗系统调用栈的，这里会占用额外的空间。 快速排序是一个不稳定的排序算法。
快速排序的优化：
当分区点选择不合理，快排的时间复杂度退化为 。比如，在升序序列中，将最后一个元素设为pivot。
当数组中有大量重复元素，上述方法会增加不必要的排序。
三路切分排序 （三路快排）
public class ThreeWayQuickSorter{
public void sort(int[] data) {
if (data == null || data.length <= 1) return;
sort(data, 0, data.length - 1);
}
private void sort(int[] data, int lo, int hi) {
if (lo >= hi) return;
// 分区
int pivot = data[hi];
int less = lo;
int great = hi;
int i = lo;
while (i <= great) {
if (data[i] < pivot) {
swap(data, i, less);
less++;
i++;
} else if (data[i] > pivot) {
swap(data, i, great);
great--;
} else {
i++;
}
}
sort(data, lo, less - 1);
sort(data, great +1, hi);
}
}
