新浪微博筆試題和面試題答案與答案(三)

　　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應用的功能。