归并排序及其相关问题

1.归并排序：

 1 // mergeSort.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 using namespace std;
 7 
 8 void m_sort(int arr[],int temp[],int lbegin,int rbegin,int rend)
 9 {
10     int lend = rbegin - 1;
11     int tempIndex = lbegin;//重要
12     int len = rend - lbegin + 1;//重要
13 
14     while(lbegin <= lend && rbegin <= rend)
15     {
16         if(arr[lbegin] <= arr[rbegin])
17             temp[tempIndex++] = arr[lbegin++];
18         else
19             temp[tempIndex++] = arr[rbegin++];
20     }
21     while(lbegin <= lend)
22         temp[tempIndex++] = arr[lbegin++];
23     while(rbegin <= rend)
24         temp[tempIndex++] = arr[rbegin++];
25 
26     for(int i = 0;i < len;i++,rend--)//回收元素
27         arr[rend] = temp[rend];
28 }
29 
30 void msort(int arr[],int temp[],int lbegin,int rend)
31 {
32     if(lbegin >= rend)
33         return;
34 
35     int middle = (lbegin + rend)>>1;
36     msort(arr,temp,lbegin,middle);
37     msort(arr,temp,middle+1,rend);
38     m_sort(arr,temp,lbegin,middle+1,rend);
39         /* 分别对左右两边进行递归处理，调用m_sort合并所得的划分*/
40 }
41 
42 void mergeSort(int arr[], int len)
43 {
44     if(len <= 1)
45         return;
46 
47     int *temp = new int[len];//空间复杂度为O(n),时间复杂度为O(logn)
48     if(temp != NULL)
49     {
50         msort(arr,temp,0,len-1);
51         delete[] temp;
52     }
53 }
54 
55 int _tmain(int argc, _TCHAR* argv[])
56 {
57     int arr[] = {1,3,5,7,9,2,4,6,8,10,0};
58     for(int i = 0; i < 11;i++)
59         cout<<arr[i]<<" ";
60     cout<<endl;
61 
62     mergeSort(arr,11);
63 
64     for(int i = 0; i < 11;i++)
65         cout<<arr[i]<<" ";
66     cout<<endl;
67 
68     system("pause");
69     return 0;
70 }

View Code

备注：归并三步：1.temp数组的处理；2.分割原数组；3.将结果合并到temp中，并回拷；

2.计算数组的小和

题目：若有数组arr = {1,3,5,2,4,6},在arr[0]左边小于等于arr[0]的数和为0，在arr[1]左边小于等于arr[1]的数和为1，在arr[2]左边小于等于arr[2]的数和为1+3 = 4，······，s[5]的小和1+3+5+2+4 = 15。整个数组的小和为0+1+4+1+6+15 = 27；

 1 // GetSmallSum1.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 using namespace std;
 7 
 8 void m_sort(int *arr,int* temp, int lbegin,int rbegin,int rend)
 9 {
10     int lend = rbegin - 1;
11     int len = rend - lbegin + 1;
12 
13     int result = 0;
14     int tempIndex = lbegin;
15 
16     while(lbegin <= lend && rbegin <= rend)
17     {
18         if(arr[lbegin] <= arr[rbegin])
19         {
20             result += arr[lbegin]*(rend - rbegin + 1);
21             temp[tempIndex++] = arr[lbegin++];
22         }
23         else
24             temp[tempIndex++] = arr[rbegin++];
25     }
26 
27     while(lbegin <= lend)
28         temp[tempIndex++] = arr[lbegin++];
29     while(rbegin <= rend)
30         temp[tempIndex++] = arr[rbegin++];
31 
32     for(int i = 0; i < len; i++,rend--)
33         arr[rend] = temp[rend];
34 
35     for(int i = 0; i < len;i++)
36         cout<<arr[i]<<" ";
37     cout<<endl;
38     cout<<result<<endl;//result 为每一步递归后的到的结果，并没有全部加起来
39 }
40 
41 void mergeSort(int* arr,int *temp,int left,int right)
42 {
43     if(left >= right)
44         return;
45 
46     int middle = (left + right)>>1;
47     mergeSort(arr,temp,left,middle);
48     mergeSort(arr,temp,middle+1,right);
49     m_sort(arr,temp,left,middle+1,right);
50 }
51 
52 
53 void GetSmallSum(int *arr,int len)
54 {
55     if(arr == NULL || len <= 0)
56         return;
57     int *temp = new int[len];
58     if(temp != NULL)
59     {
60         mergeSort(arr,temp,0,len-1);
61         delete[] temp;
62     }
63 }
64 
65 int _tmain(int argc, _TCHAR* argv[])
66 {
67     int arr[] = {1,3,5,2,4,6};
68     int len = 6;
69     GetSmallSum(arr,len);
70     system("pause");
71     return 0;
72 }

