数据库入门级之算法【二】

数据库算法的熟练运用对我们的生活和工作是有很大帮助的。上一篇《数据库入门级之算法【一】》中我们介绍了一些数据算法，现在我们继续介绍一些基本排序算法。
冒泡排序
使用条件：集合的元素可对比大小
算法思想：连续地扫描待排序的记录，每扫描一次，都会找出最小记录，使之更接近顶部。数据库软件由于每次扫描都会把一条记录置于它的最终最正确的位置，因此下次扫描不需要重新检查这条记录
举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}将其冒泡排序(这里笔者将概念弄混淆了，感谢zdd的指出）

1. //冒泡排序  
2. void Bubble(int b[10])  
3. {  
4.     int temp;  
5.     int i;  
6.     for(i=9;i>0;i–)  
7.     {  
8.         for(int j=0;j<i;j++)  
9.         {  
10.             if(b[j]>b[j+1])  
11.             {  
12.                 temp=b[j];  
13.                 b[j]=b[j+1];  
14.                 b[j+1]=temp;  
15.             }  
16.         }  
17.     }  
18.     cout<<“the sort is:”;  
19.     for(int i=0;i<10;i++)  
20.     {  
21.         cout<<b[i]<<” “;  
22.     }  
23.     cout<<endl;  
24. }  

性能分析：时间复杂度O(n^2)
希尔排序
使用条件：集合的元素可对比大小
算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序“时，在对全体记录进行一次直接插入排序。子序列构成的不是简单“逐段分割”，而是相隔某个“增量”的记录组成一个子序列。因此比较排序时候关键字较小的记录就不是一步一步往前挪动，而是相隔一定增量移动，该“增量”呈现一个递减趋势，最后这个“增量”总是为1，那么此时序列已基本有序，只要作少量的比较和移动几个完成排序。希尔排序不好把握增量的设定。数据库设计一般8个数我们认为设定“增量”为：4,2,1。（这是一般希尔排序的设定）。那么笔者这里要拟定一个求“增量”的公式 h(n+1)=3*h(n)+1,（h>N/9停止）这个公式可能选择增量不是最合适，但是却适用一般“增量”的设定。如果是8个数的话，那么这里增量就是1。
举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}将其希尔排序
//希尔排序自增量需要自己合适选择

1. void ShellSort(int b[10])  
2. {  
3.    int h,i;  
4.    int n=10;  
5.    //通过这个循环算出增量为1和4  
6.    for(h=1;h<=n/9;h=3*h+1);  
7.       //增量循环  
8.    for(;h>0;h/=3)  
9.    {  
10.       for(i=h;i<n;i++)  
11.       {  
12.          int j,temp;  
13.          temp=b[i];  
14.          //插入排序  
15.          for(j=i-h;j>=0;j=j-h)  
16.          {  
17.             if(b[j]>temp)  
18.             {  
19.                 b[j+h]=b[j];  
20.             }  
21.             else 
22.             {  
23.                 break;  
24.             }  
25.          }  
26.          b[j+h]=temp;  
27.       }  
28.    }  
29.    cout<<“the sort is:”;  
30.    for(int i=0;i<10;i++)  
31.    {   
32.          cout<<b[i]<<” “;  
33.    }  
34.    cout<<endl;  
35. }  

#p#分页标题#e#

性能分析：时间复杂度对于希尔排序就有点复杂，它根据具体的“增量”不同而不同，这里笔者采用严蔚敏《数据结构》的O(n^3/2)
快速排序
使用条件：可对比大小的集合。
算法思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则可分别对这两部分记录继续这种排序，最后达到有序序列。数据库管理系统这里有一个关键点，就是选取分割的“基准”。肯定是大于这个“基准”分成一个部分，小于这个“基准”分成一个部分。这里笔者默认取该部分第一个记录为“基准”。
举例编程：int b[10]={77,1,65,13,81,93,10,5,23,17}
算法是计算机科学中一个重要的研究方向，是解决复杂问题的关键。在计算机世界中，算法无处不在
。数据库是存储数据和执行大批量计算的场所，在数据库中使用一些简单的SQL命令，进行存储、查询、

1. //快速排序  
2. void QuickSort(int *b,int low,int high)  
3. {  
4.     //交换函数  
5.     void Sawp(int *a,int *b);  
6.     int Old_low=low;  
7.     int Old_high=high;  
8.     while(low<high)  
9.     {  
10.         while(*(b+high)>*(b+low)&&low<high)high–;  
11.         Sawp(b+low,b+high);  
12.         while(*(b+low)<*(b+high)&&low<high)low++;  
13.         Sawp(b+low,b+high);  
14.     }  
15.     if(Old_low<low-1)  
16.     {  
17.         QuickSort(b,Old_low,low-1);  
18.     }  
19.     if(high+1<Old_high)  
20.     {  
21.         QuickSort(b,high+1,Old_high);  
22.     }  
23. }  
24. //交换函数  
25. void Sawp(int *a,int *b)  
26. {  
27.     int temp;  
28.     temp=*a;  
29.     *a=*b;  
30.     *b=temp;  
31. }  

性能分析：时间复杂度O(nlogn)数据库学习
到这个，我们介绍了我们常见的基本数据查找和排序的算法，而这些是最基础的算法，很多算法可以由他们延伸。希望对大家能有所帮助。