排序算法——快速、归并

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 }

快排的另一种写法如下，其实两种差不多，但也有些微的区别，这种是将基准数先存于tmp中，等基准数两边的数都排好序了，再将基准数归位。

 1 void quicksort(vector<int> &q, int l, int r) 
 2 { 
 3     if(l > r) return;
 4     int i = l, j = r, tmp = q[l]; //tmp中存的就是基准数
 5     while(i != j) { //顺序很重要，要先从右边开始找
 6         while(q[j] >= tmp && i < j) j--;
 7         while(q[i] <= tmp && i < j) i++;       
 8         if(i < j) swap(q[i], q[j]);
 9     }
10     //最终将基准数归位
11     q[l] = q[i];
12     q[i] = tmp;
13     quicksort(l, i-1);//继续处理左边的，这里是一个递归的过程
14     quicksort(i+1, r);//继续处理右边的 ，这里是一个递归的过程
15 }

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 }