merge-sort-归并排序.doc

//该代码仅仅本人学习算法分析课程时练笔,有很多愚昧之处,望老鸟指点,谢谢!
//归并排序
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

void merge_sort(int *data, int left ,int right);
void merge(int *data, int left, int mid, int right);

int main()
{
int n ;
cout << "Enter the lenght of the list : ";
cin >> n;
int *data = new int[n];
int k = n;
while(k--)
{
cout <<"Enter the " << n - k << " number : ";
cin >> data[n - k - 1];
}

cout << "Before quickSort , the list is :"<< endl;

k = n ;
while(k--)
{
cout << data[n - k - 1] << setw(6) ;
}
cout << endl;

merge_sort(data,0,n-1 );

cout << "After quickSort , the list is : "<< endl;
k = n ;
while(k--)
{
cout << data[n - k - 1] << setw(6) ;
}
cout << endl;

return 0;
}

void merge_sort(int *data , int left, int right)
{
int mid;
if(left < right)
{
mid = (left + right)/2;
merge_sort(data, left, mid);
merge_sort(data, mid + 1, right);
merge(data,left,mid,right);
}
}

void merge(int *data, int left, int mid, int right)
{
int begin1 = left, begin2 = mid + 1, end1 = mid, end2 = right;
int *temp = new int [right - left + 1];
int k = 0;
while(begin1 <= end1 && begin2 <= end2 )
{
if(data[begin1] < data[begin2])
{
temp[k] = data[begin1];
begin1 ++;
}
else
{
temp[k] = data[begin2];
begin2 ++;
}
k++;
}
while(begin2 <= end2)
temp[k++] = data[begin2++];
while(begin1 <= end1)
temp[k++] = data[begin1++];
for(int i = 0; i < right- left + 1; i++ )
data[left+i] = temp[i];
delete temp;
}