新浪微博笔试题和面试题答案与答案(三)

　　8: 罗列你知道的排序算法,并注明他们的复杂度

　　冒泡法: 复杂度为O(nn)

　　直接插入排序：O(nn)

　　选择排序：O(nn)

　　快速排序：均时间复杂度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应用的功能。