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 }
原文：https://www.cnblogs.com/hellosnow/p/11574956.html