版本1

 1 // GetSmallSum1.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 using namespace std;
 7 
 8 int m_sort(int *arr,int* temp, int lbegin,int rbegin,int rend)
 9 {
10     int lend = rbegin - 1;
11     int len = rend - lbegin + 1;
12 
13     int result = 0;
14     int tempIndex = lbegin;
15 
16     while(lbegin <= lend && rbegin <= rend)
17     {
18         if(arr[lbegin] <= arr[rbegin])
19         {
20             result += arr[lbegin]*(rend - rbegin + 1);
21             temp[tempIndex++] = arr[lbegin++];
22         }
23         else
24             temp[tempIndex++] = arr[rbegin++];
25     }
26 
27     while(lbegin <= lend)
28         temp[tempIndex++] = arr[lbegin++];
29     while(rbegin <= rend)
30         temp[tempIndex++] = arr[rbegin++];
31 
32     for(int i = 0; i < len; i++,rend--)
33         arr[rend] = temp[rend];
34 
35     for(int i = 0; i < len;i++)
36         cout<<arr[i]<<" ";
37     cout<<endl;
38     cout<<result<<endl;//版本1的result 为每一步递归后的到的结果，并没有全部加起来
39     
40     return result;//版本2的result，返回到上一层进行累加
41 }
42 
43 int mergeSort(int* arr,int *temp,int left,int right)
44 {
45     if(left >= right)
46         return 0;
47 
48     int middle = (left + right)>>1;
49     return mergeSort(arr,temp,left,middle)+mergeSort(arr,temp,middle+1,right)+m_sort(arr,temp,left,middle+1,right);
50 }
51 
52 
53 int GetSmallSum(int *arr,int len)
54 {
55     if(arr == NULL || len <= 0)
56         return 0;
57     int *temp = new int[len];
58     if(temp != NULL)
59     {
60         return mergeSort(arr,temp,0,len-1);
61         //delete[] temp;
62     }
63 }
64 
65 int _tmain(int argc, _TCHAR* argv[])
66 {
67     int arr[] = {1,3,5,2,4,6};
68     int len = 6;
69     cout<<GetSmallSum(arr,len)<<endl;
70     system("pause");
71     return 0;
72 }

版本2

备注：版本1的归并排序的方法都是void型，得到的结果为每一步的小和，最后并没有加到一块。版本2在原归并排序原型算法的基础上改动稍多，很好地实现了题目。

3.数组中的逆序对

