新浪微博笔试题和面试题答案与答案(三)
8: 罗列你知道的排序算法,并注明他们的复杂度
冒泡法: 复杂度为O(n*n)
直接插入排序：O(n*n)
选择排序：O(n*n)
快速排序：平均时间复杂度log2(n)*n
归并排序：log2(n)*n
堆排序：log2(n)*n
9: 用java/php/C++实现快速排序算法
public class QSort {
/*
* @param pData 需要排序的数组
* @param left 左边的位置,初始值为0
* @param right 右边的位置,初始值为数组长度
*/
public static void QuickSort(int[] pData,int left,int right)
{
int i,j;
int middle,temp;
i = left;
j = right;
middle = pData[left];
//一趟快速排序
while(true)
{
//从第二个数开始找大于中枢的数
while((++i)
//从最后一个数开始找第一个小于中枢的数
while((--j)>left && pData[j]>middle);
if(i>=j)
break;
//交换两边找到的数
temp = pData[i];
pData[i] = pData[j];
pData[j] = temp;
}
//交换中枢
pData[left] = pData[j];
pData[j] = middle;
//递归快排中枢左边的数据
if(left
QuickSort(pData,left,j);
//递归快排中枢右边的数据
if(right>i)
QuickSort(pData,i,right);
}
public static void main(String[] args){
int [] pData = new int[10];
for(int i = 0; i< 10; i++)
pData[i] = (int)(Math.random()*100);
for(int i = 0; i
System.out.print(pData[i]+" ");
System.out.println("");
QSort.QuickSort(pData, 0, pData.length);
System.out.println("\n*");
for(int i = 0; i
System.out.print(pData[i]+" ");
}
}
10: 名词解释：HTML5，CSS，STL，MYSQL, B-tree, Fedora
HTML5:HTML5草案的前身名为Web Applications 1.0，於2004年被WHATWG提出，於2007年被W3C接纳，并成立了新的HTML工作团队。HTML标准自1999年12月发布的 HTML 4.01后，后继的HTML 5 和其它标准被束之高阁，为了推动web标准化运动的发展，一些公司联合起来，成立了一个叫做 Web Hypertext Application Technology Working Group (Web 超文本应用技术工作组 - WHATWG) 的组织，他们重新拣起 HTML 5。第一份正式草案已于2008年1月22日公布。HTML 5有两大特点：首先，强化了Web网页的表现性能。其次，追加了本地数据库等Web应用的功能。
