有趣的演算法（1）排序

0.寫在前面

閑來無事，去圖書館借了兩本演算法方面的書，畢竟現在全民CS，哈哈，我也來學習學習~然鵝，發現很多演算法書都是理論居多，介紹了推導過程、實現思路，就是不給出完整的程序。所以啊，我就以借來的書互為參考，邊看書，邊寫程序。

在學習的過程中總結一下下，不定期更新這篇文章，添加一些有意思的演算法，水平有限，歡迎大佬移步評論區批評指正~

1.快速排序

快速排序，顧名思義就是排序速度比較快的排序演算法。假設存在一個存儲無序元素的數組，將數組的第一個元素作為基準值，先從數組的最右邊向左遍歷，尋找小於基準值的元素，再從數組的左邊向右遍歷，尋找大於基準值的元素，然後將二者交換；再繼續遍歷，直至左邊遍歷和右邊遍歷相遇。而後遞歸調用此演算法對序列進行排序。

說了那麼多，都不如用個實例最能說明問題。那就用最俗氣的學生成績排序來說明問題，相信每一個學過C語言的都遇到過這個問題，哈哈~

結合注釋，上程序~

#include "stdafx.h"n#include<stdlib.h>nnstruct student//定義結構體，用於存儲學生的姓名與成績n{ntchar name[20];ntint score;n};nstruct student record[20];//定義結構體類型的數組nvoid Quick_sort(int left,int right);//函數聲明nnint _tmain(int argc, _TCHAR* argv[])n{ntint i,n;ntsystem("color 02");ntprintf("輸入學生的數量:");//讀入學生的成績ntscanf("%d",&n);ntprintf("輸入名字與分數:n");ntfor(i=1;i<=n;i++)nttscanf("%s %d",record[i].name,&record[i].score);nntQuick_sort(1,n);//調用快速排序函數nntprintf("排序的結果:n");//輸出排序的結果ntfor(i=n;i>=1;i--)nttprintf("第%d名 : %s(%d)n",(n-i+1),record[i].name,record[i].score);nntgetchar();ntgetchar();ntreturn 0;n}nnvoid Quick_sort(int left,int right)//快速排序函數n{ntint i,j;ntstruct student base,temp;ntif(left>right)//如果左邊標號小於右邊，則 returnnttreturn;nntbase=record[left];//左邊第一個值作為基準nti=left;ntj=right;nntwhile(i!=j)//左右標號不相等時nt{nttwhile(record[j].score>=base.score&&i<j)//從數組右邊開始尋找小於基準的值ntttj--;nttwhile(record[i].score<=base.score&&i<j)//從數組左邊開始尋找大於基準的值nttti++;nttif(i<j)//找到二者，且左邊標號小於右邊標號時，交換二者ntt{nttttemp=record[i];ntttrecord[i]=record[j];ntttrecord[j]=temp;ntt}nt}ntrecord[left]=record[i];//將基準值與一次尋找結束時的中間某值交換ntrecord[i]=base;//再次取基準值n Quick_sort(left,i-1);//遞歸調用，解決ntQuick_sort(i+1,right);n}n

沒有運行結果的程序不是好程序，上截圖~

由此可見，Andrew同學的成績最棒嘛，Michel同學需要加油啦~

2.冒泡排序與快速排序比較

同樣是排序演算法，我冒泡排序憑什麼輸給你快速排序？你快在哪呢？

我也有同樣的疑問，所以我寫了一個程序，以此來驗證，做一個不嚴謹的小實驗。

在一個容量為50000的數組中隨機存儲一定數量大小隨機的數據，然後分別調用快速排序和冒泡排序演算法進行排序並輸出排序結果。為了使得二者的差異明顯，我選擇40000個元素進行排序。

廢話不多說，上程序~

// 排序速度比較.cpp : 定義控制台應用程序的入口點。n//nn#include "stdafx.h"n#include<stdlib.h>nnint record[50000];//用於比較的數組nvoid Quick_sort(int left,int right);//快速排序聲明nvoid Maopao(int num);//冒泡排序函數聲明nnint _tmain(int argc, _TCHAR* argv[])n{ntint num,i,choice=1;ntsystem("color 02");ntprintf("輸入數組的範圍:");//數組有多少個元素ntscanf("%d",&num);ntfor(i=0;i<num;i++)//調用隨機函數給數組中的元素賦值nt{nttrecord[i]=rand()%num;nt}nntprintf("n(1-快速排序；2-冒泡排序）:");ntscanf("%d",&choice);ntif(choice==1)nttQuick_sort(0,num-1);//40000,1s不到，結果輸出完畢14.96秒ntelsenttMaopao(num);//40000,25sntprintf("排序的結果:n");ntfor(i=0;i<num;i++)nt{nttprintf("%d ",record[i]);nt}nntnntgetchar();ntgetchar();ntreturn 0;n}nnvoid Quick_sort(int left,int right)//快速排序函數n{ntint L,R,base,temp;ntif(right<left)nttreturn;ntL=left;ntR=right;ntbase=record[left];ntwhile(L!=R)nt{nttwhile(record[R]>=base&&L<R)ntttR--;nttwhile(record[L]<=base&&L<R)ntttL++;nttif(L<R)ntt{nttttemp=record[R];ntttrecord[R]=record[L];ntttrecord[L]=temp;ntt}nt}ntrecord[left]=record[L];ntrecord[L]=base;n Quick_sort(left,L-1);n Quick_sort(L+1,right);n}nnvoid Maopao(int num)//冒泡排序函數n{ntint i,j,temp;ntfor(i=num-1;i>=0;i--)nttfor(j=0;j<=i;j++)ntt{ntttif(record[j]>record[j+1])nttt{ntttttemp=record[j];nttttrecord[j]=record[j+1];nttttrecord[j+1]=temp;nttt}ntt}n}n

首先選擇快速排序對數組進行排序，我掐著手機秒錶來做這個不嚴謹的實驗~

對40000個隨機排列的元素進行排序，選擇1-快速排序，從按下回車，到有結果輸出不到一秒，結果輸出完畢，耗時14.96秒，所以大部分時間都耗在結果輸出上。

接下來我們調用不服氣的冒泡排序，同樣的測試方法~

從選擇2-冒泡排序之後，直到結果輸出完畢，耗時25秒左右。

雖然，這個小小的實驗不嚴謹，但是還是足以說明快速排序比冒泡排序快~

後記

如果覺得有問題的話，歡迎評論區指教~

如果覺得還不錯的話，點個讚唄~