快速排序+归并排序代码回顾

快速排序与归并排序简介： 

quick_sort为快速排序，merge_sort为归并排序，两者基于分治的思想；

快速排序，简称快排，它以原来数组中的一个值（我们记为x）作为界限，将比它小的元素放到x的左边，大于x的放到x的右边，一遍之后，x就放到了它应该放到的位置，然后对x左侧的子数组做快排，同理，对于x右侧的子数组继续做快排即可；

归并排序，是将数组的中点作为界限，将处于前50%的值放在左一半，将大小处于后50%的值放在右一半。不考虑顺序。一轮过去，我们继续对数组前半边使用归并排序，同理，对于数组右半边使用归并排序。值得注意的是，归并排序一直这样递归下去，数组将不断被分割为大小为1的单个元素数组。前面我们并没有考虑顺序，现在我们使用一个tmp数组，对于两个已经被切割的子数组中的元素进行排序。对于原来两个数组各自使用一个指针从头到尾遍历，谁小谁就放在tmp数组中，遍历完成之后，如果有一个数组没有遍历完，那说明它的值相对于另一个数组来说值较大，我们直接拷贝到tmp数组中即可。这样tmp数组放的肯定就是已经排好序的元素，我们应该把他放到原数组中去，让它参与下一轮比较。

代码一览：

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<assert.h>
using namespace std;void Swap(int* pa, int* pb) {int temp = *pa;*pa = *pb;*pb = temp;
}
void quick_sort(int q[], int l,int r) {if(l >= r)return;int i = l - 1, j = r + 1;int x = q[(l + r) / 2];while (i < j) {do i++; while (q[i] < x);do j--; while (q[j] > x);if (i < j)Swap(&q[i], &q[j]);}quick_sort(q, l, j), quick_sort(q, j+1,r);//不要把这个忘记了！是j而不是i，如果是后者，模板得换;
}
int tmp[100];
void merge_sort(int q[], int l, int r) {if (l >= r)return;int mid = (l + r) / 2;merge_sort(q, l, mid), merge_sort(q, mid + 1, r);int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r) {if (q[i] < q[j])tmp[k++] = q[i++];else tmp[k++] = q[j++];}while (i <= mid) {tmp[k++] = q[i++];}while (j <= r) {tmp[k++] = q[j++];}for (k = 0, i = l; i <= r; k++,i++) {q[i] = tmp[k];}
}
int main() {int arr[] = { 95,1,45,45,454,5,45,62,64,87,84,36,16,1 };int arr2[] = { 95,1,45,45,454,5,45,62,64,87,84,36,16,1 };int len = sizeof(arr) / sizeof(arr[0]);quick_sort(arr, 0, len - 1);merge_sort(arr2, 0, len - 1);for (int i = 0; i < len; i++) {printf("%d ", arr[i]);}puts("");for (int i = 0; i < len; i++) {printf("%d ", arr2[i]);}puts("");return 0;
}

为了保证随机性，我们亦可以在main函数中使用随机数来初始化数组，其他不变：

int main(){int p[10],q[10];srand(time(NULL));for (int i = 0; i < 10; i++) {p[i] = rand() % 999 + 1;q[i] = rand() % 9999 + 1;}for (int i = 0; i < 10; i++) {printf("%d ", p[i]);}puts("");for (int i = 0; i < 10; i++) {printf("%d ", q[i]);}puts("");quick_sort(p, 0, 9);merge_sort(q, 0, 9);puts("");for (int i = 0; i < 10; i++) {printf("%d ", p[i]);}puts("");for (int i = 0; i < 10; i++) {printf("%d ", q[i]);}puts("");return 0;
}