數(shù)據(jù)庫實現(xiàn)原理#2（獲取第N個值）

獲取數(shù)組中的第N個值,仍使用代碼說明,算法參考快速排序的思想,詳見代碼注釋.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../pub/pub.h"
//tmparr : 待處理的數(shù)組
//counter : 數(shù)組元素個數(shù)
//n : 從小到大排列,第n個數(shù)字(從0開始計數(shù))
static int quicksort_nth_recursion(int tmparr[],int counter,int n)
{
  //DEBUG : 數(shù)組信息
  //print_array(tmparr,counter);
  //任意取一個值,找到該值的位置
  int pos = 0;
  int randompos = rand() % counter;
  //把選定的值移到第一個位置
  swap(tmparr,0,randompos);
  for(int i=1;i < counter;i++)
  {
    //從1開始遍歷,如遍歷的元素小于選定的值,則把pos加一并吧該值移到pos所在的位置
    //循環(huán)完成后,小于隨機(jī)選擇值的數(shù)會在pos的左邊,大于等于選擇值的在pos的右邊
    if(tmparr[i] < tmparr[0])
    {
      //如果遍歷
      swap(tmparr,++pos,i);
    }
  }
  //printf("value = %d,counter = %d,target = %d,pos = %d\n",tmparr[0],counter,n,pos);
  //把選定的值移到它該在的地方
  swap(tmparr,pos,0);
  if(pos == n)
    return tmparr[pos];
  //遞歸處理
  if(pos < n)//在右邊的數(shù)組中
    quicksort_nth_recursion(tmparr+(pos+1),counter-(pos+1),n-(pos+1));
  else//在左邊的數(shù)組中
    quicksort_nth_recursion(tmparr,pos,n);
}
void main(void)
{
  //參數(shù):第1個/中間/最后一個
  int pos[3] = {1,0,0};
  int result = 0,counter = 0;
  int arr[] = {4,10,25,100,53,103,50,40,77,9,5,1,65,19,60,51,500};
  counter  = sizeof(arr)/sizeof(int);
  pos[1] = (counter+1)/2;//中位數(shù)
  pos[2] = counter;//最大值
  for(int i = 0;i < 3;i++)
  {
    result = quicksort_nth_recursion(arr,counter,pos[i]-1);
    printf("---------- The No.%d result is %d ----------\n",pos[i],result);
  }
  printf("------------------------------------------------------------\n");
  int arr2[1<<16];
  srand(38838);
  for(int i=0;i < 1<<16;i++)
  {
    arr2[i] = rand();
  }
  counter  = sizeof(arr2)/sizeof(int);
  pos[1] = (counter+1)/2;
  pos[2] = counter;
  for(int i = 0;i < 3;i++)
  {
    result = quicksort_nth_recursion(arr2,counter,pos[i]-1);
    printf("---------- The No.%d result is %d ----------\n",pos[i],result);
  }
}

運行輸出

helloworld@DESKTOP-BRAEUTR /d/yunpan/Work/Z-SRC/sort
$ /d/tmp/test.exe
---------- The No.1 result is 1 ----------
---------- The No.9 result is 50 ----------
---------- The No.17 result is 500 ----------
------------------------------------------------------------
---------- The No.1 result is 0 ----------
---------- The No.32768 result is 16541 ----------
---------- The No.65536 result is 32767 ----------