排序第二记——插入排序(插入、Shell排序)
2017-04-03 本文已影响0人
AceCream佳
这次直入主题，我今天要复习的是插入排序！插入排序分为“直接插入”和“Shell排序”，Shell排序就是希尔排序，可以看做是直接插入排序从成熟体进化为完全体~
好的直接来看插入排序：
直接插入排序
我们先说一下插入排序的原理：
通过对未排序的数据执行逐个插入到合适的位置完成排序工作。
- 1.首先对数组前两个数据进行从小到大排序
- 2.将第三个数据与排好序的两个数据比较，插入合适的位置。
- 3.第四个同样方式插入到他们三个中。
- 4.不断重复，直到结束。
- 时间复杂度： 平均：O(n^2) 最佳：O(n) 最坏：O(n^2)
- 空间复杂度： O(1)
- 稳定性： 稳定
这个听起来比冒泡难一些，但是其实想象力丰富一些，就会觉得这个这个很简单~给个图片就懂了！
我又去百科盗图了：
插入排序
图片的简单明了吧？就是从第二个值开始依次去取。然后每次都比较，然后把每次取的数字，放到该放的位置上。
直接看代码吧：手敲代码：
/**
* Created by AceCream on 2017/3/20.
*
* 插入排序（Insertion Sort）
* 原理：通过对未排序的数据执行逐个插入到合适的位置完成排序工作。
* 1.首先对数组前两个数据进行从小到大排序
* 2.将第三个数据与排好序的两个数据比较，插入合适的位置。
* 3.第四个同样方式插入到他们三个中。
* 4.不断重复，直到结束。
*
* 时间复杂度： 平均：O(n^2) 最佳：O(n) 最坏：O(n^2)
* 空间复杂度： O(1)
* 稳定性： 稳定
*
*/
public class InsertSort {
public static void main(String[] args) {
int value[] = {12,15,9,20,6,31,24};
InsertSort insertSort = new InsertSort();
insertSort.insertSort(value);
System.out.print("最终结果 ");
for (int result : value) {
System.out.print(result+" ");
}
}
private void insertSort(int[] value) {
//temp值待命
int temp;
for (int i=1;i<value.length;i++){
//从第二个数据开始取 每轮的检测数据都先放temp里
temp = value[i];
int j = i-1;
while (j>=0 && temp<value[j]){
//如果比较的值，比temp大，就让这个值往后去。temp继续比较。。。碰到比它小的，就在其后面落下（后面这句是循环外放下的）
value[j+1]=value[j];
j--;
}
//没有比它小的就放回去，有的话就放到应该在的位置
value[j+1]=temp;
}
}
}
我都注释的比较详细了~虽然我自己也总忘这个排序。
好的吃完甜点，我们开始今天的主菜——Shell排序
希尔排序
希尔排序是理论上效率最高的排序。但是！但是仅仅是理论上，因为在实践中的使用，希尔排序还是被快排击败了，两种排序都不太稳定，但是整体的试验中，快排还是略胜一筹~
希尔排序，也叫做缩小增量排序，其执行方式，我个人觉得还是很变态的。
还是看步骤吧：
- 1.将n个元素的数组分为n/2个数字序列：第一个数据和第n/2+1个数据为一对...
- 2.一次循环使每个序列对排好
- 3.变为n/4个序列，再次排序。
- 4.不断重复，周而复始，随着序列变为1，排序完成
希尔排序过程
看这个图，应该是可以理解的，它是分来，然后一一对应，然后比较，单独排序，直到最后，排列整齐。。。
当初觉得这个思想好强！但是！我觉得简单了解其原理就足够了。当然，想手敲也是可以的，但觉得必要性不是那么强，因为应用情况下，我宁可选择快排。
/**
* Created by AceCream on 2017/3/22.
* 希尔排序（ShellSort）
* 希尔排序效率很高！所以也是很常用的一种排序。
* 基于插入排序的思想：缩小增量排序
* 步骤：
* 1.将n个元素的数组分为n/2个数字序列：第一个数据和第n/2+1个数据为一对...
* 2.一次循环使每个序列对排好
* 3.变为n/4个序列，再次排序。
* 4.不断重复，周而复始，随着序列变为1，排序完成
*
* 时间复杂度： 平均：O(n^1.3) 最佳：O(n) 最坏：O(n^2)
* 空间复杂度： O(1)
* 稳定性： 不稳定
*
*/
public class ShellSort {
public static void shellSort(int a[]){
int gap;
int lenth = a.length;
for (gap=lenth/2;gap>0;gap/=2){ //从数组的第gap个元素开始 分出来循环几次
for (int i=0;i<gap;i++){ //分出来有多少组
//直接插入排序
for (int j=i+gap;j<lenth;j+=gap){
if (a[j]<a[j-gap]){
int temp = a[j];
int k = j-gap;
while (k>=0&&temp<a[k]){
a[k+gap]=a[k];
k -= gap;
}
a[k+gap]=temp;
}
}
}
}
}
public static void main(String[] args) {
int value[] = {49,27,46,55,4,13,38,65,97,26};
shellSort(value);
System.out.print("最终结果 ");
for (int result : value) {
System.out.print(result+" ");
}
}
}
这一次我没有选择在线手敲，私下每次我需要使用的时候我会回来看看毕竟学习不是背诵，最主要的是：了解其思想！
