欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++ 快排思想 求第k大的数据(3种方法)、第k小的数据(3种方法)

程序员文章站 2024-02-18 15:49:28
...

C++ 快排思想 求第k大的数据(3种方法)、第k小的数据(3种方法)

#include<iostream>
using namespace std;

//找出数组中第k大的数 法1 二路快排1
int quicksort_k_big1(int a[], int l, int r, int k)//从大到小排序
{
    if (l >= r) return a[l];
    int v = a[l];//基准

    //i,j左右分块的初始值, 要保证初始化时,俩个子数组都为空,即,数组右端索引<左端索引
    int i = l + 1;//a[l+1...i-1]>v
    int j = r;//a[j+1...r]<v

    while (true){
        while (i <= r && a[i] > v) ++i;//降序
        while (j >= l + 1 && a[j] < v) --j;
        if (i > j) break;
        swap(a[i], a[j]);
        ++i;
        --j;
    }
    swap(a[l], a[j]);

    if (j == k) return a[j];
    if (j < k) return quicksort_k_big1(a, j + 1, r, k);
    else return quicksort_k_big1(a, l, j - 1, k);
}

//找出数组中第k小的数 法1_1 二路快排1
int quicksort_k_small1_1(int a[], int l, int r, int k)//从大到小排序
{
    if (l >= r) return a[l];
    int v = a[l];//基准

    //i,j左右分块的初始值, 要保证初始化时,俩个子数组都为空,即,数组右端索引<左端索引
    int i = l + 1;//a[l+1...i-1]>v
    int j = r;//a[j+1...r]<v

    while (true){
        while (i <= r && a[i] > v) ++i;//降序
        while (j >= l + 1 && a[j] < v) --j;
        if (i > j) break;//循环结束标志
        swap(a[i], a[j]);
        ++i;
        --j;
    }
    swap(a[l], a[j]);

    int th = r - k;//设定好 降序时 第k小的数 对应 的是 正序时的 第th大的数

    if (j == th) return a[j];
    if (j < th) return quicksort_k_small1_1(a, j + 1, r, k);
    else return quicksort_k_small1_1(a, l, j - 1, k);
}

//找出数组中第k小的数 法1 二路快排1
int quicksort_k_small1(int a[], int l, int r, int k)//从小到大排序
{
    if (l >= r) return a[l];
    int v = a[l];//基准

    //i,j左右分块的初始值 左:a[l+1...i-1]>v 右:a[j+1...r]<v
    int i = l + 1, j = r;

    while (true){
        while (i <= r  && a[i] < v) ++i;
        while (j >= l + 1 && a[j] > v) --j;

        if (i > j) break;//退出while循环

        swap(a[i], a[j]);
        ++i;
        --j;
    }
    swap(a[l], a[j]);

    if (j == k) return a[j];
    if (j < k) return quicksort_k_small1(a, j + 1, r, k);
    else return quicksort_k_small1(a, l, j - 1, k);
}

//找出数组中第k大的数 法1_1 二路快排1
int quicksort_k_big1_1(int a[], int l, int r, int k)//从小到大排序
{
    if (l >= r) return a[l];
    int v = a[l];//基准

    //i,j左右分块的初始值 左:a[l+1...i-1]>v 右:a[j+1...r]<v
    int i = l + 1, j = r;

    while (true){
        while (i <= r  && a[i] < v) ++i;//升序
        while (j >= l + 1 && a[j] > v) --j;

        if (i > j) break;//退出while循环

        swap(a[i], a[j]);
        ++i;
        --j;
    }
    swap(a[l], a[j]);

    int th = r - k;//设定好 升序时 第k大的数 对应 的是 正序时的 第th小的数

    if (j == th) return a[j];//因为基准元素的索引j是正序的,所以,与转换成正序的第th小的数相比较,会更好一些。
    if (j < th) return quicksort_k_big1_1(a, j + 1, r, k);
    else return quicksort_k_big1_1(a, l, j - 1, k);
}

//找出数组中第k大的数 法2 二路快排2
int quicksort_k_big2(int a[], int l, int r, int k)
{
    if (l >= r) return a[l];
    int v = a[l];

    //i,j左右分块的初始值 左:a[l...i-1]>=v 右:a[j...r]<=v
    int i = l, j = r;
    while (i < j)
    {
        while (i < j && a[j] <= v) --j;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] >= v) ++i;
        if (i < j) a[j--] = a[i];
    }
    a[i] = v;
    if (i == k) return a[i];
    if (i < k) return quicksort_k_big2(a, i + 1, r, k);
    else return quicksort_k_big2(a, l, i - 1, k);
}

//找出数组中第k小的数 法2 二路快排2
int quicksort_k_small2(int a[], int l, int r, int k)//从小到大排序
{
    if (l >= r) return a[l];
    int v = a[l];

    //i,j左右分块的初始值 左:a[l...i-1]<=v 右:a[j...r]>=v
    int i = l, j = r;

    while (i < j)
    {
        while (i < j && a[j] >= v) --j;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= v) ++i;
        if (i < j) a[j--] = a[i];
    }
    a[i] = v;

    if (i == k) return a[i];
    if (i < k) return quicksort_k_small2(a, i + 1, r, k);
    else return quicksort_k_small2(a, l, i - 1, k);
}

int main()
{
    int a[] = { 100, 8, 4, 6, 5, 98, 0, 7, 100, 4, 8, 0, 8, 2, 1, 9, 3, 6 };
    int n = sizeof(a) / sizeof(a[0]);

    //测试 二路快排 法1 找出数组中第k大的数 
    cout << "---quicksort_k_big1--------" << endl;
    for (int k = 1; k <= n; ++k)//测试从第1-n的所有数据
        cout << quicksort_k_big1(a, 0, n - 1, k - 1) << "\t";
    cout << endl;

    //测试 二路快排 法3 找出数组中第k大的数 
    cout << "---quicksort_k_big1_1--------" << endl;
    for (int k = 1; k <= n; ++k)//测试从第1-n的所有数据
        cout << quicksort_k_big1_1(a, 0, n - 1, k - 1) << "\t";
    cout << endl;

    //测试 二路快排 法2 找出数组中第k大的数 
    cout << "---quicksort_k_big2--------" << endl;
    for (int k = 1; k <= n; ++k)//测试从第1-n的所有数据
        cout << quicksort_k_big2(a, 0, n - 1, k - 1) << "\t";
    cout << endl;

    //测试 找出数组中第k小的数 法1
    cout << "---quicksort_k_small1--------" << endl;
    for (int k = 1; k <= n; ++k)//测试从第1-n的所有数据
        cout << quicksort_k_small1(a, 0, n - 1, k - 1) << "\t";
    cout << endl;

    //测试 找出数组中第k小的数 法1_1
    cout << "---quicksort_k_small1_1--------" << endl;
    for (int k = 1; k <= n; ++k)//测试从第1-n的所有数据
        cout << quicksort_k_small1_1(a, 0, n - 1, k - 1) << "\t";
    cout << endl;

    //测试 找出数组中第k小的数 法2
    cout << "----quicksort_k_small2-------------------------" << endl;
    for (int k = 1; k <= n; ++k)//测试从第1-n的所有数据
        cout << quicksort_k_small2(a, 0, n - 1, k - 1) << "\t";
    cout << endl;

    return 0;
}

C++ 快排思想 求第k大的数据(3种方法)、第k小的数据(3种方法)

相关标签: 快排的应用