首页 > 编程语言 >算法练习：TopK_1

算法练习：TopK_1

时间：2022-12-07 18:38:52浏览次数：41  
标签：int pArray 练习 nHeap high 算法 TopK low nArray


问题描述

求一维数组中最小的K个数。

 

方法一：排序

先把数组从小到大排序，取前K个数。时间复杂度为O(nlogn)。如果数组过大，机器内存无法同时容纳整个数组，则需要使用外部排序。

以下程序使用的是标准库algorithm中的排序方法----std::sort，代码如下：

//排序法，算法复杂度O(nlogn)
void GetTopK_Sort( int nArray[], int nCount, int k )
{
  //标准库中的排序算法 
  sort( nArray, nArray+nCount );

  if ( K_SIZE <= 20 )
  {
    for( int i = 0; i < k; ++i ) cout << nArray[i] << " ";
    cout << endl << "----------------------------------------" << endl;
  }
}



 

方法二：使用堆

初始化一个大顶堆，然后扫描一遍数组，往堆里插入数据，如果堆的元素个数已经到达K，那么新元素就要和堆顶比较，如果小于堆顶，则移除堆顶，插入新元素；最终我们得到k个最小的元素。时间复杂度为O(nlogk)。

代码实现见后面

 

 

方法三：快速排序思想

使用快速排序分区函数：选择一个数，把数组的数分在两部分，把比选中的数小的或者相等的数移到数组的左边，把比选中的数大的移到数组的右边，返回分区后选中数的下标。

分区结束后，如果返回的下标为K-1，那么左边k个元素即我们所找；如果返回的下标大于K-1，那么我们需要在右半部分找；如果返回的下标小于K-1，则在左半部分继续找。这样重复操作，直到找到分区函数返回的下标为K-1。由于我们并没有实现真正的快速排序，每次只会在两部分中的一部分中查找，而且划分的基准都是随机的，所以算法的平均时间复杂度为O(n)(本人还没太理解这个复杂度是怎么计算得到的，嘿嘿)。

代码说明：由于快速排序在最坏的情况下，时间复杂度为O(n^2)，比如找最小元素时，总是在最大的元素处划分，或者所有元素都相同。所以代码中对分区函数作了一个优化，在一次划分中，记录是否有元素交换，如果没有，说明这部分已经有序，无需在操作下去了。

代码实现见后面

 

代码实现与运行性能对比

代码：

/
//求一维数组中最小的K个数
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdlib>


using namespace std;

#define MAX_TEST      10000/*0000*/   //数据数量
#define K_SIZE        20          //k值
#define SRAND_TEST      7         //随机种子


//排序法，算法复杂度O(nlogn)
void GetTopK_Sort( int nArray[], int nCount, int k )
{
  //标准库中的排序算法 
  sort( nArray, nArray+nCount );

  if ( K_SIZE <= 20 )
  {
    for( int i = 0; i < k; ++i ) cout << nArray[i] << " ";
    cout << endl << "----------------------------------------" << endl;
  }
}



//
//使用堆 O(nlogk)
//数组nHeap的0号单元存放堆的大小

//从底部往上调整成大顶堆
void AdjustHeapFromDown( int nHeap[], int i )
{
  int j = i / 2;
  while( j > 0 )
  {
    if ( nHeap[j] < nHeap[i] )
    {
      int temp = nHeap[j];
      nHeap[j] = nHeap[i];
      nHeap[i] = temp;

      j = j / 2;
    }
    else break;//调整结束（因为是在大顶堆的前提下插入元素）
  }
}

