快速排序演算法導論

① 計算機科學的「兩本聖經」是什麼

第一本：《演算法導論》原書名——《Introction to Algorithms》，

第二本：高德納（Donald E.Knuth）的《計算機程序設計藝術》（《The Art Of Computer Programming》）

計算機科學是一門包含各種各樣與計算和信息處理相關主題的系統學科，從抽象的演算法分析、形式化語法等等，到更具體的主題如編程語言、程序設計、軟體和硬體等。計算機科學分為理論計算機科學和實驗計算機科學兩個部分。

(1)快速排序演算法導論擴展閱讀：

研究課題

①、計算機程序能做什麼和不能做什麼（可計算性）；

②、如何使程序更高效的執行特定任務（演算法和復雜性理論）；

③、程序如何存取不同類型的數據（數據結構和資料庫）；

④、程序如何顯得更具有智能（人工智慧）；

⑤、人類如何與程序溝通（人機互動和人機界面）。

相關獎項

計算機科學領域的最高榮譽是ACM設立的圖靈獎，被譽為是計算機科學的諾貝爾獎。它的獲得者都是本領域最為出色的科學家和先驅。華人中首獲圖靈獎的是姚期智先生.他於2000年以其對計算理論做出的諸多「根本性的、意義重大的」貢獻而獲得這一崇高榮譽。

專業介紹

培養目標

本專業培養德、智、體全面發展，具有計算機應用技術的基礎理論知識，具備計算機及相關設備的維護與維修、行業應用軟體、平面圖像處理、廣告設計製作、動畫製作、計算機網路及網站建設與管理、資料庫管理與維護等應用能力和操作能力的高等技術應用性人才。

計算機應用基礎、計算機組裝與維護、計算機區域網絡的建設與管理、網路工程、操作系統、伺服器、資料庫的開發與應用、網站建設與網頁設計、C/C++語言、Visual Basic語言、平面設計、3D圖形設計、多媒體設計、專業英語。

就業方向

畢業生主要面向交通系統各單位、交通信息化與電子政務建設與應用部門、各類計算機專業化公司、廣告設計製作公司、汽車營銷技術服務等從事IT行業工作。

參考資料：網路-計算機科學

② 《演算法導論》（原書第二版）。這本書裡面的程序是用什麼寫的是java嗎

這本書的程序是用偽代碼加英文注釋寫的，學過C/C++/JAVA的都能看懂。

原書摘錄如下（快速排序）：
QUICKSORT'(A,p,r)
while p<r
do △ Partition and sort left subarray.
q <- PARTITION(A,p,r)
QUICKSORT'(A,p,q-1)
p <- q+1

③ 為什麼《演算法導論》中的數組序號是從1開始的

c語言下標從零開始是個錯誤，並且 index 也是一個有誤導性的名詞，它表示的是偏移量，明明應該用 offset。
然後 c 的徒子徒孫都學了它，導致現在很多人都誤以為下標應該從 0 開始。
早期蠻荒時代，很多東西都不科學，演算法導論作者致力於與落後文明作斗爭，然而卻遭到了樓主你的不理解，實乃編程屆一大憾事。
我再說一遍，C 是結構化的匯編，下標基 0 是受到了 PDP-11 指令集的影響，更老的語言（比如 Fortran）都是基 1 的。
另外用 0/非 0 代表 false/true 也是 PDP-11 中 TST 指令和 Z 位的行為。
可能是這本書強調演算法的求學思想，所以從一更加符合數學的數組規定。
但是編程的時候，指針這個東西會經常用到，如果用a(o)作為第一個元素 那麼*a+n就等同於a(n) 比較方便
演算法導論上的這個問題呢，我覺得我比較同意樓上的看法，這個書上面的很多的程序並不是可以敲上去直接運行的，他只是偽代碼，思想而已，給人看的，人類的普遍思維是從1開始，那麼書頁就是從1開始了
說編程語言是給機器看而偽代碼是給人看的簡直是逗大家笑吧...編程語言設計出來就是給人看的....
另外從0開始在很多方便都極好....我覺得寫多代碼都能體會到吧..
幫算導洗地：
演算法導論通篇用的是偽代碼 是給人類閱讀理解的 不是設計給機器去運行的
而絕大多數情況下， index 從 1 開始更符合人類直覺（如果你對這點有異議請參考的答案 ）
但少數情況下， index 從 0 開始更符合人類直覺。例如書中 hashing 還有 FFT 那塊內容， index 是從 0 開始的。
其實寫幾天 Pascal 你就適應啦。。

