归并排序
定义
归并排序是一种采用分治法,即先使每个子序列有序,再使子序列段间有序,然后合成一个完整的有序表的有效排序方法。
主要步骤
- 划分
- 排序
- 合并
实际过程
实际过程如下图(图片来自百度)
代码
核心代码
- merge()
因为我们在此使用了递归的方式,对于临时数组temp在此函数内不好写,所以为了简洁我们不直接调用该函数,而是再次封装的mergeSort()
//R为排序数组,l为左界,r为右界,temp为临时数组
void merge(int R[],int l, int r,int temp[])
{
//若左右边界相等则返回
if (l == r) return;
//中间位置,位运算右移1位相当于除以2
int mid = (l + r) >> 1;
//为保证[l,mid] [mid+1,r]有序性,我们在此先递归
merge(R,l, mid,temp);
merge(R,mid + 1, r,temp);
//利用临时数组,并从左右区间开头一次取到最小,然后跳过这个数(逆序取大)
int lp = l; //左边区间取到的最小值
int rp = mid + 1; //右边区间取到的最小值
int cnt = 0; //选出的数的个数
while (lp <= mid && rp <= r)
{
temp[cnt] = R[lp] < R[rp] ? R[lp++] : R[rp++];
cnt++;
}
//若做有区间还有剩余的数,则依次把它们装入临时数组
while (lp <= mid)
temp[cnt] = R[lp], lp++, cnt++;
while (rp <= r)
temp[cnt] = R[rp], rp++, cnt++;
//更新数组,register int是将其放到寄存器中以提高效率
for (register int i = l; i <= r; i++)
R[i] = temp[i - l];
}
- mergeSort()
//R为排序数组,l为左界,r为右界
void mergeSort(int R[], int l, int r)
{
if (l >= r) return;
int* temp = (int*)malloc(r - l+1);
merge(R, l, r, temp);
}
调用测试
- main函数
int main()
{
int num[] = { 5,4,3,2,1 };
mergeSort(num,0, 4);
for (int i = 0; i < 5; i++)
cout << num[i] << endl;
return 0;
}
- 输出结果
1
2
3
4
5