//从上面往下调整成大顶堆
void AdjustHeapFromUp( int nHeap[], int i )
{
  int s = i;
  while ( s <= nHeap[0]/2 )//堆中最后一个非终端叶子结点为nHeap[0]/2
  {
    int m = 2*s;
    if ( (2*s+1) <= nHeap[0] && nHeap[2*s+1] > nHeap[m] ) m = 2*s+1;//右孩子更大

    if ( nHeap[s] < nHeap[m] )
    {
      int temp = nHeap[s];
      nHeap[s] = nHeap[m];
      nHeap[m] = temp;

      //转到下一层
      s = m;
    }
    else
    {
      break;
    }
  }
}

void InsertHeap( int nHeap[], int val, int k )
{
  if ( nHeap[0] < k )
  {
    nHeap[++nHeap[0]] = val;

    AdjustHeapFromDown( nHeap, nHeap[0] );
  }
  else
  {
    //堆个数已达到k，需要和堆顶比较，如果小于堆顶，则移除堆顶，插入新元素
    if ( nHeap[1] > val )
    {
      nHeap[1] = val;
      AdjustHeapFromUp( nHeap, 1 );
    }
  }
}

void GetTopK_Heap( int nArray[], int nCount, int k )
{
  //创建大小为k+1的堆，0号单元放堆的大小
  int* pHeap = new int[k+1];
  pHeap[0] = 0;

  for( int i = 0; i < nCount; ++i )
  {
    InsertHeap( pHeap, nArray[i], k );
  }

  //输出结果 
  if ( K_SIZE <= 20 )
  {
    for( int i = 1; i <= k; ++i ) cout << pHeap[i] << " ";
    cout << endl << "----------------------------------------" << endl;
  }
  

  if ( NULL != pHeap )
  {
    delete pHeap;
    pHeap = NULL;
  }
}






///
//使用快速排序思想
// int Partition( int* pArray, int low, int high )
// {
//  int temp = pArray[low];
//  while( low < high )
//  {
//    while( low < high && pArray[high] >= temp ) --high;
//    pArray[low] = pArray[high];
// 
//    while( low < high && pArray[low] <= temp ) ++low;
//    pArray[high] = pArray[low];
//  }
//  pArray[low] = temp;
// 
//  return low;
// }


//int PartitionRandom( int* pArray, int low, int high )
int PartitionRandom( int* pArray, int low, int high, bool& bLeftSwap, bool& bRightSwap )
{
  //随机产生基准元素
  int i = low + rand() % (high-low);
  int temp = pArray[i];
  pArray[i] = pArray[low];
  pArray[low] = temp;

  temp = pArray[low];
  bLeftSwap = bRightSwap = false;
  while( low < high )
  {
    while( low < high && pArray[high] >= temp )
    {
      --high;//同时进行起泡操作。。。
      if ( !bRightSwap &&/* pArray[high] >= temp &&*/ high != low && pArray[high] > pArray[high+1] ) 
      {
        bRightSwap = true;
        int temp2 = pArray[high];
        pArray[high] = pArray[high+1];
        pArray[high+1] = temp2;
      }
    }
    //pArray[low] = pArray[high];
    if ( pArray[low] != pArray[high] )
    {
      pArray[low] = pArray[high];
      bRightSwap = true;
    }
    

    while( low < high && pArray[low] <= temp ) 
    {
      ++low;//同时进行起泡操作。。。
      if ( !bLeftSwap &&/* pArray[low] <= temp && */low != high && pArray[low] < pArray[low-1] )
      {
        bLeftSwap = true;
        int temp2 = pArray[low];
        pArray[low] = pArray[low-1];
        pArray[low-1] = temp2;
      }
    }
    //pArray[high] = pArray[low];
    if ( pArray[high] != pArray[low] )
    {
      pArray[high] = pArray[low];
      bLeftSwap = true;
    }
    
  }
  pArray[low] = temp;

  return low;
}