④ 演算法導論中的快排演算法實現出錯

我未學過pascal，但看你的代碼總覺得posion函數有問題，下面是我的C代碼，不知你能否看懂
int Posion(int *ar,int l,int h){
int k=ar[l];
while(l<h){
while(l<h&&k<=ar[h])
h--;
ar[l]=ar[h];
while(l<h&&k>=ar[l])
l++;
ar[h]=ar[l];
}
ar[l]=k;
return l;
}

⑤ 數據結構 如何快速排序

這個過程對於初學者的確有點復雜，建議你看下嚴蔚敏數據結構書上的例子，多耐心看下，然後再看代碼。另外也可以參考下演算法導論，關於快排這本書有單獨章節講解。自己去弄懂會很深刻的。

⑥ 快速排序演算法問題，看看大家的思路

/*剛看了下演算法導論，寫了一個，感覺效率還可以，你看看 */
#include <stdio.h>

static int a[8] = {3, 7, 2, 8, 4, 5, 3, 9};

void swap (int *m, int *n)
{
int temp = *m;
*m = *n;
*n = temp;
}

int partition (int p, int r)
{
int j;
int x = a[r];
int i = p - 1;

for (j=p; j<r; j++)
{
if (a[j] <= x)
{
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i+1], &a[r]);

return i+1;
}

void quicksort (int p, int r)
{
int q;

if (p < r)
{
q = partition (p, r);
quicksort (p, q - 1);
quicksort (q+1, r);
}
}

int main ()
{
int i;
int len = sizeof(a) / 4;

for (i=0; i<len; i++)
printf ("%d ", a[i]);
printf ("\n");

quicksort (0, len - 1);

for (i=0; i<len; i++)
printf ("%d ", a[i]);
printf ("\n");

return 0;
}
/* 我空間里還有一篇文章是關於qsort的，glibc里的源碼，我也沒怎麼看懂，感興趣可以研究下 */
剛才看了樓上給出的網址，文章寫的不錯，裡面給的網址對qsort的分析也很透徹，感覺人外有人，學習的路還很長阿。

⑦ C語言一個快速排序的問題 我應該是傳參的問題 但我不知道該如何改 請大師指教 謝謝

下面是《演算法導論》里快速排序的實現，希望對你有用：

#include<stdio.h>
voidswap(int*a,int*b){
intt=*a;
*a=*b;
*b=t;
return;
}
intpartition(inta[],intstart,intend){
intx=a[end];
inti=start-1;
intj;
for(j=start;j<=end-1;j++){
if(a[j]<=x){
i+=1;
swap(a+i,a+j);
}
}
swap(a+i+1,a+end);
returni+1;
}

voidqsort(inta[],intstart,intend){
if(start>=end)return;
intp=partition(a,start,end);
qsort(a,start,p-1);
qsort(a,p+1,end);
}

