快速排序+归并排序代码回顾
快速排序与归并排序简介:
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;
}