[problem]快速排序和归并排序

最近有时间了解下快速排序和归并排序。

开始觉得很难，一直没有啃这块骨头，现在发现理解了并不难。

快排的思路就是指定一个值，然后将小于他的排到其左边，大于他的排到其右边。

 1 #include <iostream>
 2 #include <set>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 class Solution {
 8 public:
 9     void qsort(vector<int>& nums,int l,int u) {
10         if (l>=u)
11         {
12             return;
13         }
14         int m=l;
15         for(int i=l+1;i<=u;i++)
16         {
17             if (nums[i]<nums[l])
18             {
19                 m++;
20                 swap(nums[m],nums[i]);
21             }
22         }
23         swap(nums[m],nums[l]);
24         qsort(nums,l,m-1);
25         qsort(nums,m+1,u);
26     }
27 };
28 
29 int main()
30 {
31     Solution so;
32     vector<int> input;
33     input.push_back(6);
34     input.push_back(5);
35     input.push_back(3);
36     input.push_back(1);
37     input.push_back(8);
38     input.push_back(7);
39     input.push_back(2);
40     input.push_back(4);
41     so.qsort(input,0,input.size()-1);
42 }

归并利用新空间，将问题化解为各个小部分，边排序边合并。

Merge Sort

 1 #include <iostream>
 2 #include <set>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 class Solution {
 8 public:
 9     void Merge(vector<int>& nums,int p,int q,int r)
10     {
11         int n1 = q-p+1;
12         int n2 = r-q;
13         vector<int> left(n1,0);
14         vector<int> right(n2,0);
15         for(int i=0;i<n1;i++)
16         {
17             left[i]=nums[p+i];
18         }
19         for(int i=0;i<n2;i++)
20         {
21             right[i]=nums[q+i+1];
22         }
23         int i=0,j=0;
24         int k=p;
25         while(i<n1 && j<n2)
26         {
27             if(left[i]<=right[j])
28             {
29                 nums[k++]=left[i++];
30             }
31             else
32             {
33                 nums[k++]=right[j++];
34             }
35         }
36         for(;i<n1;i++)
37         {
38             nums[k++]=left[i];
39         }
40         for(;j<n2;j++)
41         {
42             nums[k++]=right[j];
43         }
44     }
45     void MergeSort(vector<int>& nums,int p,int r)
46     {
47         if(p<r)
48         {
49             int q=(p+r)/2;
50             MergeSort(nums,p,q);
51             MergeSort(nums,q+1,r);
52             Merge(nums,p,q,r);
53         }
54     }
55 };
56 
57 int main()
58 {
59     Solution so;
60     vector<int> input;
61     input.push_back(6);
62     input.push_back(5);
63     input.push_back(3);
64     input.push_back(1);
65     input.push_back(8);
66     input.push_back(7);
67     input.push_back(2);
68     input.push_back(4);
69     so.MergeSort(input,0,input.size()-1);
70 }