算法导论学习之归并排序

客官°小女子只卖身不卖艺 2022-08-26 08:14 138阅读 0赞

惭愧，又好久没看《算法导论》了。上次看《算法导论》的归并排序算法，后来自己写了段代码，实现了算法，不过有问题，一直也没找出问题来。今天趁着礼拜天有时间，调试一下代码。时间不早了，明天还得上班，有时间我会给代码加段注释，以及我在写这段代码的时候，遇到的问题与大家分享，防止大家也犯类似的错误。

// mergeSort.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include "iostream"
    using namespace std;
    void printArray(int a[], int beg, int end) {
    	for (int i = beg; i < end+1; i++) {
    		cout << a[i] << "  ";
    	}
    	cout << endl;
    }
    
    void merge(int a[], int left, int middle, int right) {
    	int leftLen = middle - left + 1;
    	int rightLen = right - middle;
    
    	int* tempLeft = new int[leftLen+1];
    	int* tempRight = new int[rightLen+1];
    
    	for (int i = 0; i < leftLen; i++) {
    		tempLeft[i] = a[left + i];
    	}
    
    	for (int j = 0; j < rightLen; j++) {
    		tempRight[j] = a[j+left+leftLen];
    	}
    
    	tempLeft[leftLen] = 100000;
    	tempRight[rightLen] = 100000;
    
    	int i = 0;
    	int j = 0;
    
    	for (int k = left; k < right+1; k++) {
    		if (tempLeft[i] < tempRight[j]) {
    			a[k] = tempLeft[i];
    			i++;
    		} else {
    			a[k] = tempRight[j];
    			j++;
    		}	
    	}
    	
    
    }
    
    
    void mergeSort(int a[], int left, int right) {
    	int middle = (left+right)/2;
    	if (left < right) {
    		mergeSort(a, left, middle);
    		mergeSort(a, middle+1, right);
    		cout << "before merge:" << endl;
    		printArray(a, left, right);
    
    		merge(a, left, middle, right);
    		cout << "merged:" << endl;
    		printArray(a, left, right);		
    		
    	} 
    	
    }
    
    void test1() {
    	int a[10] = {7, 6, 5, 9, 0, 3, 1, 2, 8, 4};
    	mergeSort(a, 0, 9);
    	cout << "final sort:" << endl;
    	for (int i = 0; i < 10; i++) {
    		cout << a[i] << "  ";
    	}
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])                        
    {
    	test1();
    	
    	int b;
    	cin >> b;
    	return 0;
    }

![20140330232514125][]

[20140330232514125]: /images/20220824/2fa4d8b83c4e4adb920928f8cd120a5f.png