分治法经典问题——快速排序、归并排序、全排列、二分查找、求第k大元素_排序算法 分类 分治

一、分治法概述

1.设计思想

2.分治法所能解决的问题一般具有以下几个特征

3.求解步骤

二、经典算法

1.快速排序

2.归并排序

3. 全排列

4.二分查找

5.求第k大元素

---

一、分治法概述

1.设计思想

将规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

2.分治法所能解决的问题一般具有以下几个特征：

• 该问题的规模缩小到一定的程度就可以容易地解决。
• 该问题可以分解为若干个规模较小的相同问题。
• 利用该问题分解出的子问题的解可以合并为该问题的解。
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

3.求解步骤

• 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
• 求解子问题：若子问题规模较小而容易被解决则直接求解，否则递归地求解各个子问题。
• 合并：将各个子问题的解合并为原问题的解。
   

二、经典算法

代码注释里有更详细的解释哦

1.快速排序

每次选取第一个数字为pivot，左边的数字均比它大，右边的数字均比它小。

#include <iostream>
#include <algorithm>
using namespace std;
/*
分治法快速排序
*/
void quick_sort(int arr[], int left, int right)
{
    if (left >= right)
        return;
 
    int i = left;
    int j = right;
    int pivot = arr[left];
    while (i < j)
    {
        //从right一直向mid遍历，如果大于pivot就继续，直到找到第一个小于pivot的元素
        while (arr[j] >= pivot && i < j)
            j--;
        //从left一直向mid遍历，如果小于pivot就继续，直到找到第一个小于pivot的元素
        while (arr[i] <= pivot && i < j)
            i++;
        //交换，把小的换到pivot左边，大的换到pivot右边
        if (i < j)
            swap(arr[i], arr[j]);
    }
 
    /*
    pivot回归它正确的位置（左边小，右边大）。
    执行到这句的时侯i和j已经相交了
    此时交换pivot和arr[i](或arr[j] 这俩是一个数）
    */
    swap(arr[left], arr[i]);
 
    //分治法，左右两边再依次进行上述快排
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}
 
int main()
{
    int a[8] = {2, 0, 2, 1, 1, 1, 7, 2};
    quick_sort(a, 0, 7);
    for (int i = 0; i < 8; i++)
        cout << a[i] << ' ';
 
    return 0;
}

运行结果

---

2.归并排序

先二分成单个元素，再相邻元素合并

#include <iostream>
#include <algorithm>
using namespace std;
 
//归并函数
void merge_sort_arr(int arr[], int left, int mid, int right)
{
    int temp[right - left + 1]; // temp作为临时数组 存放临时的值
    int i = left, j = mid + 1, k = 0;
 
    //分成(left,mid)(mid+1,right)两组，从头遍历哪组队头元素更小，选取它进入temp数组
    while (i <= mid && j <= right)
    {
        if (arr[i] < arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
 
    //某组为空，则将后续加入temp数组
    while (i <= mid)
        temp[k++] = arr[i++];
    while (j <= right)
        temp[k++] = arr[j++];
    
    //修改arr数组
    for (int i = 0; i < k; i++)
        arr[left + i] = temp[i];
}
 
//二分函数
void merge_sort(int arr[], int left, int right)
{
    if (left == right)
    {
        return;
    }
    int mid = (left + right) / 2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);
    merge_sort_arr(arr, left, mid, right);
    for (int i = 0; i < 10; i++)
    {
        cout << arr[i] << ' ';
    }
    cout << endl;
}
 
int main()
{
    int arr[10] = {3, 1, 2, 8, 7, 5, 9, 4, 0, 6};
    merge_sort(arr, 0, 9);
}

运行结果

---

3. 全排列

将除了首位的其他元素与首位交换形成暂时首位，固定当前首位，分治剩下位数的全排列，一直分治到数组只剩下一个元素。

{1,2,3}，全排列为(1,2,3)，(1,3,2)，(2,1,3)，(2,3,1)，(3,1,2)，(3,2,1)

#include <iostream>
#include <algorithm>
using namespace std;
 
void perm(int arr[], int j, int k)
{
    if (j == k) // 数组只有一个元素
    {
        for (int i = 0; i <= k; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
    else
    {
        for (int i = j; i <= k; i++)
        {
            swap(arr[i], arr[j]);
            perm(arr, j + 1, k);
            /*
            还原状态，否则再次交换时就不是交换的原来的顺序，
            而是交换过一次的顺序，这样就乱套了
            */
            swap(arr[i], arr[j]);
        }
    }
}
 
int main()
{
    int arr[] = {1, 2, 3};
    perm(arr, 0, 2);
    return 0;
}

运行结果

---

4.二分查找

太经典啦就不过多赘述了

#include <iostream>
#include <algorithm>
using namespace std;
 
//默认已排好序
int binary_search(int arr[],int low,int high,int key)
{
    if(low > high)
        return -1;
    int mid = (low + high) / 2;
 
    if(arr[mid] == key)
        return mid;
    //mid 比目标数大，在左侧区间找
    else if(arr[mid] > key)
        binary_search(arr,low,mid - 1,key);
    //mid 比目标数小，在右侧区间找
    else if(arr[mid] < key)
        binary_search(arr,mid + 1,high,key);
}
 
int main()
{
    int key = 99;
    int arr[10] = {1,23,96,45,21,36,45,99,12,10};
    int ans = binary_search(arr,0,9,key);
    if(ans > 0)
        cout << key << "在数组的下标是：" << ans << endl;
    else
        cout << "没有找到~" << endl;
    return 0;
}

运行结果

---

5.求第k大元素

将数组分为两个区域，左边为比基数小的，右边为比基数小的。令 a[i] 等于目标数，第 k 小数在数组中的下标为[ k-1 ]，所以：

当 k-1= i 时找到第k小数，返回 a[i]的值；

若 k-1 < i，在左区间递归查找；

若 k-1 > i ，在右区间递归查找。

当区间中只有一个元素时，直接返回 a[k-1] 。

#include <iostream>
#include <algorithm>
using namespace std;
 
int number_k(int arr[], int left, int right, int k)
{
    int i = left, j = right;
    // 目标数
    int target;
    // 区间内至少有两个元素
    if (left < right)
    {
        target = arr[left];
        while (i != j)
        {
            // 右边比target小的数字，提前到arr[i]
            while (i < j && arr[j] >= target)
                j--;
            arr[i] = arr[j];
            // 左边比target大的数字，置后于arr[j]
            while (i < j && arr[i] <= target)
                i++;
            arr[j] = arr[i];
        }
        // 第k大的数字下标为k-1
        arr[i] = target;
        if (k - 1 == i)
            return arr[i];
        // 比target小，在左区间递归查找
        else if (k - 1 < i)
            return number_k(arr, left, i - 1, k);
        else
            return number_k(arr, i + 1, right, k);
    }
}
 
int main()
{
    int n = 8;
    int a[] = {2, 3, 1, 4, 5, 7, 8, 6};
    // int k;
    // cout << "input k :" << endl;
    // cin >> k;
    int ans = number_k(a, 0, n - 1, 5);
    // cout << "NO." << k << ":" << ans << endl;
    cout << ans;
    return 0;
}

运行结果