Shell排序算法和合并排序算法

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));
}
}
上一篇:PHP中interface与 implements 关键字


下一篇:下拉菜单制作——利用CSS实现的一个实例