排序2：归并排序、快速排序、希尔排序
插入排序、冒泡排序和选择排序都是时间复杂度为O(n^2)的算法。小规模数据比较适合使用，实现相对简单，思想也比较符合直觉。
我们需要更优的，需要更加适合大规模数据的算法。
希尔排序
希尔排序是插入排序的优化。它的核心思想是，将原本的插入排序变成一个多阶段的不同步长的插入排序。
比如，我们有 arr = [9, 8, 7, 6, 5, 4, 3, 2, 1] , 我们选择Knuth步长策略，步长分别是4、1。
那么在第一次，我们逻辑上将步长间隔为4的元素分组，并分别对他们进行插入排序。
- step = 4：分组
[9,5,1],[8,4],[7,3],[6,2]，排序后[1,4,3,2,5,8,7,6,9]。
在第二次，我们将步长为1的元素分组，并对他们进行插入排序。此时就是原始的插入排序了。 - step = 1：退化为插入排序，最终
[1,2,3,4,5,6,7,8,9]
数学分析表明，3x + 1 的Knuth步长序列能使 Shellsort 的时间复杂度接近O(n^{3/2})（优于 O(n²) 的普通插入排序）。
实验证明，Knuth 序列比简单的 **二分步长（如 n/2, n/4, ..., 1）** 更高效。package cn.lishiyuan.algorithm.sort;
import java.util.List;
/**
* 希尔排序
* <br>
* 希尔排序是插入排序的改进。
* <br>
* 希尔排序的思路是选择不一样的步长策略将原本的插入排序变成多阶段的不同步长的插入排序。
*
*/public class ShellSort implements LeeSort{
@Override
public <T extends Comparable<T>> List<T> sort(List<T> data) {
// Knuth 序列步长选择策略
int step = 1;
int length = data.size();
while (step < (length / 3)) {
// 1,4,13,40
step = (step * 3) + 1;
}
for (;step >= 1 ;step = ((step -1) / 3) ) {
for (int i = step; i < length; i++) {
// 将当前元素插入到合适的index
T temp = data.get(i);
// 找出前方合适的index
int j = i;
for (;j >= step; j-=step) {
T left = data.get( j-step );
// 如果当前元素大于需要插入的元素则表示直接放到当前位置就行
if (temp.compareTo(left) > 0) {
break;
}
// 如果当前元素不大于需要插入的元素则向后移动给需要插入的index腾出空间。
data.set(j, data.get(j - step));
}
data.set(j, temp);
}
}
return data;
}
@Override
public <T extends Comparable<T>> T[] sort(T[] data) {
// Knuth 序列步长选择策略
int step = 1;
int length = data.length;
while (step < (length / 3)) {
// 1,4,13,40
step = (step * 3) + 1;
}
for (;step >= 1 ;step = ((step -1) / 3) ) {
for (int i = step; i < length; i++) {
// 将当前元素插入到合适的index
T temp = data[i];
// 找出前方合适的index
int j = i;
for (;j >= step; j-=step) {
T left = data[j-step];
// 如果当前元素大于需要插入的元素则表示直接放到当前位置就行
if (temp.compareTo(left) > 0) {
break;
}
// 如果当前元素不大于需要插入的元素则向后移动给需要插入的index腾出空间。
data[j] = data[j - step];
}
data[j] = temp;
}
}
return data;
}
}空间复杂度
原地排序不消耗额外的空间。空间复杂度为O(1)
稳定性
不稳定。在交换不同步长的元素时，相等元素的相对位置可能发生变化。例如，当使用增量序列（如 Knuth 序列）进行分组排序时，相同值的元素可能被分配到不同的分组中并重新排列，导致稳定性丧失。
时间复杂度
希尔排序的时间复杂度高度依赖于增量序列（步长序列）的选择。
当step为1的时候实际上就是插入排序。时间复杂度是O(n^2)
合理的策略下，希尔排序是优于插入排序的，也就是时间复杂度小于O(n^2)。
希尔排序的研究核心就是步长序列的选择。由于不需要递归，且是原地排序。在资源有不足的环境中可以有限考虑希尔排序。
归并排序
归并排序的思想是将集合分成左右两部分，左右两部分都是已经排好序的子合集，那么我们对这两个子合集进行合并，就可以得到有序合集。而对于子合集的排序也是同样的思想，对子合集也分为左右两个已经排好序的子子合集，然后进行合并，以此类推。
这里使用到了分治思想与递归。分治将大问题分解成小问题，通过解决小问题来解决大问题。分治通常与递归是一起的，大问题与小问题的解决思路是一样的。
我们可以推出归并排序的递推式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))当p=r也就是只有一个元素的时候，此时无需排序，不用再递归再分解了。
归并排序的重点与难点是合并左右两个子集合的实现，算法的主要逻辑也是这个。
package cn.lishiyuan.algorithm.sort;
import java.util.ArrayList;
import java.util.List;
/**
* 归并排序
* <br>
* 归并排序的思路是，将集合分成左右两部分，左右两部分都是已经排好序的，然后将这两部分合集进行合并。
*
*/
public class MergeSort implements LeeSort{
@Override
public <T extends Comparable<T>> List<T> sort(List<T> data) {
mergeSort(data, 0, data.size() - 1);
return data;
}
private <T extends Comparable<T>> void mergeSort(List<T> data, int left, int right) {
// 只有一个元素
if(right == left){
return;
}
// 防止int溢出
int mid = left + (right - left) / 2;
mergeSort(data, left, mid);
mergeSort(data, mid + 1, right);
merge(data, left, right, mid);
}
private static <T extends Comparable<T>> void merge(List<T> data, int left, int right, int mid) {
// 合并数据
int i = left;
int j = mid + 1;
int length = (right - left) +1;
List<T> l = new ArrayList<>(length);
for(int k = 0; k < length; k++){
// 如果左边已经完全到达末尾则将右边放进去就行
if(i > mid){
l.add(data.get(j));
j++;
continue; }
// 如果右边已经完全到达末尾则将左边放进去就行
if(j > right){
l.add(data.get(i));
i++;
continue; }
// 将小的那个放入
if (data.get(i).compareTo(data.get(j)) <= 0) {
l.add(data.get(i));
i++;
}else {
l.add(data.get(j));
j++;
}
}
// 将有序的元素放入原合集
for (int k = 0; k < l.size(); k++) {
data.set((left +k), l.get(k));
}
}
@Override
public <T extends Comparable<T>> T[] sort(T[] data) {
mergeSort(data, 0, data.length - 1);
return data;
}
private <T extends Comparable<T>> void mergeSort(T[] data, int left, int right) {
// 只有一个元素
if(right == left){
return;
}
// 防止int溢出
int mid = left + (right - left) / 2;
mergeSort(data, left, mid);
mergeSort(data, mid + 1, right);
merge(data, left, right, mid);
}
private <T extends Comparable<T>> void merge(T[] data, int left, int right, int mid) {
// 合并数据
int i = left;
int j = mid + 1;
Object[] l = new Object[(right - left) + 1];
for(int k = 0; k < l.length; k++){
// 如果左边已经完全到达末尾则将右边放进去就行
if(i > mid){
l[k] = data[j];
j++;
continue; }
// 如果右边已经完全到达末尾则将左边放进去就行
if(j > right){
l[k] = data[i];
i++;
continue; }
// 将小的那个放入
if (data[i].compareTo(data[j]) <= 0) {
l[k] = data[i];
i++;
}else {
l[k] = data[j];
j++;
}
}
// 将有序的元素放入原合集
for (int k = 0; k < l.length; k++) {
data[ left +k ] = (T) l[k];
}
}
}空间复杂度
在每次合并过程中需要申请一个临时合集（数组）存储元素，旧的临时合集会被回收掉，空间复杂度是O(n)。
稳定性
稳定性取决于合并函数的实现。在我的实现中，元素是从小到大依次放入临时合集（数组）的，没有交换位置，它是稳定的。
时间复杂度
归并排序无论在何时，时间复杂度都是O(nlogn)。
归并排序的时间复杂度为 O(n log n) ，无论输入数据的初始状态如何（最好、最坏或平均情况均一致）。具体分析如下：
- 分割阶段 ：每次将数组分为两半，递归深度为 logn 层。
- 合并阶段 ：每层合并操作需要遍历所有 n 个元素，总时间复杂度为 O(nlogn)
快速排序
快速排序的思想是，选中一个分区元素，将比他大的放到它的右边，比他小的放到它的左边。然后对左右合集分别都进行相同的快速排序，如此递归下去就可以完成排序操作。
假设分区点的index是q，根据分治、递归的处理思想，在分区获取到分区点之后，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。
快速排序的重点与难点是分区点的获取，算法的主要逻辑就是这个。
package cn.lishiyuan.algorithm.sort;
import java.util.List;
/**
* 快速排序
* <br>
* 快速排序的思路是，取一个元素作为分区点，将比这个小的元素放入到该元素的左边，将比这个大的元素放到这个元素右边。
* <br>
* 以此类推，对于每个分区的元素在分区完成后可以进行再分区，如此递归，便可实现快速排序。
*
*/public class QuickSort implements LeeSort{
@Override
public <T extends Comparable<T>> List<T> sort(List<T> data) {
quickSort(data, 0, data.size() - 1);
return data;
}
private <T extends Comparable<T>> void quickSort(List<T> data, int left, int right) {
if (left >= right) {
return;
}
int mid = partition(data, left, right);
quickSort(data, left, mid - 1);
quickSort(data, mid + 1, right);
}
/**
* 分区函数2
* <br>
* 1. 首先将取样，首，尾，中间元素中等大下坡元素作为选中的分区元素
* <br>
* 2. 将该元素交换到首位，也就是left位置。
* <br>
* 3. 使用高位high索引存储等于选中元素的最大index，使用低位low索引存储等于选中元素最小的index
* <br>
* 4. 遍历合集，如果当前元素大于选中元素，则将当前元素与高位元素交换，high--；如果当前元素等于选中元素，则index++。
* 如果当前元素小于选中元素，则当前当前元素与低位交换，low++，index++；
* <br>
* 5. 遍历完成后low就是分区的index
* <br>
*
* @param data
* @param left
* @param right
* @return
* @param <T>
*/
private <T extends Comparable<T>> int partition(List <T> data, int left, int right){
int mid = (right + left) / 2;
int nowIndex;
T selectItem;
T one = data.get(left);
T two = data.get(mid);
T three = data.get(right);
// 选择合适的元素
if (one.compareTo(two) > 0) {
if (two.compareTo(three) > 0) {
selectItem = two;
nowIndex = mid;
} else if (one.compareTo(three) > 0) {
selectItem = three;
nowIndex = right;
} else {
selectItem = one;
nowIndex = left;
}
} else {
if (one.compareTo(three) > 0) {
selectItem = one;
nowIndex = left;
} else if (two.compareTo(three) > 0) {
selectItem = three;
nowIndex = right;
} else {
selectItem = two;
nowIndex = mid;
}
}
// 将选中元素放入left，这相当于将首位置空，留出了一个空位。
data.set(nowIndex, data.get(left));
data.set(left, selectItem);
// // 双指针
// int low = left, high = right;
// for (;low < high;) {
// for (;low < high && data.get(high).compareTo(selectItem) >= 0;) {
// high--;
// }
// data.set(low, data.get(high));
//
// for (;low < high && data.get(low).compareTo(selectItem) < 0;) {
// low++;
// }
// data.set(high, data.get(low));
// }
// // 将选中元素放回到空位
// data.set(low, selectItem);
// nowIndex = low;
// 荷兰国旗算法：通过一次遍历确定区分三部分
int low = left, high = right, i = left;
while (i <= high) {
if (data.get(i).compareTo(selectItem) < 0) {
// 当前元素小于选中元素的时候，将当前元素换到低位（因为left就是选中元素的位置，所以相当于选中元素换到了当前位置）
T temp = data.get(i);
data.set(i, data.get(low));
data.set(low, temp);
low++;
i++;
} else if (data.get(i).compareTo(selectItem) > 0) {
// 如果当前元素大于选中元素，将当前元素换到高位（相当于将最小的右边元素的index换到了当前位置）
T temp = data.get(i);
data.set(i, data.get(high));
data.set(high, temp);
// 注意这里是没有移动i的，也就是当前元素index，没有变化，又因为当前元素是从高位下来的，所以他会被再比较一遍
high--;
} else {
i++;
}
}
// low是最小的等于元素的index，high是最大的等于元素的index
return low; // 返回等于基准的起始索引
}
@Override
public <T extends Comparable<T>> T[] sort(T[] data) {
quickSort(data, 0, data.length - 1);
return data;
}
private <T extends Comparable<T>> void quickSort(T[] data, int left, int right) {
if (left >= right) {
return;
}
int nowIndex = partition(data, left, right);
quickSort(data, left, nowIndex - 1);
quickSort(data, nowIndex + 1, right);
}
/**
* 分区函数1
* <br>
* 1. 首先将取样，首，尾，中间元素中等大下坡元素作为选中的分区元素
* <br>
* 2. 将该元素交换到末尾，也就是right位置。
* <br>
* 3. 使用nowIndex记录分界点，左边是比选中元素小的，右边是比分区元素大的。默认从left开始
* <br>
* 4. 遍历集合，当遇到遇到比选中元素小的元素。则该元素与nowIndex元素交换位置。然后nowIndex++。
* 这就使得nowIndex之前的元素必然是比选中元素小的。
* <br>
* 5. nowIndex元素与末尾元素，也就是选中元素，也就是right位置的元素交换。
* 这样nowIndex元素必然是选中元素，nowIndex之前的元素必然比选中元素小。
*
* @param data
* @param left
* @param right
* @return
* @param <T>
*/
private <T extends Comparable<T>> int partition(T[] data, int left, int right){
int mid = (right + left) / 2;
T selectItem ;
int selectIndex ;
T one = data[left];
T two = data[mid];
T three = data[right];
// 选择合适的元素
if (one.compareTo(two) > 0) {
if (two.compareTo(three) > 0) {
selectItem = two;
selectIndex = mid;
} else if (one.compareTo(three) > 0) {
selectItem = three;
selectIndex = right;
} else {
selectItem = one;
selectIndex = left;
}
} else {
if (one.compareTo(three) > 0) {
selectItem = one;
selectIndex = left;
} else if (two.compareTo(three) > 0) {
selectItem = three;
selectIndex = right;
} else {
selectItem = two;
selectIndex = mid;
}
}
// 将选中元素交换到最右边，这相当于将末位置空，留出了一个空位。
data[selectIndex] = data[right];
data[right] = selectItem;
// 遍历合集，比当前元素小的放到左边，大的放到右边 需要构建两个合集分别存小元素与大元素，这里我们原地分区
// 大小元素的分界点
int nowIndex = left;
for (int i = left ; i <= (right -1); i++) {
if (data[i].compareTo(selectItem) < 0) {
// 当前元素比选中元素小，
T temp = data[nowIndex];
data[nowIndex] = data[i];
data[i] = temp;
nowIndex++;
}
}
// 将选中元素放入分界线
T temp = data[nowIndex];
data[nowIndex] = data[right];
data[right] = temp;
return nowIndex;
}
}空间复杂度
这里的实现是一个原地排序，时间复杂度是O(1)。
稳定性
快速排序是不稳定的，相同元素可能会被划分到不同的分区，且需要交换数据。
时间复杂度
快排的时间复杂度与分区元素有很大的关系。在大多是情况下快排的时间复杂度都是O(nlogn)。在一些极端的情况下，比如每次你都取到了最大或者最小元素会退化成O(n^2)。
这里我们使用三数选中的方法尽量避免极端情况。分区函数
快速排序有两个重点，一是分区元素选择，二是分区逻辑的实现。
我这里使用了三种方式实现分区逻辑。
一是荷兰国旗算法，通过一次遍历，将元素划分为三个部分，low索引之前的是小于分区元素的部分，high索引之后的是大于分区元素的部分，low和high（含low和high）之间的是等于选中元素的部分。
// 荷兰国旗算法：通过一次遍历确定区分三部分
int low = left, high = right, i = left;
while (i <= high) {
if (data.get(i).compareTo(selectItem) < 0) {
// 当前元素小于选中元素的时候，将当前元素换到低位（因为left就是选中元素的位置，所以相当于选中元素换到了当前位置）
T temp = data.get(i);
data.set(i, data.get(low));
data.set(low, temp);
low++;
i++;
} else if (data.get(i).compareTo(selectItem) > 0) {
// 如果当前元素大于选中元素，将当前元素换到高位（相当于将最小的右边元素的index换到了当前位置）
T temp = data.get(i);
data.set(i, data.get(high));
data.set(high, temp);
// 注意这里是没有移动i的，也就是当前元素index，没有变化，又因为当前元素是从高位下来的，所以他会被再比较一遍
high--;
} else {
i++;
}
}
// low是最小的等于元素的index，high是最大的等于元素的index
return low; // 返回等于基准的起始索引二是双指针，通过将大元素放入高位index，小元素放入低位index实现分区，需要注意的是最后要将选择元素放入分区点
int low = left, high = right;
for (;low < high;) {
for (;low < high && data.get(high).compareTo(selectItem) >= 0;) {
high--;
}
data.set(low, data.get(high));
for (;low < high && data.get(low).compareTo(selectItem) < 0;) {
low++;
}
data.set(high, data.get(low));
}
// 将选中元素放回到空位
data.set(low, selectItem);
nowIndex = low;
return nowIndex;三是空位法，最高位index存储中元素，遍历将比选中元素小的放入到左边，同时存储分界点信息，最终遍历完成后分界点与最高位交换便可实现分区
// 遍历合集，比当前元素小的放到左边，大的放到右边 需要构建两个合集分别存小元素与大元素，这里我们原地分区
// 大小元素的分界点
int nowIndex = left;
for (int i = left ; i <= (right -1); i++) {
if (data[i].compareTo(selectItem) < 0) {
// 当前元素比选中元素小，
T temp = data[nowIndex];
data[nowIndex] = data[i];
data[i] = temp;
nowIndex++;
}
}
// 将选中元素放入分界线
T temp = data[nowIndex];
data[nowIndex] = data[right];
data[right] = temp;
return nowIndex;
评论已关闭