冒泡排序發明

Ⅰ 冒泡排序法和快速排序比較的演算法

打你屁股，這么簡單的問題都不認真研究一下。

冒泡排序是最慢的排序，時間復雜度是 O(n^2)。

快速排序是最快的排序。關於快速排序，我推薦你看看《代碼之美》第二章：我編寫過的最漂亮的代碼。作者所說的最漂亮，就是指效率最高的。

--------------------------------摘自《代碼之美》---------------

當我撰寫關於分治（divide-and-conquer）演算法的論文時，我發現C.A.R. Hoare的Quicksort演算法（「Quicksort」，Computer Journal 5）無疑是各種Quicksort演算法的鼻祖。這是一種解決基本問題的漂亮演算法，可以用優雅的代碼實現。我很喜歡這個演算法，但我總是無法弄明白演算法中最內層的循環。我曾經花兩天的時間來調試一個使用了這個循環的復雜程序，並且幾年以來，當我需要完成類似的任務時，我會很小心地復制這段代碼。雖然這段代碼能夠解決我所遇到的問題，但我卻並沒有真正地理解它。
我後來從Nico Lomuto那裡學到了一種優雅的劃分（partitioning）模式，並且最終編寫出了我能夠理解，甚至能夠證明的Quicksort演算法。William Strunk Jr.針對英語所提出的「良好的寫作風格即為簡練」這條經驗同樣適用於代碼的編寫，因此我遵循了他的建議，「省略不必要的字詞」（來自《The Elements of Style》一書）。我最終將大約40行左右的代碼縮減為十幾行的代碼。因此，如果要回答「你曾編寫過的最漂亮代碼是什麼？」這個問題，那麼我的答案就是：在我編寫的《Programming Pearls, Second Edition》(Addison-Wesley)一書中給出的Quichsort演算法。在示例2-1中給出了用C語言編寫的Quicksort函數。我們在接下來的章節中將進一步地研究和改善這個函數。
【示例】 2-1 Quicksort函數
void quicksort(int l, int u)
{ int i, m;
if (l >= u) return; 10
swap(l, randint(l, u));
m = l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
如果函數的調用形式是quicksort(0, n-1)，那麼這段代碼將對一個全局數組x[n]進行排序。函數的兩個參數分別是將要進行排序的子數組的下標：l是較低的下標，而u是較高的下標。函數調用swap(i,j)將會交換x[i]與x[j]這兩個元素。第一次交換操作將會按照均勻分布的方式在l和u之間隨機地選擇一個劃分元素。
在《Programming Pearls》一書中包含了對Quicksort演算法的詳細推導以及正確性證明。在本章的剩餘內容中，我將假設讀者熟悉在《Programming Pearls》中所給出的Quicksort演算法以及在大多數初級演算法教科書中所給出的Quicksort演算法。
如果你把問題改為「在你編寫那些廣為應用的代碼中，哪一段代碼是最漂亮的？」我的答案還是Quicksort演算法。在我和M. D. McIlroy一起編寫的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol. 23, No. 11）中指出了在原來Unix qsort函數中的一個嚴重的性能問題。隨後，我們開始用C語言編寫一個新排序函數庫，並且考慮了許多不同的演算法，包括合並排序（Merge Sort）和堆排序（Heap Sort）等演算法。在比較了Quicksort的幾種實現方案後，我們著手創建自己的Quicksort演算法。在這篇文章中描述了我們如何設計出一個比這個演算法的其他實現要更為清晰，速度更快以及更為健壯的新函數——部分原因是由於這個函數的代碼更為短小。Gordon Bell的名言被證明是正確的：「在計算機系統中，那些最廉價，速度最快以及最為可靠的組件是不存在的。」現在，這個函數已經被使用了10多年的時間，並且沒有出現任何故障。
考慮到通過縮減代碼量所得到的好處，我最後以第三種方式來問自己在本章之初提出的問題。「你沒有編寫過的最漂亮代碼是什麼？」。我如何使用非常少的代碼來實現大量的功能？答案還是和Quicksort有關，特別是對這個演算法的性能分析。我將在下一節給出詳細介紹。
2.2 事倍功半
Quicksort是一種優雅的演算法，這一點有助於對這個演算法進行細致的分析。大約在1980年左右，我與Tony Hoare曾經討論過Quicksort演算法的歷史。他告訴我，當他最初開發出Quicksort時，他認為這種演算法太簡單了，不值得發表，而且直到能夠分析出這種演算法的預期運行時間之後，他才寫出了經典的「Quicksoft」論文。
我們很容易看出，在最壞的情況下，Quicksort可能需要n2的時間來對數組元素進行排序。而在最優的情況下，它將選擇中值作為劃分元素，因此只需nlgn次的比較就可以完成對數組的排序。那麼，對於n個不同值的隨機數組來說，這個演算法平均將進行多少次比較？
Hoare對於這個問題的分析非常漂亮，但不幸的是，其中所使用的數學知識超出了大多數程序員的理解范圍。當我為本科生講授Quicksort演算法時，許多學生即使在費了很大的努力之後，還是無法理解其中的證明過程，這令我非常沮喪。下面，我們將從Hoare的程序開
11
始討論，並且最後將給出一個與他的證明很接近的分析。
我們的任務是對示例2-1中的Quicksort代碼進行修改，以分析在對元素值均不相同的數組進行排序時平均需要進行多少次比較。我們還將努力通過最短的代碼、最短運行時間以及最小存儲空間來得到最深的理解。
為了確定平均比較的次數，我們首先對程序進行修改以統計次數。因此，在內部循環進行比較之前，我們將增加變數comps的值（參見示例2-2）。
【示例2-2】 修改Quicksort的內部循環以統計比較次數。
for (i = l+1; i <= u; i++) {
comps++;
if (x[i] < x[l])
swap(++m, i);
}
如果用一個值n來運行程序，我們將會看到在程序的運行過程中總共進行了多少次比較。如果重復用n來運行程序，並且用統計的方法來分析結果，我們將得到Quicksort在對n個元素進行排序時平均使用了1.4 nlgn次的比較。
在理解程序的行為上，這是一種不錯的方法。通過十三行的代碼和一些實驗可以反應出許多問題。這里，我們引用作家Blaise Pascal和T. S. Eliot的話，「如果我有更多的時間，那麼我給你寫的信就會更短。」現在，我們有充足的時間，因此就讓我們來對代碼進行修改，並且努力編寫出更短（同時更好）的程序。
我們要做的事情就是提高這個演算法的速度，並且盡量增加統計的精確度以及對程序的理解。由於內部循環總是會執行u-l次比較，因此我們可以通過在循環外部增加一個簡單的操作來統計比較次數，這就可以使程序運行得更快一些。在示例2-3的Quicksort演算法中給出了這個修改。
【示例2-3】 Quicksort的內部循環，將遞增操作移到循環的外部
comps += u-l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
這個程序會對一個數組進行排序，同時統計比較的次數。不過，如果我們的目標只是統計比較的次數，那麼就不需要對數組進行實際地排序。在示例2-4中去掉了對元素進行排序的「實際操作」，而只是保留了程序中各種函數調用的「框架」。
【示例2-4】將Quicksort演算法的框架縮減為只進行統計
void quickcount(int l, int u)
{ int m;
if (l >= u) return;
m = randint(l, u);
comps += u-l;
quickcount(l, m-1);
quickcount(m+1, u);
}
12
這個程序能夠實現我們的需求，因為Quichsort在選擇劃分元素時採用的是「隨機」方式，並且我們假設所有的元素都是不相等的。現在，這個新程序的運行時間與n成正比，並且相對於示例2-3需要的存儲空間與n成正比來說，現在所需的存儲空間縮減為遞歸堆棧的大小，即存儲空間的平均大小與lgn成正比。
雖然在實際的程序中，數組的下標（l和u）是非常重要的，但在這個框架版本中並不重要。因此，我們可以用一個表示子數組大小的整數(n)來替代這兩個下標（參見示例2-5）
【示例2-5】 在Quicksort代碼框架中使用一個表示子數組大小的參數
void qc(int n)
{ int m;
if (n <= 1) return;
m = randint(1, n);
comps += n-1;
qc(m-1);
qc(n-m);
}
現在，我們可以很自然地把這個過程整理為一個統計比較次數的函數，這個函數將返回在隨機Quicksort演算法中的比較次數。在示例2-6中給出了這個函數。
【示例2-6】 將Quicksort框架實現為一個函數
int cc(int n)
{ int m;
if (n <= 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
在示例2-4、示例2-5和示例2-6中解決的都是相同的基本問題，並且所需的都是相同的運行時間和存儲空間。在後面的每個示例都對這些函數的形式進行了改進，從而比這些函數更為清晰和簡潔。
在定義發明家的矛盾（inventor's paradox）(How To Solve It, Princeton University Press)時，George Póllya指出「計劃越宏大，成功的可能性就越大。」現在，我們就來研究在分析Quicksort時的矛盾。到目前為止，我們遇到的問題是，「當Quicksort對大小為n的數組進行一次排序時，需要進行多少次比較？」我們現在將對這個問題進行擴展，「對於大小為n的隨機數組來說，Quichsort演算法平均需要進行多少次的比較？」我們通過對示例2-6進行擴展以引出示例2-7。
【示例2-7】 偽碼：Quicksort的平均比較次數
float c(int n)
if (n <= 1) return 0
sum = 0
for (m = 1; m <= n; m++)
sum += n-1 + c(m-1) + c(n-m)
return sum/n
如果在輸入的數組中最多隻有一個元素，那麼Quichsort將不會進行比較，如示例2-6
13
中所示。對於更大的n，這段代碼將考慮每個劃分值m（從第一個元素到最後一個，每個都是等可能的）並且確定在這個元素的位置上進行劃分的運行開銷。然後，這段代碼將統計這些開銷的總和（這樣就遞歸地解決了一個大小為m-1的問題和一個大小為n-m的問題），然後將總和除以n得到平均值並返回這個結果。
如果我們能夠計算這個數值，那麼將使我們實驗的功能更加強大。我們現在無需對一個n值運行多次來估計平均值，而只需一個簡單的實驗便可以得到真實的平均值。不幸的是，實現這個功能是要付出代價的：這個程序的運行時間正比於3n（如果是自行參考（self-referential）的，那麼用本章中給出的技術來分析運行時間將是一個很有趣的練習）。
示例2-7中的代碼需要一定的時間開銷，因為它重復計算了中間結果。當在程序中出現這種情況時，我們通常會使用動態編程來存儲中間結果，從而避免重復計算。因此，我們將定義一個表t[N+1]，其中在t[n]中存儲c[n]，並且按照升序來計算它的值。我們將用N來表示n的最大值，也就是進行排序的數組的大小。在示例2-8中給出了修改後的代碼。
【示例2-8】 在Quicksort中使用動態編程來計算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += n-1 + t[i-1] + t[n-i]
t[n] = sum/n
這個程序只對示例2-7進行了細微的修改，即用t[n]來替換c(n)。它的運行時間將正比於N2，並且所需的存儲空間正比於N。這個程序的優點之一就是：在程序執行結束時，數組t中將包含數組中從元素0到元素N的真實平均值（而不是樣本均值的估計）。我們可以對這些值進行分析，從而生成在Quichsort演算法中統計比較次數的計算公式。
我們現在來對程序做進一步的簡化。第一步就是把n-1移到循環的外面，如示例2-9所示。
【示例2-9】 在Quicksort中把代碼移到循環外面來計算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += t[i-1] + t[n-i]
t[n] = n-1 + sum/n
現在將利用對稱性來對循環做進一步的調整。例如，當n為4時，內部循環計算總和為：
t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0]
在上面這些組對中，第一個元素增加而第二個元素減少。因此，我們可以把總和改寫為：
2 * (t[0] + t[1] + t[2] + t[3])
我們可以利用這種對稱性來得到示例2-10中的Quicksort。
【示例2-10】 在Quichsort中利用了對稱性來計算
t[0] = 0
14
for (n = 1; n <= N; n++)
sum = 0
for (i = 0; i < n; i++)
sum += 2 * t[i]
t[n] = n-1 + sum/n
然而，在這段代碼的運行時間中同樣存在著浪費，因為它重復地計算了相同的總和。此時，我們不是把前面所有的元素加在一起，而是在循環外部初始化總和並且加上下一個元素，如示例2-11所示。
【示例2-11】 在Quicksort中刪除了內部循環來計算
sum = 0; t[0] = 0
for (n = 1; n <= N; n++)
sum += 2*t[n-1]
t[n] = n-1 + sum/n
這個小程序確實很有用。程序的運行時間與N成正比，對於每個從1到N的整數，程序將生成一張Quicksort的估計運行時間表。
我們可以很容易地把示例2-11用表格來實現，其中的值可以立即用於進一步的分析。在2-1給出了最初的結果行。
表2-1 示例2-11中實現的表格輸出
N Sum t[n]
0 0 0
1 0 0
2 0 1
3 2 2.667
4 7.333 4.833
5 17 7.4
6 31.8 10.3
7 52.4 13.486
8 79.371 16.921
這張表中的第一行數字是用代碼中的三個常量來進行初始化的。下一行（輸出的第三行）的數值是通過以下公式來計算的：
A3 = A2+1 B3 = B2 + 2*C2 C3 = A2-1 + B3/A3
把這些（相應的）公式記錄下來就使得這張表格變得完整了。這張表格是「我曾經編寫的最漂亮代碼」的很好的證據，即使用少量的代碼完成大量的工作。
但是，如果我們不需要所有的值，那麼情況將會是什麼樣？如果我們更希望通過這種來方式分析一部分數值（例如，在20到232之間所有2的指數值）呢？雖然在示例2-11中構建了完整的表格t，但它只需要使用表格中的最新值。因此，我們可以用變數t的定長空間來替代table t[]的線性空間，如示例2-12所示。
【示例2-12】 Quicksoft 計算——最終版本
sum = 0; t = 0
15
for (n = 1; n <= N; n++)
sum += 2*t
t = n-1 + sum/n
然後，我們可以插入一行代碼來測試n的適應性，並且在必要時輸出這些結果。
這個程序是我們漫長學習旅途的終點。通過本章所採用的方式，我們可以證明Alan Perlis的經驗是正確的：「簡單性並不是在復雜性之前，而是在復雜性之後」 ("Epigrams on Programming," Sigplan Notices, Vol. 17, Issue 9)。

Ⅱ C語言怎麼對英文字母排序

根本就是.現代的英文字母就是拉丁字母
古代沒有拼音,就使用反切,就是用兩個認識會念的字,取第一個的聲母,取第二個的韻母,拼合起來就行了.
古代，中國的回族兄弟不學漢字，學習阿拉伯語，但他們用阿拉伯文的字母來拼寫口語（漢語），所以這是中國最早的拼音。
元朝，蒙古統治者用改變了的藏文的字母來拼寫漢語等語言，叫八思巴字。雖然不是專門拼寫漢語的，但是，也算漢語拼音的一種吧。
明朝，西方傳教士用拉丁字母拼寫漢語，是中國最早的拉丁字拼音。
清末明初，出現了用簡單的古字表現漢語語音的拼音方式。民國年間，政府制定了「注音字母」，就是這個系統的集中表現。現在台灣依然使用。但是，同時也出現了拉丁字的拼音運動，而且，跟左翼人士的政治運動結合很密切。
共和國成立後，立即由政府制定了「漢語拼音方案」，就是現在使用的這一套方案。聯合國也承認的。
**《現代漢語拼音方案》的出籠 **
1949年中華人民共和國成立後，就馬上著手研製拼音方案。1949年10月成立了民間團體「中國文字改革協會」，協會設立「拼音方案研究委員會」，討論拼音方案採用什麼字母的問題。
在1951年，毛澤東就指出：「文字必須改革，必須走世界文字共同的拼音方向」。但是，究竟採用什麼形式的拼音方案，他本人也是經過了反復斟酌的。毛澤東到蘇聯訪問時，他曾經問斯大林，中國的文字改革應當怎麼辦；斯大林說，中國是一個大國，可以有自己的字母。毛澤東回到北京之後，指示中國文字改革研究委員會制訂民族形式的拼音方案。同時，上海的新文字研究會停止推廣北方拉丁化新文字，等待新方案的產生。
1955年10月15日，全國文字改革會議在北京舉行。葉籟士在發言中說：「從1952年到1954年這個期間，中國文字改革研究委員會主要進行漢字筆畫式拼音方案的研究工作，經過了三年的摸索，曾經擬定幾種草案，都放在《漢語拼音方案草案初稿》（漢字筆畫式）里頭」。這次會議上印發給代表們六種拼音方案的草案，有四種是漢字筆畫式的，一種是拉丁字母式的，一種是斯拉夫字母式的。會議之後，當時的中國文字改革委員會主任吳玉章向毛澤東報告，他說，民族形式方案搞了三年，難以得到大家都滿意的設計，不如採用拉丁字母。毛澤東同意採用拉丁字母，並在中央開會通過。
在中國制定拼音方案的時候，蘇聯已經不再搞拉丁化，改為搞斯拉夫化，把所有的拉丁化民族文字一律改成了斯拉夫字母。蒙古人民共和國也把蒙古字母改成了斯拉夫字母。50年代，中國向蘇聯一邊倒，有人主張採用斯拉夫字母，跟蘇聯在文字上結盟。蘇聯派到中國的語言學家謝爾久琴柯也提出使用斯拉夫字母的建議。據說，蘇聯的一位副總理來中國訪問時，曾經向陳毅副總理說，希望中蘇兩國都採用相同的字母。陳毅副總理回答說，中國文化必須跟東亞和東南亞聯系，東亞和東南亞都習慣用拉丁字母。這樣，中國才沒有採用斯拉夫字母。如果我國當時採用了斯拉夫字母，我們今天使用計算機將會遇到更多的困難。中國政府當時在字母選擇上的決策，是非常正確的。
1956年1月20日，毛澤東在知識分子問題會議上，發表了贊成拉丁字母的講話。他說，「吳玉章同志的發言講的很好。關於文字改革的意見，我很贊成。在將來採用拉丁字母，你們贊成不贊成呀？我看，在廣大群眾里頭，問題不大；在知識分子里頭，有些問題。中國怎麼能用外國字母呢？但是，看起來還是採用這種外國字母比較好。吳玉章同志在這方面說得很有理由。因為這種字母很少，只有二十幾個，向一面寫，簡單明了。我們漢字在這方面實在比不上。比不上就比不上，不要以為漢字那麼好。有幾位教授跟我說，漢字是『世界萬國』最好的一種文字，改革不得。假使拉丁字母是中國人發明的，大概就沒有問題了。問題就出在外國人發明，中國人學習。但是，外國人發明中國人學習的事情是早已有之的。例如阿拉伯數字，我們不是久已通用了嗎？拉丁字母出在羅馬那個地方，為世界大多數國家所採用。我們用一下，是否就大有賣國的嫌疑呢？我看不見得。凡是外國好的東西，對我們有用的東西，我們就是要學，就是要統統拿過來，並且加以消化，變成自己的東西。我們中國歷史上，漢朝就是這么做的，唐朝也是這么做的。漢朝和唐朝，都是我國歷史上很有名很強盛的朝代。他們不怕吸收外國的東西，有好的東西就歡迎。只要態度和方法正確，學習外國的好東西，對自己是大有好處的。」（轉引自鄭林曦《論語說文》）。
此期間，群眾中也創制了不少的文字方案，寄到中國文字改革委員會。根據統計資料，從1950年到1955年8月31日全國文字改革工作會議為止，寄來的方案有655個，從1955年8月31日到1958年2月漢語拼音方案公布為止，寄來的方案有1000多個，從1958年2月到1980年文化大革命結束為止，寄來的方案有1667個。群眾設計的各種各樣的文字方案總共有3300多個。這種創製造文字方案的積極性，在中國文化的發展歷史上是空前的。這充分說明了語言規劃的社會性。
1955年2月，中國文字改革委員會設立了「拼音方案委員會」，開始設計漢語拼音方案，提出了《漢語拼音方案（草案）》。1956年2月12日，中國文字改革委員會發表《漢語拼音方案（草案）》，公開徵求意見。這個草案共有31個字母，其中有5個新字母（無點的i；長腳的n；帶尾的z,c,s），以便實現「一字一音」，不用變讀和雙字母。草案發表後在全國范圍內引起熱烈的討論，甚至海外華僑和留學生也提出了自己的意見。
1955年10月，國務院成立「漢語拼音方案審定委員會」，經過一年的工作，於1957年10月提出《修正草案》，11月1日由國務院全體會議第60次會議作為新的《漢語拼音方案（草案）》通過，提請全國人民代表大會審議，1958年2月11日，第一屆全國人民代表大會第五次會議正式批准《漢語拼音方案》。1958年秋季開始，《漢語拼音方案》作為小學生必修的課程進入全國小學的課堂。《漢語拼音方案》是拼寫規范化普通話的一套拼音字母和拼寫方式，是中華人民共和國的法定拼音方案。這個方案吸取了以往各種拉丁字母式拼音方案，特別是國語羅馬字和拉丁化新文字拼音方案的優點，它是我國三百多年拼音字母運動的結晶，是六十年來中國人民創造拼音方案經驗的總結，比任何歷史上一個拉丁字母式的拼音方案都更加完善和成熟。
《漢語拼音方案》有如下特點：
①只用國際通用的26個字母，不增加新字母；
②盡量不用附加符號（只用了兩個附加符號）；
③盡量不用變讀；
④採用y,w和隔音符號「'」來隔音；
⑤採用四個雙字母zh, ch, sh, ng；
⑥採用四個聲調符號來表示陰平、陽平、上聲、去聲四個調類；
⑦採用拉丁字母通用的字母表順序，並確定了漢語拼音字母的名稱。
周恩來在《當前文字改革的任務》的報告中說：「現在公布的漢語拼音方案，是在過去的直音、反切以及各種拼音方案的基礎上發展出來的。從採用拉丁字母來說，它的歷史淵源遠則可以一直追溯到350多年以前，近則可以說是總結了60年來我國人民創制漢語拼音方案的經驗。這個方案，比起歷史上存在過的以及目前還在沿用的各種拉丁字母的拼音方案來，確實更加完善。」
《漢語拼音方案》自製訂以來，得到迅速的推廣和應用。主要有如下方面。
①用於給漢字注音：從1958年秋季開始，全國小學的語文課本採用漢語拼音給漢字注音，接著，中學教科書、字典、詞典以及通俗讀物、掃盲課本也採用漢語拼音注音。《人民日報》等用漢語拼音字母給難字注音。1958年10月，中央工商行政管理局和中國文字改革委員會聯合發出通知，要求各種商標圖樣和商品包裝上加註漢語拼音字母。郵電局名、鐵路站名、氣象站名、城市街道名也都使用漢語拼音標注。1982年6月19日國家標准局發布了國家標准《中文書刊名稱漢語拼寫法》，規定國內出版的中文書刊在封面、或首頁、或封底、或版權頁上加註漢語拼音書名、刊名。
②用於教學普通話：《漢語拼音方案》公布後，陸續出版了利用漢語拼音編寫的普通話教材、讀物、字表、字典、詞典，促進了普通話的推廣和普及。在對外漢語教學中，《漢語拼音方案》已經成為外國人學習漢語進行全面訓練的不可缺少的工具。
③用於字典、詞典的注音、排序，書刊的索引。75卷的《中國大網路全書》採用漢語拼音排序，正文的每一個條目都註上了漢語拼音。
④作為我國少數民族創制和改革文字的共同基礎。我國已經有壯族、苗族、侗族、哈尼族、僳僳族、佤族、黎族、納西族、土族等少數民族採用漢語拼音字母相一致的字母形式。
⑤用於不便使用或不能使用漢字的領域：《漢語拼音方案》為盲文的點字和聾啞人的手語的制定提供了依據。漢語拼音還可用於手旗通訊、燈光通信中，用同漢語拼音字母對應的手旗訊號或燈光符號來傳遞信息。在電子計算機輸入漢字方面，拼音輸入法是一種最為普及的輸入方法。
1977年，聯合國地名標准化會議決定採用《漢語拼音方案》作為拼寫中國地名的國際標准。1978年9月，國務院轉發了《關於改用漢語拼音方案作為我國人名地名羅馬字母拼寫法的統一規范的報告》。1982年8月1日，國際標准化組織(ISO)文獻工作技術委員會決議採用漢語拼音作為世界文獻工作中拼寫中國專有詞語的國際標准，標准號：ISO7098-1982。《漢語拼音方案》已經從中國標准發展成為國際標准。
漢語拼音目前還是拼寫漢字的輔助工具.

Ⅲ 關於網路英語新詞的論文

總括來說，世界上語言可分為兩大類。一類是目前已經沒有人使用的，已不通行的，或已被廢棄了的，稱為「死」語言（dead language）；另一類是目前仍然通行的稱為「活」語言(living language)。希伯萊語、古拉丁語等屬於前者；而漢、英、日、西、法、德、俄等語言俱屬於後者，而且是其中最通行的幾種。

「活」的語言有一個很重要的共通點，就是它們都隨著時代的發展而變化。英語上這樣，其他的語言也是如此。不過，由於英語在世界上的通行度和通行范圍都勝於其他各種語言，所以其變化尤烈。

英語的變化主要表現於語法和詞彙兩方面，並籍這兩種變化推動發展，構成現代英語的基礎。近二十年來語言學理論最重大的進展之一是出現了「轉換——生成語法」（Transformational-generative Grammar),這種語言學理論的誕生使英語進一步科學化。與此同時，大量新詞彙的涌現使英語的表達力加強了，形式豐富了，因而使英語更趨生活化。

新詞彙的產生

新詞彙到底是怎樣產生的？

當人們發現新事物，遇到新問題，總結了新經驗，發展了新思想的時候，便需要新字和新詞來表達，這是因為舊有的、沿襲使用的表達方法已經不適合或不敷應用了。另一方面，由於以英語作母語及第二語言的國家遍及全球各洲，而各地的風 土人情、生活習慣和社會環境大有區別，這就必然會出現不同的表達形式和用語，而這些語匯中不少會被逐漸吸收進經典的英語辭典中，成為語言的一部分。

在目前日益進步的社會里，科學和技術是新詞彙的主要供應者，每當某一門科學發展到一個新階段的時候，就有相當大一批新詞涌現。在這些新詞當中，很多是該等科學的專用詞彙，鮮為外行人所知曉，只有專科字典及詞典才有收栽；但是，其中也有不少常被應用和引用，結果成了一般人所喜聞樂道的用語。

例如，當美國太空人成功地登陸用於月球時，英語中出現了moonwalk（月球漫步），lunar rove(月球車)，moonrock（月球標本車）等一系列有關的用詞。由於近年發射了不少人造衛星繞月運行，故此就很必要地創出了apolune(遠月點)和perilune(近月點)二詞。太空船與太空站在空間會合對接，使docking增添了一個新含義（靠泊），同義的還有linkup。發射太空船被視為人類科學發展的象徵，故很受注意。因此，不少與太空船有關的用詞已被廣泛使用，如CM(command mole:指令艙，指揮艙），splashdown （濺落），space sickness（宇航病），space age (太空時代）等。在談到探索deep space(深空間，遠空間）和其他太空現象時，quasar（類星射電源），pulsar（脈沖星），neutron srar （中子星）及神秘的black hole （太空黑洞）等已是耳熟能詳的用語。

近二十年來，遺傳學的迅速發展創造了許多使人耳目一新的詞彙，如genetic code（遺傳密碼），codon（密碼子），DNA（脫氧核糖核酸），transfa RNA（傳輸核糖核酸），messenger RNA（信使核糖核酸），transcription（信使核糖核酸的形成）等。這些新詞流行日廣，連到一般的書刊報道都有應用，故此早已廣大讀者所接受。

近年來發展迅猛的大了電腦工業帶來的新詞彙也著實不少。常聽常用的包括FORTRAM（公式翻譯程序語言），COBOL（面向商業的通用語言），ALGOL（演算法語言），BASIC（初學者的通用符號指令碼），absolute address（絕對地址），data bank（資料庫，資料庫），floppy dise（柔性塑料磁碟）pushdown（下推存儲器）等等。舊有詞如keyboard,terminal,memorym bit等也分別加添了新用法。

醫學的飛躍發展同樣帶來了大批新詞，包括了醫學上的技術性用語及新製成的葯品名稱，新發現的病菌、病毒等。其中如hotoscanning（光掃描），open heart surgery(開心手術)，picornabirus(換心人)，microcirculation（微血管循環）等都是近期出現的。一些用詞如the pill（口服避孕丸），test-tube baby（試管嬰兒），transsexual operation（變性生術）等已成日常用語。

核物理學發展的結果，好象要把人們帶進微觀世界。kron（K介子），muon（μ介子），pion(π介子)等陸續發現，lepton（輕子），baryon(重子)的分別，當然還有引起轟動的quark(誇克)。假設上由各種antimatter(反物質)如antiproton(反質子),antineutrino(反中微子),antiquark(反誇克)等組成的antiworld(反物質世界)也備受重視。

數學和其他學科也在不停地發展。在通俗的教研、科普讀物中,不難發現以下的名詞術語:NOT("非"邏輯運算元),parametric equation(變數方程),近年中小學推行的newmath(新數),artificial intelligence(人工智慧),magmetocardiogram(磁性心動掃描記圖)，IC (集成電路)，piscicide (魚類滅絕)，hot mooner (熱月學家),Sealab(海底實驗室)，radiosterilization（放射性消毒）等。新的學科也在不斷形成，例如bionics（仿生學），cryosurgery（冷凍手術），macrometereology（大氣象學），ocean engineering（海洋工程學），phytochemistry（植物化學），biotelemetry（生物遙測學），astrionics（太空電子學）等數十種新的學科在發展和壯大。

軍備競爭激烈，武器日新月異，自然也產生了不少新詞彙。ABM(antiballistic missile:反彈道導彈),MIRV(multiple independently-targetedreentry vehicle:多彈頭分導重返大氣層運載工具),the Bomb(核威懾),helilift(使用直升機運輸),Green Berets("綠色貝雷帽"特種部隊),grunt(步兵,beam weapons(死光武器)等,幾乎成了家喻戶曉的用語。

交通工具的改進,也使人有瞠目結舌之感。天空上充斥著SST(supersonic transport:超音速運輸機)，airbus（空中巴士），air-taxi（空中的士）；英法合制的Concorde（協調式飛機）在航空史上當然也占著重要地位。HST（hyper-sonic transport：特超音速飛機）的誕生，使飛機工業有了新發展。一些富裕的有閑人士經常乘搭噴氣式飛機到各地旅遊集會，成了一個特殊的階層，稱為jetset。噴氣式飛機的乘客有時也會患上這樣或那樣的不適症狀，統稱為jetsyndrome。在水面和陸地上，新型的交通工具接連出現，包括ACV （air-cushion vehicle：氣墊式運載工具），ATV（all-terrain vehicle:全地形車），hovercraft（氣墊船），freight-liner（貨櫃火車），bullet train（子彈車），aerotrain（懸浮火車）等。

除了科學和技術之外，動盪的政局、日趨變革的社會環境和世界性的文化及各方面的交流，也是英文新字的來源。例如自六十年代初期「－in 運動」的興起、轉化和發展，使這個「家族」膨脹得使人吃驚。從第一代的sit-in（靜坐示威）到第二代的teach-in （宣講會），以至第三代的be-in（頹廢派的社交集會），一共出現了數十個－in的用詞，其演變之速，實令人咋舌。

近年來，世界政壇風雲變幻。西歐諸國為加強團結，發展貿易，組織了EEC（European Economic Community:歐洲經濟共同體）。中東和南美、非洲的石油輸出國也組織了OPEC(Organization of Petroleum Exporting Countries:石油輸出國組織）。在美國爆發了水門事件之後，Watergate一字被廣泛應用以指任何的政治丑聞在政府內部，主張用武力解決爭端的一派人被稱為hawk（鷹派），主張和平手段的稱為dove（鴿派)，而dawk是介乎鷹派),主張和平手段的稱為dove(鴿派),而dawk是介乎鷹派與鴿派的消極反戰者。其他的政治用詞如establishment(政府),atomic club(原子俱樂部),advance man(先行人員,助選人員),pilitical animal(政治動物)等亦常見用於報刊之上。

世界性的經濟危機,通貨膨脹和工商業的發展也是新詞的重要來源之一。ASP(American Selling Price美國售價),slumpflation(蕭條膨脹),added-value tax(增值稅),Eurodollar(歐洲美元),petrodollar(石油美元),revenue sharing(國庫分享)等都是近期產物。

社會的變革在過去兩個年代中造成了很大的影響,不少基本意識形態受到了沖擊。女權運動的爆發產生了像Women'sLib(婦解運動),chairperson(主席),malechauvinist(大男子主義者),girlcott(抵制)等新用詞,但也促成了Men's Lib(男子解放運動)的誕生。六十年代末期美國黑人運動Black Power(黑色權力)爆發後,不少表示"…運動"的用語即仿此而出現,計有:Brown Power(褐色權力),Flower Power(花癲派權力),student power(學生權力),Red Power(紅色權力)等,更有人戲謔地創出green power一語，意指「金錢魔力」（因美元背面是綠色的）。

道德觀念的轉變造成了generation gap(代溝),而gap字的用途又在此基礎上多樣化,以致產生了credibility gap(信譽溝),culture gap(文化溝),communication gap(通信隔閡)等新詞。西方青年的思想與舊習俗社會的脫離,迫使他們要尋找發泄的途徑。於是Mary Jane(大麻),LSD(迷幻葯),upper(興奮劑),soft drug(軟毒品),hard drug(硬毒品),headshop(迷幻商店),commune(嬉皮士公社),psychedelphia(迷幻村)等詞又應運而生。一代一代的頹廢派亦相繼出現:hippie(嬉皮士),flower children(花癲派),Gentle People(溫和人),street people(街頭頹廢派),teenybopper(少年頹廢派),等等。

人們對環境污染的注視在近年特別顯著,這可見諸環境學家的倡議設立EarthDay(地球清潔日)和Eargh Week(地球清潔周)。"污染"這一用詞無日不見出現於報章雜志之中,較新的詞彙包括environmental pollution(環境污染) ,heat/thermal pollution(熱污染), internal pollution(體內污染),visual pollution(視覺污染),antipollutionist(反污染者),environmentalist(環境問題專家),dystrophication(河湖污染)等。

在教育和語言研究方面,也因教學方法和教學用具的改革而出現了一系列的新詞,如schoolbook(教科書式的),pass-fail(取否法),CAI(computer-assisted instruction(電腦輔助教學),audiovisuals(視聽教材),coedism(男女同校教育),preppie(預科學生),open classroom(開放教室),polyversity(多元大學),megaversity(超級大學),generative grammar(生成語法),kernel sentencd(核心句)和Chomskian(喬姆斯基理論的)等。

娛樂和體育亦是較大的新詞彙供應者。電台和電視台的audience rating(視聽率),call-in(電話節目),sitcom(長壽單元喜劇),soup opera(肥皂劇),prime time(黃金時間),imstant replay(即時重播),VTR(磁帶錄像),VCR(盒式錄像)等都是人所共知的用語了。多姿多採的新體育運動也豐富了英語的詞彙。近期新興的玩意包括skate-boarding(滑板運動),skydive(緩張傘跳傘)。land/sand yacht(沙灘艇,陸地風帆),hang glider(飛行風箏)是較高級的玩物。一些組合詞如cyclo -cross(自行車越野賽),roller hockey(滾軸冰球),demolition derby(撞車大賽)等也因新型運動的興起而相繼出現。體育家們還發明了slimnastics(減肥體操),isometrics(靜力鍛練)等健美身體、增強力量的方法,當然還有流行海外的中國kung fu(功夫)和日本的aikido(合氣道)等。

很多的新詞彙實際上已經進入人們的日常生活和每個家庭之中。現在,很多家庭里都有VCD(盒式錄像機);而原來稱為television set的電視機現被謔稱為television set 的電視機現被謔稱作box, gogglebox, idiot box, idiot'slantern。microwave oven(微波電鋦爐),autotimer(自動開關器)等是科技的新產物。videophone/picturephone(電視電話)亦在大量生產中。音響領域中的新詞也有quadraphony(四聲道),sensurrornd(杜比系統)等。七十年代最後一年才出產的Polarvision System(寶麗視系統)現已流行世界。較早期出現的telex(用戶電報)更是大公司和商行必設的通訊系統,當然還有IDDD(International DirectDistance Dialling:國際直通長途電話)。過去幾年生產了一種拉蓋即開的罐裝飲品,這種引起浪費和製造廢品的用完即丟的容器也有新名稱:thrwaway 或diposable 。

為了加強表達的力量，不少新的日用詞彙被創造出來了。這一類的用詞近年來大行其道,若不弄懂實難秘英、美、人士交談。舉例而言，精神病醫院的新名稱是funny farm,而fat farm卻是減肥中心;在停車場向違例停泊的車輛派告票的女警察被稱為meter maid(老虎機女郎),用油特多的"大食車"是gas eater。容易到手、尤其是以不正當手段得來的金錢叫做quick buck等等。

事實上,新詞彙產生的原因及其來源非常廣泛,可以說是由世界上各式各樣的變化促成的,故此無法盡量羅列。總而言之,大量新詞的涌現說明了社會在變化,英語在變化。

新詞彙的構成

根據研究和統計的結果，在六十年代和七十年代中，共出現了一萬多新的英文詞彙。然而，這個數目所包括的僅是已經確立並被廣泛使用的字和詞，一些被大多數人接納、太專門化或罕用的詞語尚不算在內。按這一萬多的新詞彙所做的研究，其構成法可以分為四大類。

<1>創新法—— 即創造出一個全新的英文字。據研究結果顯示，用這一種方法創出的新字新詞所佔比例較小，因為到目前為止，英語已經有了相當雄厚而根基鞏固的「班底」，新詞彙可由舊字和原有的詞根變化出來。用創新法構成的新詞彙包括。

(a)少量的社會科學及自然科學用詞,如:periapsis(近拱點),cladistics(遺傳分類學),penetralium(核心組織),ekistics(城市與區域計劃學),isomorphism(同構),quark(誇克);

(b)已通用的新產品的商標名(代表或用來指同一類產品)和已被用作普通名詞的專有名稱,如:lasercomp(激光電腦排版機),dolby system(杜比系統),miniteller(微型出納機),Rent-a-Train出租列車).polarvision system(寶麗視系統——即影即有電影系統),sealab(海底實驗室),watergate(政治丑聞),Frisbee(玩具飛碟);

(c)人名和地名等專有名詞衍變出的普通詞類,如:Hitchcockian(希治閣式的,懸疑的),Chandler wobble(錢德勒振盪),cocacolonization(美國化),a-go-go(阿哥哥舞廳),Mcluhanesque(麥克盧漢式的,電子化的);

(d)經常被使用的字首縮略詞(acronym)和普通的縮寫語(abbtreviation),如:STLT(Strategic Arms Limitation Talks:限制戰略武器會談),COBOL(Coommon business Oriented Language:面向商業的通用語言),BADGE(Base Air Defense Ground Environment:地域半自動防空警備體系),ACV(air-cushion vehicle:氣墊式運載工具),EEC(European Economic Community:歐洲經濟共同體,歐洲共同市場),comsat(communication satellite:通訊衛星);

(e)新的習語,包括以前未被收入正式詞典中的俚語(slang)和口語(colloquialism),如:posh(非常時髦的),bonkers(瘋狂的),easy meat(易辨的事),like a lead balloon(毫無作用),can of worms(一團糟),merchant of death(死亡販子),go for broke(盡最大努力),carry the can(面對責備,負起責任),selllike T shirts(貨如輪轉)。

用這一種方法創成的新字新詞中,還包括了一種把長字縮短而保持原義的新形式,如deli(delicatessen:熟食店),mod(modern:時髦的,摩登的),nat(mationalist:民族主義者),neut(neutron bomb:中子彈),divi(dividend:紅利),disco (discotheque:迪斯科,唱片夜總會)等。這種新形式與原字同樣流行,有睦甚而超過。

一部分商標名被接納為普通用詞後,用法、含意和詞類屬性上亦起了變化。如telex原為名詞(用戶電報,電報用戶直通電路),現可作動詞用,表示"以用戶電報通知";xerox原為名詞(乾式影印,靜電影印),現可作動詞;STP原為汽油附加劑,現指幻覺劑;Tom it一詞中,表示"逆來順受"。

<2>結合法——在舊有用詞的基礎上,加上前綴、後綴或其他構詞成分構成新詞,或使兩個舊有用詞或舊有用詞的部分結合起來成為新詞,或使兩個構詞成分結合成新詞。利用這種方法構成的新詞彙所佔比例較大,詞義亦較易理解推出。例如:microelectronics(micro+electronies:微電子學),antididnapping(anti +kidnapping:防綁架的),autocue(auto+cue:自動提示器),electrofishing (electro+fishing:電力捕魚),photobotany(photo+botany:光植物學),ecationese(ecation+ese:教育界術語),Pekingology(Peking+o+logy:北京學,北京問題研究),Dullesian(Dulles+ian:杜勒斯式的),robotesque(robot+esque:機械人似的);

Housrmanship(house+manship:英議員的雄辯),Americandom(American+dom:：美國人的世界),cryptosecurity(crypto+security:秘密安全部的),paint-in(paint+in:油漆示威),pedestrianization(pedestrian+ization:人行道化),peacenik(peace+nik:反戰運動分子);

diet pill(減肥丸),easy meat(易辨的事;易得的東西),Great Society(大社會),hard science(硬科學,自然科學),landmark(陸標),cardcarrying(典型的),carbecue(烤車架),boatel(汽艇旅館),chunnel(水底列車隧道);

electrophobia(electro+phobia:電氣恐怖症),bionics(bio+onics:仿生學),quarkonics(quark+onics:誇克學)。

有一部分前綴、後綴及構詞成分是特別多產或特別活躍的,其中包括anti-,auto,bio,electro-,Euro-,extra-,geo-,hyper-,-ian,immuno-,in-,-in,inter-,intra-,-logy,macro-,micro-,mini-,multi-,-nik,non-,prar-,-phobia-,photo-,poly-,psycho-等,此等構詞成分在構成新詞的過程中起著相當積極的作用.

<3>添義法---使舊詞添上新釋義.近年來,不少沿用的舊詞增添了新的含義.這一類形舊義新的字為數不少,碰上和使用時宜加註意,例如:

Happening:舊用法指一次事件,新用法指「哈普寧藝術」（一種目的使觀眾意外、驚奇和投入的舞台或其它形式的演出等。

這一部分的新詞還包括了一些過去只能作為某一種詞類使用，現在卻可作別一詞類運用的舊字。如H-bomb過去是名詞（氫彈），現在可作動詞，表示「用氫彈襲擊」；lookingglass過去是名詞，指「鏡子」，現在可作形容詞用，表示「顛倒的」，「亂七八糟的」等意。又如soul一字既加添了新意，指「黑人文化」，更可作形容詞，泛指「黑人的」，如soul music（黑人音樂，靈樂），soul food（黑人食物）等。

一個值得注意的構詞形式是back-formation，即所謂「逆序造詞」或「倒反構詞」。這是把一個現存的詞的真正後綴或貌似後綴的部分脫落而形成該詞的另一種詞類。例如先有 free association（自由發言，自由聯想），才有freeassociate;one-up（勝人一籌的，占上風的）和 one-upman勝...一籌，占...的上風）是從one-upmanship 一詞倒反構成的。laser（激光）本是一字首縮略詞，但是由於像是從lase變出來的名詞，故英、美人士又創出lase這個動詞，表示「放射激光」，「使受激光照射」。

<4>外借法---借用或吸收外來語。這種方法由來已久，英語中不少字和詞其實是從外國借來使用，最後成了英語中不可缺少的部分。這些外來語很多保留原來的樣貌，有些拉丁化拼音拼寫成英語，亦有些被改頭換面或按義譯成英語的。例如：

discothèque <法>:唱片夜總會

autostrada <意>:高速公路

autopista <西>:高速公路

mao tai <中>:茅台酒

sushi <日>:壽司

westpolitik <德>:(東歐國家的)西方政策

samizdat <俄>:地下出版(物)

favela <葡>:貧民窟,木屋區

haman <阿拉伯語>:海瑪姆(伊朗公眾浴堂)

又如black humor (黑幽默)原為法語humour noir,英美人士借用後按義改成正式英語;同樣地,found object (拾得藝術品)來自法語objet trouve。kirin來自日語kylin，後者又源於漢語ch』i lin（麒麟的舊拼寫法）。

（本文是作者為《10000英文新字字典》寫的導言）

Ⅳ 用C++交換排序

所謂交換，就是根據序列中兩個記錄值的比較結果來對換這兩個記錄在序列中的位置。交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。常見的交換排序有冒泡排序（Bubble Sort），雞尾酒排序（Cocktail Sort），奇偶排序（OddEven Sort），地精排序（Gnome Sort），快速排序（Quick Sort），臭皮匠排序（Stooge Sort），梳排序（Comb Sort），Bogo排序（Bogo sort）。下面介紹前六種：
（一）冒泡排序
最差時間復雜度：O(n^2)
最優時間復雜度：O(n)
平均時間復雜度：O(n^2)
最差空間復雜度：總共O(n)，需要輔助空間O(1)
穩定性：穩定
冒泡排序（Bubble Sort），它重復地走訪過要排序的數列，一次比較兩個元素如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。
冒泡排序演算法的運作如下：
1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
3.針對所有的元素重復以上的步驟，除了最後一個。
4.持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

實現代碼：

[cpp] view plain
void BubbleSort(int *a, int len)
{
for (int i=0; i<len; i++)
{
for (int j=len-1; j>i; j--)
{
if (a[j]<a[j-1])
swap(a[j], a[j-1]);
}
}
}

（二）雞尾酒排序

最差時間復雜度：O(n^2)
最優時間復雜度：O(n)
平均時間復雜度：O(n^2)
穩定性：穩定
雞尾酒排序（Cocktail sort），是冒泡排序的一種變形。它與冒泡排序的不同之處在於排序時是以雙向在序列中進行排序。數組中的數字本是無規律的排放，先對數組從左到右進行冒泡排序（升序），把最大值放到最右端，然後對數組從右到左進行冒泡排序（降序），把最小的數字放到最左端。然後再以此類推，以此改變冒泡的方向，並不斷縮小未排序元素的范圍。直到在一趟雙向冒泡後沒有發生交換，排序結束。

實現代碼：

[cpp] view plain
void CocktailSort(int* a, int len)
{
int bottom = 0;
int top = len-1;
bool swapped = true;

while (swapped)
{
swapped = false;
for (int i=bottom; i<top; i++)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
top = top-1;

for (int i=top; i>bottom; i--)
{
if (a[i]<a[i-1])
{
swap(a[i], a[i-1]);
swapped = true;
}
}
bottom = bottom+1;
}
}

（三）奇偶排序

最差時間復雜度：O(n^2)
穩定性：穩定
奇偶排序（OddEven Sort），是一種相對簡單的排序演算法，最初發明用於有本地互聯的並行計算。此演算法通過比較數組中相鄰的（奇-偶）位置數字對，如果該奇偶對是錯誤的順序（第一個大於第二個），則交換。下一步重復該操作，但針對所有的（偶-奇）位置數字對。如此交替下去，直到不發生交換，則排序結束。
在並行計算排序中，使用該演算法，每個處理器對應處理一個值，並僅有與左右鄰居的本地互連。所有處理器可同時與鄰居進行比較、交換操作，交替以奇-偶、偶-奇的順序。該演算法由Habermann在1972年最初發表並展現了在並行處理上的效率。但在單處理器串列運行此演算法，類似冒泡排序，較為簡單但效率並不特別高。

實現代碼：

[cpp] view plain
void OddEvenSort(int *a, int len)
{
bool swapped = true;
while (swapped)
{
swapped = false;
for (int i=0; i<len-1; i=i+2)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
for (int i=1; i<len-1; i=i+2)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
}
}

（四）地精排序

最差時間復雜度：O(n^2)
最優時間復雜度：O(n)
平均時間復雜度：O(n^2)
穩定性：穩定
地精排序（Gnome Sort），被Dick Grune稱為最簡單的排序演算法。整個演算法只有一層循環，默認情況下前進冒泡，一旦遇到冒泡的情況發生就往回冒，直到把這個數字放好，然後繼續前進，前進到數組最後一個數結束。此排序演算法雖然代碼極短，但效率不高。

實現代碼：

[cpp] view plain
void GnomeSort(int *a, int len)
{
int i=0;
while (i<len)
{
if (i==0 || a[i-1]<=a[i]){
i++;
}
else {
swap(a[i], a[i-1]);
i--;
}
}
}

（五）快速排序

最差時間復雜度：O(n^2)
最優時間復雜度：O(nlogn)
平均時間復雜度：O(nlogn)
穩定性：不穩定
快速排序（Quick Sort），使用分治法策略來把一個串列分為兩個子串列，左邊子串的值總小於右邊的子串。此演算法的三個步驟：
1．分解：將數組A[l...r]劃分成兩個（可能空）子數組A[l...p-1]和A[p+1...r]，使得A[l...p-1]中的每個元素都小於等於A(p)，而且，小於等於A[p+1...r]中的元素。下標p也在這個劃分過程中計算。
2．解決：通過遞歸調用快速排序，對數組A[l...p-1]和A[p+1...r]排序。
3．合並：因為兩個子數組時就地排序，將它們的合並並不需要操作，整個數組A[l..r]已經排序。

實現代碼（其他實現方法見「三種快速排序演算法的實現」）：

[cpp] view plain
int partition(int* a, int left, int right)
{
int x = a[right];
int i = left-1, j = right;
for (;;)
{
while(a[++i] < x) { }
while(a[--j] > x) { if(j==left) break;}
if(i < j)
swap(a[i], a[j]);
else break;
}
swap(a[i],a[right]);
return i;
}

void quickSort(int* a, int left, int right)
{
if (left<right)
{
int p = partition(a, left, right);

quickSort(a, left, p-1);
quickSort(a, p+1, right);
}
}

（六）臭皮匠排序

最差時間復雜度：O(n^2.7)
臭皮匠排序（Stooge Sort），是一種低效的排序演算法，在《演算法導論》第二版第7章的思考題中被提到，是由Howard Fine等教授提出的所謂「漂亮的」排序演算法。將數列平分為三個子串，依次遞歸排序前兩個子串、後兩個子串、前兩個子串，最後確保整個數列有序。此演算法在最壞情況下的遞歸式為T(n) = 3T(2n/3) + 1。由主定理很容易知道它的演算法復雜性為：T(n) = O(n^log(3/2, 3))。很顯然log(3/2, 3))>2，也就是說這個演算法比插入排序的O(n^2)性能還差。

實現代碼：

[cpp] view plain
void StoogeSort(int *a, int i, int j)
{
if(a[i]>a[j])
swap(a[i], a[j]);
if((i+1)>=j)
return;
int k = (j-i+1)/3;
StoogeSort(a, i, j-k);
StoogeSort(a, i+k, j);
StoogeSort(a, i, j-k);
}

Ⅳ 排序演算法是怎樣的

一、背景介紹

在計算機科學與數學中，排序演算法（Sorting algorithm）是一種能將一串資料依照特定排序方式進行排列的一種演算法。

最常用到的排序方式是數字順序以及字典順序。

有效的排序演算法在一些演算法（例如搜尋演算法與合並演算法）中是重要的， 如此這些演算法才能得到正確解答。

排序演算法也用在處理文字資料以及產生人類可讀的輸出結果。

基本上，排序演算法的輸出必須遵守下列兩個原則：

1、輸出結果為遞增序列（遞增是針對所需的排序順序而言）；

2、輸出結果是原輸入的一種排列、或是重組；

雖然排序演算法是一個簡單的問題，但是從計算機科學發展以來，在此問題上已經有大量的研究。 更多的新演算法仍在不斷的被發明。

二、知識剖析

查找和排序演算法是演算法的入門知識，其經典思想可以用於很多演算法當中。因為其實現代碼較短，應用較常見。 所以在面試中經常會問到排序演算法及其相關的問題。但萬變不離其宗，只要熟悉了思想，靈活運用也不是難事。

一般在面試中最常考的是快速排序和冒泡排序，並且經常有面試官要求現場寫出這兩種排序的代碼。對這兩種排序的代碼一定要信手拈來才行。除此之外，還有插入排序、冒泡排序、堆排序、基數排序、桶排序等。

三、常見的幾種演算法：

冒泡演算法、選擇排序、插入排序、希爾排序、歸並排序、快速排序

演算法的特點：

1、有限性：一個演算法必須保證執行有限步之後結束。

2、確切性： 一個演算法的每一步驟必須有確切的定義。

3、輸入：一個演算法有零個或多個輸入，以刻畫運算對象的初始情況，所謂零個輸入是指演算法本身給定了初始條件。

4、輸出：一個演算法有一個或多個輸出。沒有輸出的演算法毫無意義。

5、可行性：演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）。

Ⅵ 計算機專業學演算法的都學些什麼演算法，有什麼書可以看的學的話需要些什麼基礎的

計算機演算法非常多的
A*搜尋演算法
俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。
Beam Search
束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。
二分取中查找演算法
一種在有序數組中查找某一特定元素的搜索演算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。
Branch and bound
分支定界(branch and bound)演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。
數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。
Diffie–Hellman密鑰協商
Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。
Dijkstra』s 演算法
迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。
動態規劃
動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。
歐幾里得演算法
在數學中，輾轉相除法，又稱歐幾里得演算法，是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。
最大期望（EM）演算法
在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。
快速傅里葉變換(FFT)
快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。
哈希函數
HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。
堆排序
Heapsort是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。
歸並排序
Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
RANSAC 演算法
RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。
RSA加密演演算法
這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經專利失效，其被廣泛地用於電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。
並查集Union-find
並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。
Viterbi algorithm
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。