归并排序&快速排序（递归与分治）
--------------------------------------------------------------------------归并排序---------------------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
int a[10000],b[10000];
void hebin(int l,int mid,int r)
{
int p = l,q = mid + 1;
for(int i=l;i<=r;i++)
{
if((q > r) || (a[p] <= a[q] && p <= mid))
{
b[i] = a[p++];
}
else
{
b[i] = a[q++];
}
}
for(int i=l;i<=r;i++)
{
a[i] = b[i];
}
}
void merge_sort(int l,int r)
{
if(l == r) return;
int mid = (l + r) / 2;
merge_sort(l,mid);
merge_sort(mid + 1,r);
hebin(l,mid,r);
}
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
merge_sort(1,n);
for(int i=1;i<=n;i++)
{
cout << a[i];
}
cout << endl;
return 0;
}
------------------------------------------------------------------------------------快速排序---------------------------------------------------------------------------------
方法一 ：
#include<bits/stdc++.h>
using namespace std;
int a[10000],b[10000];
void quick_sort(int *a,int low,int high){ //快排
if(low>=high) return; //若待排序序列只有一个元素，返回空
int i=low; //i作为指针从左向右扫描
int j=high; //j作为指针从右向左扫描
int key=a[low];//第一个数作为基准数
while(i<j)
{
while(a[j]>=key&&i<j)
{ //从右边找小于基准数的元素 （此处由于j值可能会变，所以仍需判断i是否小于j）
j--; //找不到则j减一
}
a[i]=a[j]; //找到则赋值
while(a[i]<=key&&i<j)
{ //从左边找大于基准数的元素
i++; //找不到则i加一
}
a[j]=a[i]; //找到则赋值
}
a[i]=key; //当i和j相遇，将基准元素赋值到指针i处
quick_sort(a,low,i-1); //i左边的序列继续递归调用快排
quick_sort(a,i+1,high); //i右边的序列继续递归调用快排
}
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
quick_sort(a,1,n);
for(int i=1;i<=n;i++)
{
cout << a[i];
}
cout << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int a[10000];
void quick_sort(int l,int r)
{
int key = a[l];
int mid = (l + r) / 2;
int i = l,j = r;
if(l >= r) return;
while(i < j)
{
while(a[j] >= key && j > i)
{
j--;
}
while(a[i] <= key && j > i)
{
i++;
}
if(i < j) swap(a[i],a[j]);
}
a[l] = a[i];
a[i] = key;
quick_sort(l,i-1);
quick_sort(i + 1,r);
}
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
quick_sort(1,n);
for(int i=1;i<=n;i++)
{
cout << a[i];
}
cout << endl;
return 0;
}
快排总结：
回到刚开始的时候提的问题，当选取最左边的数字为基准数的时候，为什么要先从右边开始搜索？ 要回答为什么先从右边开始搜索，不妨我们先从左边开始搜索。比如说“6 1 2 7 9 3 4 5 10 8”的第一轮，我们先让i从左边开始，遇到小于等于6的继续走，大于6的停下，于是i停在了7的位置；再让j从右边走，小于6的时候停下，于是j停在5的位置；这个时候i < j 于是7和5交换位置变成“6 1 2 5 9 3 4 7 10 8”；继续上面的操作，9和4交换，变成“6 1 2 5 4 3 9 7 10 8”，继续，i先走，停在了9的位置，这个时候i == j了，那么这一轮就比较完了，最后需要交换i和base位置的数（基准数归位），这个时候发生了什么？？6与9交换，变成了下面的序列：“9 1 2 5 4 3 6 7 10 8”，这个序列并不是完成了一轮处理之后，基准数左边的都比基准数小，右边的都比它大。所以这样先从左边开始搜索得不到正确结果的。
因此，我们可以得到下面的结论：当基准数选择最左边的数字时，那么就应该先从右边开始搜索；当基准数选择最右边的数字时，那么就应该先从左边开始搜索。不论是从小到大排序还是从大到小排序！
