百度移动端网站,网站建设设计思想,电脑ps软件哪个好,百度竞价推广是什么工作快速排序与归并排序简介#xff1a;
quick_sort为快速排序#xff0c;merge_sort为归并排序#xff0c;两者基于分治的思想#xff1b;
快速排序#xff0c;简称快排#xff0c;它以原来数组中的一个值#xff08;我们记为x#xff09;作为界限#xff0c;将比它小…快速排序与归并排序简介
quick_sort为快速排序merge_sort为归并排序两者基于分治的思想
快速排序简称快排它以原来数组中的一个值我们记为x作为界限将比它小的元素放到x的左边大于x的放到x的右边一遍之后x就放到了它应该放到的位置然后对x左侧的子数组做快排同理对于x右侧的子数组继续做快排即可 归并排序是将数组的中点作为界限将处于前50%的值放在左一半将大小处于后50%的值放在右一半。不考虑顺序。一轮过去我们继续对数组前半边使用归并排序同理对于数组右半边使用归并排序。值得注意的是归并排序一直这样递归下去数组将不断被分割为大小为1的单个元素数组。前面我们并没有考虑顺序现在我们使用一个tmp数组对于两个已经被切割的子数组中的元素进行排序。对于原来两个数组各自使用一个指针从头到尾遍历谁小谁就放在tmp数组中遍历完成之后如果有一个数组没有遍历完那说明它的值相对于另一个数组来说值较大我们直接拷贝到tmp数组中即可。这样tmp数组放的肯定就是已经排好序的元素我们应该把他放到原数组中去让它参与下一轮比较。
代码一览
#includeiostream
#includestdlib.h
#includestdio.h
#includestring.h
#includeassert.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, j1,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;
}
