引言
一直用java,沉溺于面向对象与设计模式,以为那就是编程的一切,以为算法和c语言一样的古老!所以很多问题都止步于java的糖衣炮弹里面!
多次的挣扎后,打开算法导论,细细的从头看起,慢慢的思考!突然豁然明白,算法才是计算机核心科学!不懂算法怎么能说自己是编程的?
Merge Sort
core: divide-conquer-combine
package agri;
public class MergSort {
public static void main(String[] args) {
int[] arr = { 6, 2, 25, 8,58,4,12};
mergeSort(arr, 0, arr.length);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void mergeSort(int arr[], int start, int end) {
if (end-start>1) {
// divide
int length = end - start;
// conquer
mergeSort(arr, start, start + length / 2);
mergeSort(arr, start + length / 2, end);
// merge
merge(arr, start, end);
}
}
public static void merge(int[] arr, int start, int end) {
int size = end - start;
int[] re = new int[size];
int i = 0, k = 0;
int j = size / 2;
// start
while (i < size / 2 && j < size) {
if (arr[start + i] < arr[start + j]) {
re[k++] = arr[start + i];
i++;
} else if (arr[start + i] > arr[start + j]) {
re[k++] = arr[start + j];
j++;
}
}
// end
if (i == size / 2) {
while (j < size) {
re[k++] = arr[start + j];
j++;
}
} else {
while (i < size / 2) {
re[k++] = arr[start + i];
i++;
}
}
//
for(int m=0;m<size;m++){
arr[start+m] = re[m];
}
}
}
这个是经过自己几个迭代才写出来的,所以非常值得反思自己其中的错误历程,以回答为什么不能一气呵成的原因?这个版本和别人实现的不一样,当然碰到的问题是一样的,只是别人用了非常巧妙方法解决了,而我却纠结于整体的正确性,局部采用最笨的方法来实现!
总结:
没有想清楚就动手,自己从来没有写伪代码的习惯,也没有接受写伪代码正规的教育,所以脑袋里面大概有个印象就开始写代码了.在思路不清晰的情况下,也就没有办法去论证算法的正确性!
从后来编写的情况来看,自己主要犯的错误是:前期算法的步骤不正确,后期java语言上犯的一些低级错误!解决办法是,一面看正确代码实现,一面理解自己是如何犯错的,到了最后,就是靠debugger跟踪,发现自己的一些低级错误!
第一版本的最初实现:
package agri;
public class MergeSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {6,2,3,8,4,9};
int[] re = mergeSort(arr);
for(int i:re){
System.out.print(i+" ");
}
}
public static int[] mergeSort(int arr[]){
//divide
int[] beforeHalf = new int[arr.length/2];
int i=0;
int[] afterHalf = new int[arr.length-arr.length/2];
for(;i<arr.length/2;i++)
beforeHalf[i] = arr[i];
for(;i<arr.length;i++)
afterHalf[i-arr.length/2] = arr[i];
//conquer
mergeSort(beforeHalf);
mergeSort(afterHalf);
//merge
return merge(beforeHalf,afterHalf);
}
public static int[] merge(int be[],int af[]){
int i = be.length-1;
int j = af.length-1;
int k = i+j;
int[] re = new int[k+2];
while(i>0&&j>0){
if(be[i]>af[j]){
re[k] = be[i];
i--;
}
else if(be[i]<af[j]){
re[k] = af[j];
j--;
}
k--;
}
if(i==0){
while(j>0){
re[k] = af[j];
k--;
j--;
}
}else{
while(i>0){
re[k] = af[i];
k--;
i--;
}
}
return re;
}
}
这个版本就是生搬硬套了divide-conquer-merge,所以整体算法就是错误的,细节方面碰到的问题有,如此多的重复代码,却不晓得如何的消除!整体的正确性得不到论证,考虑细节的正确性与否都是在做无用功!
所以教训是,如果先用伪代码去论证整体算法思路的正确性,细节暂时不考虑!集中精力从大局入手!而等到我把握大局的时候,已经浪费了好长时间了!
中间的一个版本:
package agri;
public class MergeSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {6,2,3,8,4,9};
mergeSort(arr,0,arr.length);
for(int i:arr){
System.out.print(i+" ");
}
}
public static void mergeSort(int arr[],int start,int end){
//divide
// int[] beforeHalf = new int[arr.length/2];
// int i=0;
// int[] afterHalf = new int[arr.length-arr.length/2];
// for(;i<arr.length/2;i++)
// beforeHalf[i] = arr[i];
// for(;i<arr.length;i++)
// afterHalf[i-arr.length/2] = arr[i];
int length = end - start;
if(length==1)
return;
//conquer
mergeSort(arr,start,start+length/2);
mergeSort(arr,arr.length/2,arr.length-arr.length/2);
//merge
}
public static int[] merge(int[] arr){
int[] re = new int[arr.length];
int i=0,k=0;
int j=arr.length/2;
while(i<arr.length/2||j<arr.length){
if(arr[i]<arr[j]){
re[k++] = arr[i++];
}else if(arr[i]>arr[j]){
re[k++] = arr[j++];
}
}
if(i==arr.length/2){
while(j<arr.length)
re[k++] = arr[j++];
}else{
while(i<arr.length/2)
re[k++] = arr[i++];
}
return re;
}
}
这个版本将陷入无限的死循环,而我却惶惶找不到答案,直到打开debugger跟踪才发现问题!我发现自己如此的依赖debugger,为什么不能第一次就正确呢?现在想起来,应该是实现function特别要注意的是局部变量,都是局部变量引起的错误,关注参数,关注局部变量,认真推敲与思考!但是有时候觉得怎么都无法避免此类错误,只有依赖debugger才能找到!
整体的正确性是千真万确的了,但是程序运行不正常,只有慢慢的一步一步调试了,下面是离最终版本很近的另以版本
package agri;
public class MergSortByMyself {
public static void main(String[] args) {
int[] arr = { 6, 2, 3, 8, 4, 9 };
mergeSort(arr, 0, arr.length);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void mergeSort(int arr[], int start, int end) {
if (end-start>1) {
System.out.println(start+":"+end);
// divide
int length = end - start;
// conquer
mergeSort(arr, start, start + length / 2);
mergeSort(arr, start + length / 2, end);
// merge
merge(arr, start, end);
}
}
public static void merge(int[] arr, int start, int end) {
int size = end - start;
int[] re = new int[size];
int i = 0, k = 0;
int j = size / 2;
// start
while (i < size / 2 || j < size) {
if (arr[start + i] < arr[start + j]) {
re[k++] = arr[start + i];
i++;
} else if (arr[i] > arr[j]) {
re[k++] = arr[start + j];
j++;
}
}
// end
if (i == size / 2) {
while (j < size) {
re[k++] = arr[start + j];
j++;
}
} else {
while (i < size / 2) {
re[k++] = arr[start + i];
i++;
}
}
//
for(int m=0;m<size;m++){
arr[start+m] = re[m];
}
}
}
这个版本犯了两个低级错误!或许最终觉得它们真够低级的,但是发现与探索之旅时间却是如此之长,值得深思啊!
从代码来看,混乱的局部变量,不管是命名和使用上都值得考量,这个错误或许很难避免,但是发现的容易与否在于代码的规范与整齐上,看来花时间整理代码是永远都有必要的!
记得一句印象很深的话:建立在不良的解决方案上,只会带来更多的问题,所以与其在不良解决方案上修改,还不如脚踏实地在正确的道路上一步一步前行!
做一样东西,如果有捷径的话,那么我认为是:规范地慢慢走每一步,因为任何问题都不可避免,可以避免的是犯错的概率!对于算法来说,前期的设计,论证的正确性,实现其规范性,分析与改进,每一步都需要时间去梳理!
分享到:
相关推荐
归并排序(Merge sort)(台灣譯作:合併排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
c++ 分治法合并排序 merge sort c语言 分治法合并排序 merge sort(将cout修改printf 加头文件include "stdio.h")
merge sort 排序 C++ merge sort 算法的C++实现
Merge Sort 算法的C语言实现 linux 下编译;windows下没试过,也许需要改头文件
通过merge-sort算法的实现,掌握外存算法所基于的I/O模型与内存算法基于的RAM模型的区别;理解不同的磁盘访问优化方法是如何提高数据访问性能的。
C#,单向链表(Simply Linked List)的归并排序(Merge Sort)算法与源代码 归并排序法(3Merge Sort,以下简称MS)是分治法思想运用的一个典范。 其主要算法操作可以分为以下步骤: Step 1:将n个元素分成两个含n/...
斯坦福公开课算法1 merge sort 第一节
C#,双向链表(Doubly Linked List)归并排序(Merge Sort)算法与源代码 1 双向链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一...
排序——归并排序(Merge sort)
基于python的排序算法-归并排序Merge Sort
归并排序(Merge Sort)源码及运行示例
算法分析与设计教学课件:Chapter 4 Merge Sort and Recursion.pptx
sql学习 Merge Sort Join优化第4式(保证PGA尺寸).sql
sql学习 Merge Sort Join优化第2式(连接条件索引消除排序).sql
sql学习 Merge Sort Join优化第1式(两表限制条件有索引).sql
sql学习 Merge Sort Join优化第3式(避免取多余列致排序尺寸过大).sql
void merge(int A[],int p,int q,int r);//合并排序算法 /************合并排序算法的实现******************/ int main() { int p,q,r; printf("合并排序算法的实现:\n"); printf("请输入p、q、r的值(输入...