SortAlgorithm
Sort Algorithm： ShellSort、QuickSort、MergeSort
SortAlgorithm
四、ShellSort
希尔排序(Shell Sort)是插入排序的一种，又称“缩小增量排序”（DiminishingIncrement Sort），
是直接插入排序算法的一种更高效的改进版本。
思想：
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序；
随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1）插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。（经过一定增量后，数据变得有序，减少了插入排序的次数）
2）但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。（希尔排序则可以移动gap 位）
1.对有序序列在插入时采用交换法
希尔排序需要定义一个增量，这里选择增量为gap=length/2，缩小增量以gap=gap/2的方式，直到增量为为1时，（即插入排序中的增量就为1）
然后进行按增量gap的形式来进行直接插入排序，默认第一个数为有序数，则从该数的下一个增量gap开始进行往前插入，即 i =gap开始往前插入，
（直接插入排序中n个数需要进行n-1次插入），希尔排序则需要 n - gap 次插入，即 int i = gap; i< arr.length; i++；
在直接插入排序中是某个数与其前一个数进行比较，然后判断是否需要往前插入，直到插入到最前面，
希尔排序则是将某个数与其前一个相隔为增量gap的数进行比较看是否需要插入，直到插入到最前面，
int j = i - gap; j >= 0; j -= gap；类比于直接插入排序 int j = i - 1; j >=0; j--；
希尔排序主要是为了实现较好情况（数据部分已经变得有序）插入排序
// 希尔排序 ---》交换法
public static void shellSort(int[] arr) {
int count = 0;
//增量为 gap ，每次为gap = gap/2 ,直到gap为1
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 进行插入，至多需要插入 arr.length - gap次
for (int i = gap; i < arr.length; i++) {
// 步长为 gap
for (int j = i - gap; j >= 0; j -= gap) {
// 判断相差 gap增量 的两数大小关系，是否需要交换
if (arr[j] > arr[j + gap]) {
int temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
System.out.println("希尔排序第"+(++count)+"轮=" + Arrays.toString(arr));
}
}
// 希尔排序---》移位法
public static void shellSort2(int[] arr) {
int count = 0;
// 增量gap，并逐步缩小增量
for (int gap = arr.length / 2; gap > 0 ; gap /= 2) {
// 从第gap个元素，逐个对其所在的组进行插入排序
for (int i = gap; i < arr.length; i++) {
int j = i; // 当前待要插入的数的下标
int temp = arr[j]; // 当前待要插入的数
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
// 移动
arr[j] = arr[j - gap];
j -= gap;
}
// 当退出while后，就给temp找到插入的位置
arr[j] = temp;
}
}
System.out.println("希尔排序第"+(++count)+"轮=" + Arrays.toString(arr));
}
}
希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。
步长（gap）的选择是希尔排序的重要部分，只要最终步长为1任何步长序列都可以工作。
算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。
当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
五、QuickSort
快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1960年提出。
算法思路：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
1、首先设定一个分界值，通过该分界值将数组分成左右两部分。
2、将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，
同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。
当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
概括来说为 挖坑填数 +分治法。（分治：一个复杂的问题分成两个或更多的相同或相似的子问题）
实现方式： 1）挖坑法 2）指针交换法
- 指针交换法
1.找一个基准值（默认为第一个元素），用两个指针分别指向数组的头部和尾部；
2.先从右向左开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
3.再从左向右开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4.交换当前左边指针位置和右边指针位置的元素；
5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
public static void quickSort(int[] arr, int start, int end) {
int left = start; //左下标
int right = end; //右下标
int temp; // 用于交换时的临时变量
if (start > end) {
return;
}
// 记录基准数,并且该语句必须放在 递归终止条件语句下，若数组为6，2，5时处理右边部分start：left+1会索引越界
int pivot = arr[left];
while (left != right) {
// 从右开始查找 比基准数小的数
while(arr[right] >= pivot && left < right) {
right--;
}
// 从左开始查找 比基准数大的数
while (arr[left] <=
pivot && left < right) {
left++;
}
if (left < right) {
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
// 基准数归位
arr[start] = arr[left];
arr[left] = pivot;
quickSort(arr, start, left-1);
quickSort(arr, left + 1, end);
}
- 挖坑法
快速排序的最差时间复杂度和冒泡排序是一样的都是 O(n^2)，它的平均时间复杂度为 O(nlog2n)。
不稳定排序
六、MergeSort
- 归并排序（Merge Sort）：利用归并的思想实现。采用分治(divide-and-conquer)策略
（分治问题将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的解合并在一起，即分而治之）
核心思想：分治。
基本思想
1.把数组从中间划分成两个子数组;
2.一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素
3.依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
治：
当每个小组内部比较出先后顺序以后，小组之间会展开进一步的比较和排序，合并成一个大组；
大组之间继续比较和排序，再合并成更大的组......最终，所有元素合并成了一个有序的集合。
package sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8,4,5,7,1,3,6,2};
int[] temp = new int[arr.length];
System.out.println(Arrays.toString(arr));
mergeSort(arr, 0 , arr.length - 1, temp);
System.out.println(Arrays.toString(arr));
}
// 分
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2; //中间索引
//向左递归进行分解 // 0 --- mid 8 4 5 7 | 8 4 | 8
mergeSort(arr, left, mid, temp);
//向右递归进行分解 // mid+1 --- right 1 3 6 2 |
mergeSort(arr, mid + 1, right, temp);
// 合并
merge(arr, left, mid, right, temp);
}
}
/**
*
* @param arr 排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引，右边有序索引的开始
* @param right 右边索引
* @param temp 中转的数组
*/
// 合并的方法
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 左边有序序列的初始索引
int j = mid + 1; // 右边有序序列的初始索引
int t = 0; // 指向temp数组的当前索引
// 1.先把左右两边(有序)的数据按照规则填到temp数组
// 直到左右两边的有序序列，有一边处理完为止
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
// 2.把有剩余数据的一边的数据依次全部填到temp数组
while (i <= mid) {
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
temp[t] = arr[j];
t++;
j++;
}
// 3.将temp数组的元素拷贝到arr数组
t = 0;
while (left <= right) {
arr[left] = temp[t];
t++;
left++;
}
}
}
时间复杂度： O(nlogn)
空间复杂度： O(n)
归并排序是稳定排序