Shell排序（希尔排序）算法
Shell排序严格来说基于插入排序的思想，其又称为希尔排序或者缩小增量排序。
Shell排序的流程：
1.将由n个元素的数组分成n/2个数字序列，第1个数据和第n/2+1个数据为一对，......
2.一次循环使每个序列对排序好顺序
3.然后，再变为n/4个序列，再次排序。
4.不断重复上述过程，随着序列减少最后为一个，也就完成整个排序
/**
* Shell排序（希尔排序）
* @author Red Ants(guangboyuan.cn)
* 微信公众号：程序员之路 堆排序
*/
public class ShellSort { public static void shellSort(int[] a) {
int x = 0;
for (int r = a.length / 2; r >= 1; r /= 2) {//分解数组元素为多个序列，每次比较两数的间距，直到其值为0就结束循环
for(int i = r;i<a.length;i++){//按设置的间距r,分别比较对应的数组元素。在该循环中使用插入排序法对指定间距的元素进行排序
int temp = a[i];
int j = i-r;
while (j>=0 && temp <a[j]) {
a[j+r] = a[j];
j-=r;
}
a[j+r] = temp;
}
x++;
System.out.println("第"+x+"步排序结构："+Arrays.toString(a));
}
} public static void main(String[] args) {
int[] nums = new int[]{3,22,77,8,12,54,11,15,2};
System.out.println("排序前："+Arrays.toString(nums));
shellSort(nums);
System.out.println("排序后："+Arrays.toString(nums));
}
}
合并排序算法
是用分治策略实现对N个元素进行排序的算法。其基本思想是：
将待排序元素分成大小大致相同 的两个子集合，分别 对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。
重点：
1.分治的实现
2.合并的实现
分治，就是把整个集合的元素一直除2化分，一直化为到没有两个元素开始合并。
/**
* 合并排序
* @author Red Ants(guangboyuan.cn)
* 微信公众号：程序员之路 堆排序
*/
public class MergeSort { public static void main(String[] args) {
MergeSort m = new MergeSort();
int a[] = { 5, 4, 10, 8, 7, 9, 11 };
System.out.println("排序前："+Arrays.toString(a));
m.mergeSort(a, 0, a.length - 1);
System.out.println("排序后："+Arrays.toString(a));
} public void mergeSort(int[] arrays, int start, int end) {//递归算法
if (start < end) {//出口
int m = (start + end) / 2;
mergeSort(arrays, start, m);
mergeSort(arrays, m + 1, end);
combin_arrays(arrays, start, m, end);
}
} // 合并数组
public void combin_arrays(int[] arrays, int start, int m, int end) {
int length = end - start + 1;
int temp[] = new int[length];// 用来存放比较的数组，用完复制回到原来的数组
int i = start;
int j = m + 1;
int c = 0;
while (i <= m && j <= end) {
if (arrays[i] < arrays[j]) {
temp[c] = arrays[i];
i++;
c++;
} else {
temp[c] = arrays[j];
j++;
c++;
}
}
while (i <= m) {
temp[c] = arrays[i];
i++;
c++;
}
while (j <= end) {
temp[c] = arrays[j];
j++;
c++;
}
c = 0;
for (int t = start; t <= end; t++, c++) {
arrays[t] = temp[c];
}
System.out.println(Arrays.toString(arrays));
}
}