排序算法（二）希尔排序排序算法（二）希尔排序+归并排序归并排序+快速排序快速排序+堆排序堆排序–O(nlogn)的的
排序排序
文章目录文章目录希尔排序归并排序快速排序（20世纪对世界影响最大的算法之一）牛掰！堆排序
希尔排序希尔排序
排序思想：希尔排序可以说是插入排序的一种变种插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正
确的位置就需要 n – 1 次移动。当原数组的一个元素如果距离它正确的位置很远的话，需要与相邻元素交换多次才能到达正确的位置，
这样效率较低。希尔排序就是插入排序排序的一种简单改进，交换不相邻的元素以对数组的局部进行排序，以此来提升效率。
排序过程：
先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2
接着让 h = n / 4，让 h 一直缩小，相当于不断增大步长，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有
序的了。
package sorting;
import java.util.Scanner;
/**
* @ClassName HillSort.java
* @Description 希尔排序
* @Author ZBW
* @Date 2020年03月07日 19:20
**/
public class HillSort {
public static int[] sort(int array[]) {
if (array == null || array.length 0; h /= 2) {
//对各个局部分组进行插入排序
for (int i = h; i 0 && temp < array[k]; k -= h) {
array[k + h] = array[k];
}
array[k + h] = temp;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("请输入待排序数据个数：");
//输入需要排序的数据个数
int n = in.nextInt();
int[] array = new int[n];
System.out.println("请输入待排序数据：");
for (int i = 0; i < n; i++) {
array[i] = in.nextInt();
}
int[] res = sort(array);
print(res);
}
public static void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
时间复杂度为O(nlogn)，空间复杂度：O(1)
属于非稳定排序
属于原地排序
归并排序归并排序
排序思想：将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一
个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。
注意：在一个归并排序中，可以将总的数组中n个元素分成logn个层次个层次，每个层次的合并保持在O(n)的复杂度，那么最后的算法时间复的复杂度，那么最后的算法时间复
杂度为杂度为O(nlogn)
排序过程：
通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了
再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …
直到全部小的数组合并起来。
package sorting;
剩余6页未读，继续阅读
资源评论