voidprint(inta[],intstart,intend){
inti;
for(i=start;i<=end;i++)
printf("%d",a[i]);
printf("
");
return;
}

intmain(void){
inta[5]={1,1,2,2,3};
inti;
qsort(a,0,4);
print(a,0,4);
printf("Pleaseinput5numbers:
");
while(1){
for(i=0;i<=4;i++)
scanf("%d",a+i);
qsort(a,0,4);
print(a,0,4);
}
return0;
}

⑧ 快速排序的代碼，跟我們學的不一樣，大神解釋一下。

快排一般我們採用第一個或者最後一個元素作為樞紐元 這里是採用任意一個元素作為樞紐元

具體的解釋可參考《演算法導論》快速排序那一小節

⑨ 誰能舉個例子解釋一下，什麼是快速排序，冒泡排序，直接插入排序，堆序法thx

快速排序：quicksort: 找數組中一個數，把比他大的放到左邊，比他小的放到右邊，然後用遞歸排他左右邊的，直到排完，復雜度O（nlgn）。
4,2,1,6，5.開始選4-2，1，4，6，5，再在2，1里選2-1，2，在6，5里選6-5，6 這樣就完了1，2，4，5，6.

冒泡排序： bubblesort：簡單的方法，從第一個數開始，依次和後面比較，比後面大就往後移動，直到排完，舉例： 5，1，2，3，4. 先看5-1，5，2，3，4-1，2，5，3，4-1，2，3，5，4-1，2，3，4，5.這例子特殊，一下排完，事實上復雜度為O（n*n）；
插入排序： insertion sort： 簡單的方法，和打牌時排序一樣，復雜度O（n*n）
1，3，2，4，7，5-1，2，3，4，7，5-1，2，3，4，5，7.

堆： heapsort： 和樹比較像，有根大枝小或根小枝大的特點，很難講明白，時間復雜度為O（n*lgn）

建議看《演算法導論》，或《programming pearls》 很清楚。

⑩ 演算法導論的作品目錄

目錄（Table of Contents）
前言（Preface）
第一部分（Part I） 基礎（Foundations）
第一章 計算中演算法的角色（The Role of Algorithms in Computing）
第二章 開始（Getting Started）
第三章 函數的增長率（Growth of Functions）
第四章 遞歸（Recurrences）
第五章 概率分析與隨機化演算法（Probabilistic Analysis and Randomized Algorithms）
第二部分（Part II） 排序與順序統計（Sorting and Order Statistics）
第六章 堆排序（Heapsort）
第七章快速排序（Quicksort）
第八章 線性時間中的排序（Sorting in Linear Time）
第九章 中值與順序統計（Medians and Order Statistics）
第三部分（Part III） 數據結構（Data Structures）
第十章 基本的數據結構（Elementary Data Structures）
第十一章 散列表（Hash Tables）
第十二章 二叉查找樹（Binary Search Trees）
第十三章 紅-黑樹（Red-Black Trees）
第十四章 擴充的數據結構（Augmenting Data Structures）
第四部分（Part IV） 高級的設計與分析技術（Advanced Design and Analysis Techniques）
第十五章 動態規劃（Dynamic Programming）
第十六章 貪婪演算法（Greedy Algorithms）
第十七章 分攤分析（Amortized Analysis）
第五部分（Part V） 高級的數據結構（Advanced Data Structures）
第十八章 B-樹（B-Trees）
第十九章 二項式堆（Binomial Heaps）
第二十章 斐波納契堆（Fibonacci Heaps）
第二十一章 不相交集的數據結構（Data Structures for Disjoint Sets）
第六部分（Part VI） 圖演算法（Graph Algorithms）
第二十二章 基本的圖演算法（Elementary Graph Algorithms）
第二十三章 最小生成樹（Minimum Spanning Trees）
第二十四章單源最短路徑（Single-Source Shortest Paths）
第二十五章 全對的最短路徑（All-Pairs Shortest Paths）
第二十六章 最大流（Maximum Flow）
第七部分（Part VII） 精選的主題（Selected Topics）
第二十七章 排序網路（Sorting Networks）
第二十八章矩陣運算（Matrix Operations）
第二十九章 線性規劃（Linear Programming）
第三十章 多項式與快速傅里葉變換（Polynomials and the FFT）
第三十一章 數論演算法（Number-Theoretic Algorithms）
第三十二章 字元串匹配（String Matching）
第三十三章 計算幾何學（Computational Geometry）
第三十四章 NP-完備性（NP-Completeness）
第三十五章 近似演算法（Approximation Algorithms）
第八部分（Part VIII） 附錄：數學背景（Mathematical Background）
附錄A 求和（Summations）
附錄B 集合，等等。（Sets, Etc.）
附錄C 計數與概率（Counting and Probability）
參考文獻（Bibliography）
索引（Index）