數組中尋找第K小的數----位圖法（bitmap）

（1）位圖法

     所謂bitmap，就是用每一位來存放某種狀态，适用于大規模資料，但資料狀态又不是很多的情況。通常是用來判斷某個資料存不存在的(百度百科)。　

     例如：對{0， 1， 5，3， 7}進行排序，可以在計算機中使用8位表示這幾個數，也就是使用一個位元組空間可以完成排序。

      數組中的數：               0   1            3              5               7

      bitmap中的位值：      1    1    0     1      0     1      0       1     //若在數組中，則位值設為1，否則為0

      bitmap中的位标号：  0    1    2     3      4      5      6      7

      位圖法還可以判斷數組中值是否重複出現。位圖法在降低了時間複雜度的同時，很好的控制了空間複雜度。

（2）算法實作（分為  針對無符号數組  及  有符号數組）

         A：針對無符号數組實作：

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;

void set_bit(char *bit_map, int n)
{
	for(int i=0; i<(n/8); ++i)
		bit_map++;
	//相應表示的位置1
	*bit_map =(*bit_map) | (0x01<<n%8);
}

int get_max_value(int num[], int n)
{
   int temp = num[0];
   for(int i=1; i<n; ++i)
   {
	   if(num[i]>temp)
		   temp = num[i];
   }
   return temp;
}

void bit_map_sort(int num[], int n)
{
	//首先得到數組中的最大值
	int max = get_max_value(num, n);
	//計算bitmap的長度,每一個位元組可以表示8個數
	int bit_map_len = 0;
	if(max%8 == 0)
	  bit_map_len = max/8;
	else
	  bit_map_len = max/8+1;
	//建立bitmap
	char* bit_map = new char[bit_map_len];
	memset(bit_map, 0, bit_map_len);
	for(int i=0; i<n; ++i)
		set_bit(bit_map, num[i]);
	//輸出數組
	for(int i=0; i<bit_map_len; ++i)
	{
		for(int j=0; j<8; ++j)
		{
			//如果該位是1，則輸出
			if((bit_map[i]&(0x01<<j)) == (0x01<<j))
				cout<<(i*8+j)<<" ";
		}
	}
	cout<<endl;
}

int main()
{
    int num[] = {3,5, 2, 10, 6, 9999999, 8, 14, 9};
    bit_map_sort(num, 9);
    return 0;
}
           

       B：針對有符号數組（數組中存在負數）

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;

//從bitmap中間開始計算，左邊表示負數，右邊表示正數
void set_bit(char *bit_map_mid, int num)
{
	//若為正數，則指針右移
	if(num >= 0)
	   for(int i=0; i<(num/8); ++i)
		bit_map_mid++;
	//反之，指針左移
	if(num < 0)
	{
	   num = -1*num;
       for(int i=0; i<(num/8); ++i)
		bit_map_mid--;
	   bit_map_mid--;
	}
	//相應表示的位置1
	*bit_map_mid =(*bit_map_mid) | (0x01<<num%8);
}

//得到數組中絕對值最大的值
int get_max_absolute_value(int num[], int n)
{
   int temp = 0;
   for(int i=0; i<n; ++i)
   {
	   if(num[i]>temp)
		   temp = num[i];
	   else if(num[i]<0)
		 if((num[i]*(-1))>temp)
			 temp = num[i]*(-1);
   }
   return temp;
}

void bit_map_sort(int num[], int n)
{
	//首先得到數組中的最大值
	int max = get_max_absolute_value(num, n);
	//計算bitmap的長度,每一個位元組可以表示8個數
	int bit_map_len = 0;
	if(2*max%8 == 0)//若最大值為16，則其bitmap應該能表示[-16, 16]，是以乘以2；
	  bit_map_len = 2*max/8;
	else
	  bit_map_len = 2*max/8+1;
	//建立bitmap
	char* bit_map = new char[bit_map_len];
	memset(bit_map, 0, bit_map_len);
	int mid = bit_map_len/2;
	for(int i=0; i<n; ++i)
		set_bit(bit_map+mid, num[i]);
	//首先輸出負數
	for(int i=0; i<mid; ++i)
	{
		for(int j=0; j<8; ++j)
		{
			//如果該位是1，則輸出
			if((bit_map[i]&(0x01<<j)) == (0x01<<j))
				cout<<(-1)*((mid-1-i)*8+j)<<" ";
		}
	}
	for(int i=mid; i<bit_map_len; ++i)
	{
		for(int j=0; j<8; ++j)
		{
			//如果該位是1，則輸出
			if((bit_map[i]&(0x01<<j)) == (0x01<<j))
				cout<<(i-mid)*8+j<<" ";
		}
	}
	cout<<endl;
}

int main()
{
    int num[] = {3,5, 2, 10, 6, -999999, 8, -14, 9};
	bit_map_sort(num, 9);
	return 0;
}