void QSortSelectK( int nArray[], int low, int high, int k )
{
  if ( low < high )
  {
    bool bLeftSwap = false;
    bool bRightSwap = false;
    int pivot = PartitionRandom( nArray, low, high, bLeftSwap, bRightSwap );
    if ( pivot == k-1 ) return;
    else if ( pivot > k-1 )
    {
      if ( !bLeftSwap ) return;
      QSortSelectK( nArray, low, pivot-1, k );
    }
    else
    {
      if ( !bRightSwap ) return;
      QSortSelectK( nArray, pivot+1, high, k );
    }
  }
}

void GetTopK_QSort( int nArray[], int nCount, int k )
{
//  //int pivot = Partition( nArray, 0, nCount - 1 );
//  int pivot = PartitionRandom( nArray, 0, nCount - 1 );
//  while( pivot != k - 1 )
//  {
//    if ( pivot > k - 1 )
//    {
//      //pivot = Partition( nArray, 0, pivot - 1 );
//      pivot = PartitionRandom( nArray, 0, pivot - 1 );
//    }
//    else
//    {
//      //pivot = Partition( nArray, pivot + 1, nCount - 1 );
//      pivot = PartitionRandom( nArray, pivot + 1, nCount - 1 );
//    }
//  }
  QSortSelectK( nArray, 0, nCount-1, k );


  //结果输出
  if ( K_SIZE <= 20 )
  {
    for( int i = 0; i < k; ++i ) cout << nArray[i] << " ";
    cout << endl << "----------------------------------------" << endl;
  }
  
}

//生成测试数据
void RandomTestData( int* pArray, int nCount )
{
  for( int i = 0; i < nCount; ++i ) pArray[i] = rand()%100000000;
  //for( int i = 0; i < nCount; ++i ) pArray[i] = nCount-i;
  //for( int i = 0; i < nCount; ++i ) pArray[i] = 2;
  //for( int i = 0; i < nCount; ++i ) pArray[i] = i;
}



void PrintArray( int nArray[], int nCount )
{
  for( int i = 0; i < nCount; ++i )
  {
    cout << nArray[i] << " ";
  }
  cout << endl;
}

int main()
{
  clock_t start, finish;    
  double duration = 0.0;

//    int nArray1[] = { 1, 2, 3, 4 };
//  QuickSort( nArray1, 0, _countof(nArray1)-1 );
//  PrintArray( nArray1, _countof(nArray1) );

//  GetTopK_Sort( nArray1, _countof(nArray1), 10 );
// 
//    int nArray2[] = { 2, 1, 56, 34, 23, 56, 12, 10, 6, 4, 19, 22, 89, 3, 5, 7 };
//  GetTopK_QSort( nArray2, _countof(nArray2), 5 );
//  GetTopK_Heap( nArray2, _countof(nArray2), 10 );

  
  ///
  //排序法
  //srand( (unsigned)time(NULL) );
  srand( SRAND_TEST );
  int* pArray = new int[MAX_TEST];
  RandomTestData( pArray, MAX_TEST );

  //
  start = clock();
  /

  GetTopK_Sort( pArray, MAX_TEST, K_SIZE );

  ///
  finish = clock();    
  duration = (double)(finish-start);    
  cout << "使用排序法----时间消耗:" << duration << "ms" << endl << endl;  
  ///


  
  //使用堆
  srand( SRAND_TEST );
  RandomTestData( pArray, MAX_TEST );

  //
  start = clock();
  /

  GetTopK_Heap( pArray, MAX_TEST, K_SIZE );

  ///
  finish = clock();    
  duration = (double)(finish-start);    
  cout << "使用堆----时间消耗:" << duration << "ms" << endl << endl;  
  ///


  ///
  //使用快速排序思想
  srand( SRAND_TEST );
  RandomTestData( pArray, MAX_TEST );

  //
  start = clock();
  /

  //srand( (unsigned)time(NULL) );
  //int nArray[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
  //GetTopK_QSort( nArray, _countof(nArray), K_SIZE );
  GetTopK_QSort( pArray, MAX_TEST, K_SIZE );

  ///
  finish = clock();    
  duration = (double)(finish-start);    
  cout << "使用快排分区----时间消耗:" << duration << "ms" << endl << endl;  
  ///
  

  if ( NULL != pArray ) 
  {
    delete pArray;
    pArray = NULL;
  }

  return 0;
}



