算法学习（一）：寻找最小的k个数

题目

题目描述：寻找最小的k个元素
题目：输入n个整数，输出其中最小的k个
例如输入1,2,3,4,5,6,7,8,则最小的4个数是1,2,3,4

思路

一，最容易想到的就是排序，然后输出前k个元素，快速排序，排序时间是n*logn,再加上遍历输出前k个元素，总的时间复杂度是n*logn+k = O(n*logn)
二，其实题目中只要求输出前k个数，没有要求这些数是有顺序的，而且不必对n个数进行排序。从n个数中先取出前k个数放到一个数组中，然后对这k个数使用选择排序或者交换排序，找到kmax这k个数中最大的数，用时O(k)。然后从剩下的n-k个数中依次取出一个数x，与kmax比较，if x > kmax, 跳过，if x < kmax ，kmax= x,然后再对这k个数进行选择排序找到最大的kmax，总的时间复杂度平均下来为n*O(k),利用的就是要找的是最小的前k个数，如果比最大的大，肯定不在里面，如果比最大的小，可能在里面，因为有新的元素加入，再次进行排序找最大，又重复比较。
三，我们可以对思路二中的k个数的操作进行改进，就是找到k个数中的kmax，可以使用最大堆，维护k个元素的最大堆，建堆耗时O(k)，此时堆顶的根节点是最大的kmax，然后遍历剩下的n-k个元素，if x>kmax ,跳过，if x < kmax ,kmax = x,更新最大堆，时间复杂度为O(logk)，总的时间复杂度为O(n*logk)。
四，我们的目的就是找到最小的k个数，如果有一种方法正好把这k个数放到左边，右边的都是比它们大的，直接输出就好了，这个其实就是快速排序的思路。n个数存在数组S中，随机选取一个数X作为枢纽元素，将数组划分为Sa和Sb两个部分，Sa<=X <= Sb，如果要查找的个数k小于sizeof(Sa),就返回Sa中前k个元素，否则返回Sa中所有元素+Sb中小的k-sizeof(Sa)个元素。这个算法的关键就是这个枢纽元素的选择，随机选取枢纽元素，可以做到线性期望时间O(n)。我们通常所熟知的快速排序是以固定的第一个或者最后一个做为枢纽元，每次递归划分都是不均等的，最后的平均时间复杂度为O(n * logn),RANDOMIZED-SELECT(数据结构与算法分析-c语言描述P185)提出的对于选择的线性期望时间，与普通的快排不同的是，每次都是随机的，随机的方法有“中位数的中位数”，“五分化中项的中项”。
五，可以使用线性时间排序，计数排序，时间复杂度达到O(n)
六，既然是找最小的前k个数，我们可以使用最小堆，将n个元素所在数组，建立最小堆，用时O(n)，从堆顶取k次数，取完一次就要重新排列最小堆，保证最小堆的性质，每次平均用时logn，,总的时间复杂度为O(n+k*logn),这种方法与二比较，时间复杂度小，但是空间复杂度为O(n),最大堆的空间复杂度为O(k)
七，思路和六是一样的，只不过是在取完堆顶元素后，重新排列时，换到堆顶的元素只需要下移最多k次就足够了，此时堆顶的元素已经是我们要找的第二小的元素，然后取出第二小的元素，再次把堆中的最后一个元素送到堆顶，又经过k-1次下移后，此后下移次数逐渐减少，重复k-1次，不断取出的堆顶元素是我们要找的最小的k个数，不过需要注意，算法中断后的堆已经不再是最小堆了，思路六中每次提取都要logn，这个需要k,总的时间复杂度为O(n+k^2)

实现

代码都是通过编译调试的，记录下来方便以后再回过头来复习，不过感觉还是写的比较low。加油吧。
思路一：快速排序

/*************************************************************************
 > File Name: quicksort_kmin.cpp
 > Author: zxl
 > mail: [e-mail]
 > Created Time: 2016年04月07日 星期四 21时01分26秒
 ************************************************************************/

#include <iostream>
#define MAX 20000
#define K 100
using namespace std;
int partion(int A[],int start,int end)
{
int x = A[end];
int i = start-1;
int j;
for(j = start;j<end;j++)
    {
if(A[j] <= x)
        {
            i++;
            swap(A[i],A[j]);

        }

    }
    swap(A[i+1],A[end]);
return i+1;

}
void quicksort(int A[],int start,int end)
{
if(start < end)
    {
int mid = partion(A,start,end);
        quicksort(A,start,mid-1);
        quicksort(A,mid+1,end);
    }
}
void Kmin(int A[],int length,int k)
{
int i;
    quicksort(A,0,length);
for(i = 0;i<k;i++)
    {
        cout << A[i] << endl;
    }

}
int main()
{
int A[MAX];
int i;
for(i = 0;i< MAX;i++)
        A[i] = MAX-i;
    Kmin(A,MAX-1,K);
return 0;
}

思路二：

/*************************************************************************
    > File Name: kmin_2.cpp
    > Author: zxl
  > mail: [e-mail]
    > Created Time: 2016年04月07日 星期四 22时12分24秒
************************************************************************/

#include <iostream>
#define MAX 200
#define K 10
using namespace std;
void swap(int * a,int *b)//c++有自带的swap函数
{
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
//找到最大值放到数组末尾
int FindMax(int buf[],int length)
{
int i;
for(i = 0;i<length;i++)
    {
if(buf[i] > buf[length-1])
        {
            swap(buf+length-1,buf+i);
        }
    }
return buf[length-1];
}
void Kmin(int A[],int length,int k)
{
int B[k];
int i;
int max;
for(i = 0;i<k;i++)
    {
        B[i] = A[i];
    }
    max = FindMax(B,k);
for(i = length-k-1;i<length;i++)
    {
if(A[i] >= max)
continue;
else
        {
            swap(B+k-1,A+i);
            max = FindMax(B,k);

        }
    }
for(i = 0;i< k;i++)
        cout << B[i] << endl;

}
int main(void)
{
int A[MAX];
int i;
for(i=0;i< MAX;i++)
        A[i] = MAX-i;
    Kmin(A,MAX,K);
return 0;
}

思路三：维护k个元素的最大堆，适用于处理海量数据

/*************************************************************************
 > File Name: kmin_3.cpp
 > Author: zxl
 > mail: [e-mail]
 > Created Time: 2016年04月08日 星期五 15时11分55秒
 ************************************************************************/

#include <iostream>
#define MAX 10
#define K 3
using namespace std;

int Parent(int i)
{
return i/2;
}
int LEFT(int i)
{
return i*2;
}
int RIGHT(int i)
{
return 2*i+1;
}
void Max_heapify(int A[],int size,int i)
{

int l = LEFT(i);
int r = RIGHT(i);
int largest;
if(l <= size && A[l]> A[i])
        largest = l;
else
        largest = i;
if(r<= size && A[r] > A[largest])
        largest = r;
if(largest != i)
    {
        swap(A[i],A[largest]);
        Max_heapify(A,size,largest);
    }

}
void Build_Max_heap(int A[],int size)
{ 
int i;
for(i = size/2;i>0;i--)
        Max_heapify(A,size,i);
}
void Kmin(int A[],int length,int k)
{
int i,j;
int B[k];
for(i = 1;i<= k;i++)
        B[i] = A[i];
    Build_Max_heap(B,k);

for(j = k+1;j<=length;j++)
    {
if(A[j] > B[1])
continue;
else
        {
            swap(A[j],B[1]);
            Max_heapify(B,k,1);
        }
    }
for(i = 1;i<=k;i++)
        cout << B[i] << endl;

}
int main()
{
int A[MAX];
int i;
for(i = 1;i<=MAX;i++)
    {
        A[i]= MAX-i;
    }
    Kmin(A,MAX,K);
return 0;
}

思路四：在选择枢纽元时采用三数求中值法，快速选择只做一次递归调用而不是两次，能保证平均时间为O（N）。

/*************************************************************************
 > File Name: kmin_4.cpp
 > Author: zxl
 > mail: [e-mail]
 > Created Time: 2016年04月11日 星期一 09时48分33秒
 ************************************************************************/

#include <iostream>
#define CTUOF 3
#define MAX 100
#define K 30
using namespace std;
// 三数中值分割方法
/*将A[left],A[right],A[center]排序，保证最小的在A[left],最大的在A[right],把枢纽元放在A[right-1]，并在分割阶段将i和j初始化到left+1,和right-2。
*/
int Median3(int A[],int left ,int right)
{
    int center = (left + right)/2;
if(A[left] > A[center])
        swap(A[left],A[center]);
if(A[left] > A[right])
        swap(A[left],A[right]);
if(A[center] > A[right])
        swap(A[center],A[right]);
    swap(A[center],A[right -1]);
return A[right-1];
}
void Insertsort(int A[],int N)
{
    int i,j;
    int temp;
    for(i = 1;i < N;i++)
    {
        temp = A[i];
        for(j = i;j > 0 && A[j-1] > temp;j--)
A[j] = A[j-1];
A[j] = temp;
    }


}
void Qselect(int A[],int k ,int left ,int right)
{
    int i,j;
    int pivot;
if(left + CTUOF <= right)
    {
        i = left;
        j = right-1;
        pivot = Median3(A,left,right);
while(true)
        {
while(A[++i] < pivot) {}
while(A[--j] > pivot) {}
if(i <j)
                swap(A[i],A[j]);
else
break;
        }
        swap(A[i],A[right-1]);
if(k <=i)
            Qselect(A,k,left,i-1);
else if(k > i+1)
            Qselect(A,k,i+1,right);

    }
else
        Insertsort(A+left,right-left+1);
}
int main()
{
    int i;
    int A[MAX];
    for(i = 0;i< MAX;i++)
A[i] = MAX-i;
    Qselect(A,K,0,MAX-1);
    for(i = 0;i<K ;i++)
        cout << A[i] << endl;
}

思路四之二：出自算法导论P120，期望为线性时间的选择算法，期望运行时间为O(N)。枢纽元为随机选择。

/*************************************************************************
 > File Name: kmin_4_2.cpp
 > Author: zxl
 > mail: [e-mail]
 > Created Time: 2016年04月11日 星期一 15时56分16秒
 ************************************************************************/

#include <iostream>
#include <stdlib.h>
#include <time.h>
#define MAX 1000
#define K 10
using namespace std;
int random(int a,int b)
{
    srand((unsigned)time(NULL));
return (rand() %(b-a+1))+a;

}
int Partion(int A[],int start,int end)
{
int x = A[end];
int i,j;
    i = start-1;
for(j = start;j< end;j++)
    {
if(A[j]<= x)
        {
            i++;
            swap(A[i],A[j]);
        }

    }
    swap(A[i+1],A[end]);
return i+1;
}
int RandomPartion(int A[],int start,int end)
{
int i;
    i = random(start,end);
    swap(A[end],A[i]);
return Partion(A,start,end);

}
void RandomSelect(int A[],int start,int end,int k)
{
if(start == end)
return;
int q;
    q = RandomPartion(A,start,end);
int cout = q-start+1; //低区加主员；
if(cout == k)
return;
else if(k < cout)
        RandomSelect(A,start,q-1,k);
else
        RandomSelect(A,q+1,end,k-cout);

}
int main()
{
int A[MAX];
int i;
for(i = 0;i<MAX;i++)
        A[i] = MAX-i;
    RandomSelect(A,0,MAX-1,K);
for(i = 0;i< K;i++)
cout << A[i] << endl;
return 0;
}

思路五：线性时间排序，计数排序，O（N）,但是限制比较多，一般不常用

/*************************************************************************
 > File Name: kmin_5.cpp
 > Author: zxl
  > mail: [e-mail]
 > Created Time: 2016年04月11日 星期一 16时41分54秒
************************************************************************/

#include <iostream>
#define MAX 1000
#define K 10
using namespace std;
void cout_sort(int A[],int length,int k)
{
 int B[length];
 int C[length];
 int i,j;
 for(i = 0;i<length;i++) //这个地方c种元素的个数，初始化时假定为max，无重复的。
 C[i] = 0;
 for(j = 1;j<=length;j++)
 C[A[j]] = C[A[j]]+1;
 for(i = 0;i<length;i++)
 C[i] = C[i-1]+ C[i];
 for(j = length;j>1;j-- )
 {
 B[C[A[j]]] = A[j];
 C[A[j]] = C[A[j]]-1;
 }
 for(i = 1;i<=k;i++)
 cout << B[i] << endl;

}
int main(void)
{
 int A[MAX];
 int i;
 for(i = 1;i<= MAX;i++)
 A[i] = MAX-i;
 cout_sort(A,MAX,K);
 return 0;
}

思路六：最小堆排序，然后依次取出堆顶元素。

/*************************************************************************
 > File Name: kmin_6.cpp
 > Author: zxl
 > mail: [e-mail]
 > Created Time: 2016年04月11日 星期一 17时07分33秒
 ************************************************************************/

#include <iostream>
#define MAX 1000
#define K 10
using namespace std;

int LEFT(int i)
{
return 2*i;
}
int RIGHT(int i)
{
return 2*i+1;
}
void Min_heapify(int A[],int size,int i)
{
int l = LEFT(i);
int r = RIGHT(i);
int small;
if(l <= size && A[l] < A[i])
        small = l;
else
        small = i;
if(r <= size && A[r] < A[small])
        small = r;
if(small != i)
    {
        swap(A[i],A[small]);
        Min_heapify(A,size,small);
    }
}
void Build_Min_heap(int A[],int size)
{
int i;
for(i = size/2;i> 0;i--)
    {
        Min_heapify(A,size,i);
    }
}
void Kmin(int A[],int size,int k)
{
    Build_Min_heap(A,size);
int i;
int length = size;
for(i = length;i>length-k;i--)
    {
        swap(A[1],A[i]);
        cout << A[i] << endl;
size = size-1;
        Min_heapify(A,size,1);
    }
}
int main(void)
{
int A[MAX];
int i;
for(i = 0;i< MAX;i++)
        A[i] = MAX-i;
    Kmin(A,MAX,K);
return 0;
}