【算法系列01】:快速排序&&归并排序
你需要知道,人的事业就如同浪潮,如果你踩到浪头,功名随之而来;而一旦错失,则终其一生都将受困于浅滩与悲哀。
——《洛克菲勒写给儿子的38封信》
大家好哇,这里是小编记录算法模板的宝地啦,其中也会包含小编平时学习的一些心得。现在,让我们一起进入算法的世界吧~
1.快速排序
找分界点:可以是数据的两端或中间,当然随机值也可。
调整区间:使得一个区间的数据小于一个值,另一个区间的值大于一个值。
递归处理:分别对两个区间进行递归处理。
const int N=1e6+10;
int a[N];
void Sorttest(int l,int r){
if(l>=r){
return ;
}
//判断数据集
int i=l-1,j=r+1;
int x=a[(l+r)/2];
//取中间值
while(i<j){
do i++;while(a[i]<x);
do j--; while(a[j]>x);
if(i<j){
std::swap(a[i],a[j]);
//交换数据
}
}
Sorttest(l,j);Sorttest(j+1,r);
//分别处理两个区间的数据
}
int main(){
using namespace std;
int n,i;
cin>>n;
//输入排序数据集
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
//Sorttest函数进行排序
Sorttest(0,n-1);
//使用循环输出排序后的数据
for(i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}
void Sorttest(int l,int r){
if(l>=r){
return ;
}
int i=l-1,j=r+1;
int x=a[(l+r)/2];
while(i<j){
do i++;while(a[i]<x);
do j--; while(a[j]>x);
if(i<j){
std::swap(a[i],a[j]);
}
}
Sorttest(l,j);Sorttest(j+1,r);
}
2.归并排序
归并排序是一种稳定的排序,而快速排序则是一种不稳定的,归并排序也基于分治。
To:原序列中2个数相同,位置不发生变化我们便说这个排序是稳定的;反之则是不稳定的。
大致思路步骤为:
确定分界点,即mid=(l+r)/2。
递归排序左边和右边。
归并:合二为一,将排序后的数据合并,也是归并排序中最重要的一个环节。
using namespace std;
const int N = 1000010;
int a[N], temp[N], n;
void Sorttest(int a[], int l, int r) {
if (l >= r) {
return;
}
//判断数据集
int mid = l + r >> 1;
//取中间值
Sorttest(a, l, mid);
Sorttest(a, mid + 1, r);
//递归左右两边
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
//排序:比较大小,将较小的数据放入temp数组中
while (i <= mid) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
//判断某一个序列是否未放入temp数组中,并将其放入
for (i = l, j = 0; i <= r; i++, j++) {
a[i] = temp[j];
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
Sorttest(a, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
void Sorttest(int a[], int l, int r) {
if (l >= r) {
return;
}
int mid = l + r >> 1;
Sorttest(a, l, mid);
Sorttest(a, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
while (i <= mid) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (i = l, j = 0; i <= r; i++, j++) {
a[i] = temp[j];
}
}
最后的话:刷题要找自己的不足,然后去专攻。
为你,千千万万遍.
程序员Bob
旨在与大家一起共享学习资源,方法,心得,经验。
Official Account
往期推荐: