ACwing算法笔记一：快排，归并排序

一、快速排序

原题链接

题目描述

给定你一个长度为n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~1e9范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

解题报告

题意理解
这道题目显然是要我们将一个无序数列排序,成为具有升序性质的升序序列.

算法处理
一道排序题目,数据范围是关键,我们发现这道题目只能让我们使用O(nlogn)O(nlogn)的算法,这里我们就使用快速排序.

快排思想图

快速排序思想图

代码实现

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[] , int l , int r)
{
    if (l >= r)   return ;
    
    int x = l + r >> 1 , i = l - 1 , j = r + 1;
    while(i < j)
    {
        do (i ++) ; while (q[i] < q[x]);        //这里不要等号， 不然会报错
        do (j --) ; while (q[j] > q[x]);
        if(i < j)  swap (q[i],q[j]);
    }
    
    quick_sort(q , l , j);         //注意这里的边界问题
    quick_sort(q , j + 1 , r);
}

int main()
{
    cin >> n;
    for (int i = 0 ; i < n ; i ++)   cin >> q[i];
    
    quick_sort(q, 0, n - 1);
    
    for(int i = 0 ; i < n ; i ++)   cout << q[i] << " ";
    cout << endl;
    
    return 0;
}

二、归并排序

题目描述

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~100000范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

解题报告

题意理解
这道题目还是让我们排序,只不过这里强制要求我们使用归并排序,所以既然如此的话,让我们好好地康康这道题目.

算法处理
归并排序,它有两大核心操作.

一个是将数组一分为二,一个无序的数组成为两个数组.

另外一个操作就是,合二为一,将两个有序数组合并成为一个有序数组.

归并排序思想图

代码实现

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n ;
int q[N], tmp[N];

void merge_sort(int q[] , int l , int r )
{
    if (l >= r )  return ;
    
    int mid = l + r >> 1 , i = l , j = mid + 1 , k = 0;    
    //j的取值为mid + 1 , 而不是mid
    
    merge_sort(q, l , mid);
    merge_sort(q, mid + 1, r);
    
    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(int i = 0 , j = l ; j <= r ; i ++ , j ++)   q[j] = tmp[i];
    //***important!  for循环中间的条件要用<= r ,而不能用<n
    
}

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++)   cin >> q[i];
	
    merge_sort(q, 0 , n - 1);
    
    for(int i = 0 ; i < n ; i ++)   cout << q[i] << " ";
    cout << endl;
    
    return 0 ;
}