探索数据库的实现原理

本篇内容介绍了"探索数据库的实现原理"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

归并连接的思想与归并排序的思想类似，详见代码注释.

#include #include #include #include "merge_sort.h"/*array : 待处理的数组low : 低位middle : 中间位high : 高位*/void merge_array(int array[],int low,int middle,int high){  //左边数组的大小(middle在左边数组中,加1)  int n1 = middle - low + 1;  //右边数组的大小  int n2 = high - middle;  //printf("---- merge_array : low = %d,high = %d,middle = %d.\n",low,high,middle);  //初始化左右两边数组  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;  //同时遍历左右两边数组,较小值进入到结果数组中(回填)  for(;i < n1 && j < n2;)    if(left[i] < right[j])      array[k++] = left[i++];    else      array[k++] = right[j++];  //处理数组中剩余的其他元素  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 : 待处理的数组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);  //对左边数组进行排序  merge_arraybyrange(array,low,middle);  //对右边数组进行排序  merge_arraybyrange(array,middle+1,high);  //两边数组排序完毕后,归并两边的数组  merge_array(array,low,middle,high);  // printf("--- merge_sort : ----\n");  // print_array(array+low,high - low + 1);}/*递归调用方法array : 待处理的数组low : 低位high : 高位*/void merge_sort_recursion(array *tmparr){  int low = 0;  int high = tmparr->counter - 1;  merge_arraybyrange(tmparr->arr,low,high);}/*非递归调用方法a/b:已完成排序的数组c:结果数组*/void merge_twoarrays2one(array *a,array *b,array *c){  int i=0,j=0;  c->counter=-1;  for(;i < a->counter && j < b->counter;)  {    //归并排序,任意一个数组结束则循环结束    if(a->arr[i] < b->arr[j])    {      c->arr[++c->counter] = a->arr[i++];    }    else    {      c->arr[++c->counter] = b->arr[j++];    }  }  //处理余下的数据  while(i < a->counter)  {    c->arr[++c->counter] = a->arr[i++];  }  while(j < b->counter)  {    c->arr[++c->counter] = b->arr[j++];  }  //从0开始计数,counter+1  c->counter++;}/*tmparr : 待排序的array结构体*/void merge_sort(array *tmparr){  //临时数组  int tmp[tmparr->counter];  //临时数组（缓存）  array buffer;  buffer.arr = tmp;  for(int i=1;i < tmparr->counter;i=i*2)  {    //i=每次比较的数量=2^x = 1/2/4/8...    for(int j=0;j < tmparr->counter;j+=i*2)    {      //j=比较起始位置,每次比较i个数      if(j+i >= tmparr->counter)        break;      array arr1,arr2;      //指向比较的位置(数组1)      arr1.arr = tmparr->arr+j;      arr1.counter = i;      //指向比较的位置(数组2)      arr2.arr = tmparr->arr+j+i;      arr2.counter = i;      //数组2的数量,判断以免越界      if(j+i*2 >= tmparr->counter)        arr2.counter = tmparr->counter - (j + i);      //归并数组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);      //归并好的数据拷贝到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 1item[1] is 5item[2] is 10item[3] is 21item[4] is 30item[5] is 40item[6] is 99item[7] is 100item[8] is 200item[9] is 301item[10] is 400--------- test_merge by recursion-----------item[0] is 1item[1] is 5item[2] is 10item[3] is 21item[4] is 30item[5] is 40item[6] is 99item[7] is 100item[8] is 200item[9] is 301item[10] is 400

"探索数据库的实现原理"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！