排序算法——快速、归并

4、快速排序

快速排序的基本思想是分治，从序列中随机选取一个数，把整个序列中所有比这个数小的放到左半边，把比这个数大的放到右半边，然后再递归的排左半边和右半边。

模版如下，我还没有看懂。。

 1 void quick_sort(vector<int> &q, int l, int r){
 2     if(l >= r) return;
 3     int i = l - 1, j = r + 1, x = q[l + r >> 1];
 4     while(i < j){
 5         do j--; while(q[j] > x);
 6         do i++; while(q[i] < x);
 7         if(i < j) swap(q[i], q[j]);
 8         else quick_sort(q, l, j), quick_sort(q, j+1, r);
 9     }
10 }

5、归并排序

归并排序也是分治的思想，把序列分成等长的两半，先把左半边递归的排好序，再把右半边递归的排好序，这样得到了两个有序的序列，再把它们合并成一个有序的序列。代码依旧是没有看懂。。。

 1 void merge_sort(vector<int> &q, int l, int r){
 2     if(l >= r) return;
 3     int mid = (l + r) / 2;
 4     merge_sort(q, l, mid);
 5     merge_sort(q, mid + 1, r);
 6
 7     static vector<int> w;
 8     w.clear();
 9
10     int i = l, j = mid + 1;
11     while(i <= mid && j <= r){
12         if(q[i] < q[j])
13             w.push_back(q[i++]);
14         else
15             w.push_back(q[j++]);
16     }
17
18     while(i <= mid) w.push_back(q[i++]);
19     while(j <= r) w.push_back(q[j++]);
20     for(i = l, j = 0; j < w.size(); i++, j++) q[i] = w[j];
21 }