探索數(shù)據(jù)庫的實現(xiàn)原理

本篇內(nèi)容介紹了“探索數(shù)據(jù)庫的實現(xiàn)原理”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

歸并連接的思想與歸并排序的思想類似，詳見代碼注釋.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "merge_sort.h"
/*
array : 待處理的數(shù)組
low : 低位
middle : 中間位
high : 高位
*/
void merge_array(int array[],int low,int middle,int high)
{
  //左邊數(shù)組的大小(middle在左邊數(shù)組中,加1)
  int n1 = middle - low + 1;
  //右邊數(shù)組的大小
  int n2 = high - middle;
  //printf("---- merge_array : low = %d,high = %d,middle = %d.\n",low,high,middle);
  //初始化左右兩邊數(shù)組
  int left[n1],right[n2];
  for(int i = 0;i < n1;i++)
    left[i] = array[low+i];
  for(int i = 0;i < n2;i++)
    right[i] = array[middle+i+1];
  //歸并
  int i=0,j=0,k=low;
  //同時遍歷左右兩邊數(shù)組,較小值進入到結(jié)果數(shù)組中(回填)
  for(;i < n1 && j < n2;)
    if(left[i] < right[j])
      array[k++] = left[i++];
    else
      array[k++] = right[j++];
  //處理數(shù)組中剩余的其他元素
  while(i < n1)
    array[k++] = left[i++];
  while(j < n2)
    array[k++] = right[j++];
  // printf("--- merge_array : ---\n");
  // print_array(array+low,n1 + n2);
}
/*
array : 待處理的數(shù)組
low : 低位
high : 高位
*/
void merge_arraybyrange(int array[],int low,int high)
{
  if (low >= high)
    return;//低位置大于等于高位值,退出
  //取中間位置
  int middle = (low + high)/2;
  //printf("---- merge_sort : low = %d,high = %d,middle = %d.\n",low,high,middle);
  //對左邊數(shù)組進行排序
  merge_arraybyrange(array,low,middle);
  //對右邊數(shù)組進行排序
  merge_arraybyrange(array,middle+1,high);
  //兩邊數(shù)組排序完畢后,歸并兩邊的數(shù)組
  merge_array(array,low,middle,high);
  // printf("--- merge_sort : ----\n");
  // print_array(array+low,high - low + 1);
}
/*
遞歸調(diào)用方法
array : 待處理的數(shù)組
low : 低位
high : 高位
*/
void merge_sort_recursion(array *tmparr)
{
  int low = 0;
  int high = tmparr->counter - 1;
  merge_arraybyrange(tmparr->arr,low,high);
}
/*
非遞歸調(diào)用方法
a/b:已完成排序的數(shù)組
c:結(jié)果數(shù)組
*/
void merge_twoarrays2one(array *a,array *b,array *c)
{
  int i=0,j=0;
  c->counter=-1;
  for(;i < a->counter && j < b->counter;)
  {
    //歸并排序,任意一個數(shù)組結(jié)束則循環(huán)結(jié)束
    if(a->arr[i] < b->arr[j])
    {
      c->arr[++c->counter] = a->arr[i++];
    }
    else
    {
      c->arr[++c->counter] = b->arr[j++];
    }
  }
  //處理余下的數(shù)據(jù)
  while(i < a->counter)
  {
    c->arr[++c->counter] = a->arr[i++];
  }
  while(j < b->counter)
  {
    c->arr[++c->counter] = b->arr[j++];
  }
  //從0開始計數(shù),counter+1
  c->counter++;
}
/*
tmparr : 待排序的array結(jié)構(gòu)體
*/
void merge_sort(array *tmparr)
{
  //臨時數(shù)組
  int tmp[tmparr->counter];
  //臨時數(shù)組（緩存）
  array buffer;
  buffer.arr = tmp;
  for(int i=1;i < tmparr->counter;i=i*2)
  {
    //i=每次比較的數(shù)量=2^x = 1/2/4/8...
    for(int j=0;j < tmparr->counter;j+=i*2)
    {
      //j=比較起始位置,每次比較i個數(shù)
      if(j+i >= tmparr->counter)
        break;
      array arr1,arr2;
      //指向比較的位置(數(shù)組1)
      arr1.arr = tmparr->arr+j;
      arr1.counter = i;
      //指向比較的位置(數(shù)組2)
      arr2.arr = tmparr->arr+j+i;
      arr2.counter = i;
      //數(shù)組2的數(shù)量,判斷以免越界
      if(j+i*2 >= tmparr->counter)
        arr2.counter = tmparr->counter - (j + i);
      //歸并數(shù)組1&2
      merge_twoarrays2one(&arr1,&arr2,&buffer);
      // printf("---------- i = %d,j = %d,counter = %d\n",i,j,buffer.counter);
      // print_array(buffer.arr,buffer.counter);
      //歸并好的數(shù)據(jù)拷貝到tmparr中
      memcpy(tmparr->arr+j,buffer.arr,buffer.counter*sizeof(int));
    }
    // printf("------------ i = %d\n",i);
    // print_array(tmparr->arr,tmparr->counter);
  }
}

運行輸出

ethanhe@DESKTOP-V73MH70 /d/yunpan/work/Z-SRC/sort
$ /d/tmp/test.exe
--------- test_merge -----------
item[0] is 1
item[1] is 5
item[2] is 10
item[3] is 21
item[4] is 30
item[5] is 40
item[6] is 99
item[7] is 100
item[8] is 200
item[9] is 301
item[10] is 400
--------- test_merge by recursion-----------
item[0] is 1
item[1] is 5
item[2] is 10
item[3] is 21
item[4] is 30
item[5] is 40
item[6] is 99
item[7] is 100
item[8] is 200
item[9] is 301
item[10] is 400

“探索數(shù)據(jù)庫的實現(xiàn)原理”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！