运行性能对比：

1、以下是从100000000条有序数据中找最小的2000个数的运行结果

 

算法练习：TopK_1_#include

2、以下是从1000000条有序数据中找最小的20个数的运行结果

 

算法练习：TopK_1_#include_02

 

3、以下是为10000条随机数据中找最小的20个数的运行结果

 

算法练习：TopK_1_#include_03

 

4、以下是在1亿条随机数据中找最小的20个数的运行结果 

 

算法练习：TopK_1_快速排序_04



系列文章说明:
1.本系列文章[算法练习],仅仅是本人学习过程的一个记录以及自我激励,没有什么说教的意思。如果能给读者带来些许知识及感悟，那是我的荣幸。
2.本系列文章是本人学习陈东锋老师《进军硅谷，程序员面试揭秘》一书而写的一些心得体会，文章大多数观点均来自此书，特此说明！
3.文章之中,难免有诸多的错误与不足,欢迎读者批评指正,谢谢.

作者：山丘儿



 

 

标签：int,pArray,练习,nHeap,high,算法,TopK,low,nArray
From： https://blog.51cto.com/u_15905375/5919886

相关文章

  • Java Swing的练习感悟
    感悟心得这还是我第一次使用JavaSwing写代码呢，直接就是趣味性拉满！在相关的界面代码的基础上，在必要的位置嵌入Java代码，就可以很好的实现啦！简单的嘞！（有兴趣的各位可以选......
  • mybatis-plus雪花算法生成Id使用详解
    文章目录​​前言​​​​一、mybatis-plus官网​​​​二、雪花算法实战​​​​1.建表​​​​2.新建测试工程​​​​3.单元测试​​​​三、实现分析​​​​四、为什么......
  • mybatis-plus雪花算法增强:idworker
    文章目录​​前言​​​​一、官网​​​​二、默认实现的弊端​​​​三、mybatis-plus中datacenterId和workerId的默认生成规则​​​​四、idworker介绍​​​​五、idwo......
  • 算法练习：两指针之三数之和为0
    问题描述给出一个整型数组，找出所有三个元素的组合，其组合之和等于0。要求在结果集里不含有重复的组合。举例：输入{-2， 1， -1， 2， 1}输出{-2， 1， 1 } 问题分析最容易想到的是......
  • 第七章练习题
    组卷一软件的六大质量特性包括：功能性可靠性可用性效率可维护性可移植性软件可靠性是指在指定的条件下使用时，软件产品维持规定的性能级别的能力，......
  • 第六章练习题
    16、软件验收测试的合格通过准则是（ABCD）。你的答案A软件需求分析说明书中定义的所有功能已全部实现，性能指标全部达到要求。√正确B所有测试项没有残余一级、二级和三级......
  • c++练习272题：金币
    *272题原题传送门：http://oj.tfls.net/p/272题解：（遍历，60分）#include<bits/stdc++.h>usingnamespacestd;longlongallday;//总天数longlongpas;//已经过去longlongmo......
  • 算法练习：两数之和
    题目：给定一个整型数组，是否能找出两个数使其和为指定的某个值？注：整型数组中不存在相同的数。一、解题方法1、暴力解法(时间复杂度O(n^2) )这是最容易想到的一种方法，即使用两......
  • 操作系统：银行家算法（避免死锁）
    算法介绍：程序实现：/*****************************************************程序：银行家算法实现作者：小单时间:2013年11月5日***************************......
  • 水仙花束的练习题
    packagewxy1;publicclassw{ publicstaticvoidmain(Stringargs[]){ //水仙花束的练习 for(inti=100;i<1000;i++){ intb=i/100; intc=i/......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99