题目：数组中如果前一个数大于后一个数，则成为一个逆序对，对于给定的数组，请统计出所有的逆序对

 1 // InversePairs.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include<iostream>
 6 using namespace std;
 7 
 8 int m_sort(int* arr,int *temp,int lbegin,int rbegin,int rend)
 9 {
10     int lend = rbegin - 1;
11     int len = rend - lbegin + 1;
12 
13     int tempIndex = rend;
14     int counter = 0;
15 
16     /*
17        前后半段都是从后往前找，并将大数放到temp数组中，同时将指针向前移动
18     */
19     while(lend >= lbegin && rend >= rbegin)
20     {
21         if(arr[lend] > arr[rend])
22         {
23             counter++;
24             cout<<" ("<<arr[lend]<<" "<<arr[rend]<<")"<<endl;
25             temp[tempIndex--] = arr[lend--];
26         }
27         else
28             temp[tempIndex--] = arr[rend--];
29     }    
30     while(lend >= lbegin)
31     {//lend<=>leftEnd ：左半段还有剩余，剩余的数要和后半段的第一个数进行比较
32         if(arr[rbegin] < arr[lend])
33         {
34             counter++;
35             cout<<"("<<arr[lend]<<" "<<arr[rbegin]<<")"<<endl;
36         }
37         temp[tempIndex--] = arr[lend--];
38     }
39         
40     while(rend >= rbegin)
41     {//rend<=>rightEnd:右半段有剩余，剩余的数要和前半段的第一个数进行比较（因为是倒着遍历的）
42         if(arr[rbegin] < arr[lend])
43         {
44             counter++;
45             cout<<"("<<arr[lend]<<" "<<arr[rbegin]<<")"<<endl;
46         }
47         temp[tempIndex--] = arr[rend--];
48     }
49     
50 
51     for(int i = 0;i < len;i++,lbegin++)
52         arr[lbegin] = temp[lbegin];
53 
54     cout<<counter<<endl;
55     return counter;
56 }
57 
58 int InversePairsCore(int* arr,int* temp,int lbegin,int rend)
59 {
60     if(lbegin == rend)
61         return 0;
62 
63     int middle = (lbegin + rend)>>1;
64 
65     int left = InversePairsCore(arr,temp,lbegin,middle);
66     int right = InversePairsCore(arr,temp,middle+1,rend);
67     return left + right + m_sort(arr,temp,lbegin,middle+1,rend);
68 }
69 
70 void InversePairs(int* arr,int len)
71 {
72     if(arr == NULL || len == 0)
73         return;
74 
75     int *temp = new int[len];
76     cout<<"数组中逆序对数为："<<InversePairsCore(arr,temp,0,len-1)<<endl;
77     delete[] temp;
78 }
79 
80 int _tmain(int argc, _TCHAR* argv[])
81 {
82     int arr[] = {7,5,6,4};
83     int len = 4;
84     InversePairs(arr,len);
85     system("pause");
86     return 0;
87 }

版本1

 1 // InversePairs.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include<iostream>
 6 using namespace std;
 7 
 8 int m_sort(int* arr,int *temp,int lbegin,int rbegin,int rend)
 9 {
10     int lend = rbegin - 1;
11     int len = rend - lbegin + 1;
12 
13     int tempIndex = rend;
14     int counter = 0;
15 
16     /*
17        前后半段都是从后往前找，并将大数放到temp数组中，同时将指针向前移动
18     */
19     while(lend >= lbegin && rend >= rbegin)
20     {
21         if(arr[lend] > arr[rend])
22         {
23             temp[tempIndex--] = arr[lend--];
24             counter += rend - rbegin  + 1; 
25             /*
26             比如，处理过程中得到的子数组5、7与4、6，
27             由于之前的处理以使得他们分别
28             有序，如果得到 7 大于 6，那么
29             7 就都大于长度为rend - rbegin  + 1的
30             子数组中的所有元素
31             */
32         }
33         else
34             temp[tempIndex--] = arr[rend--];
35     }    
36     while(lend >= lbegin)
37     {
38         temp[tempIndex--] = arr[lend--];
39     }
40         
41     while(rend >= rbegin)
42     {
43         temp[tempIndex--] = arr[rend--];
44     }
45     
46     for(int i = 0;i < len;i++,lbegin++)
47         arr[lbegin] = temp[lbegin];
48 
49     return counter;
50 }
51 
52 int InversePairsCore(int* arr,int* temp,int lbegin,int rend)
53 {
54     if(lbegin == rend)
55         return 0;    
56 
57     int middle = (lbegin + rend)>>1;
58 
59     int left = InversePairsCore(arr,temp,lbegin,middle);
60     int right = InversePairsCore(arr,temp,middle+1,rend);
61     int counter = m_sort(arr,temp,lbegin,middle+1,rend);
62     return left + right + counter;
63 }
64 
65 void InversePairs(int* arr,int len)
66 {
67     if(arr == NULL || len == 0)
68         return;
69 
70     int *temp = new int[len];
71 
72     cout<<"数组中逆序对数为："<<InversePairsCore(arr,temp,0,len-1)<<endl;
73     delete[] temp;
74 }
75 
76 int _tmain(int argc, _TCHAR* argv[])
77 {
78     int arr[] = {7,5,6,4};
79     int len = 4;
80     InversePairs(arr,len);
81     system("pause");
82     return 0;
83 }

版本2