經典入門 排序

2022-09-23 00:28:36 字數 768 閱讀 1810

題目描述:對輸入的n個數進行排序並輸出。

輸入:輸入的第一行包括一個整數n(1<=n<=100)。接下來的一行包括n個整數。

輸出:可能有多組測試資料,對於每組資料,將排序後的n個整數輸出,每個數後面都有一個空格。每組測試資料結果佔一行。

(1)氣泡排序

氣泡排序的時間複雜度為o(n^2),根據題目給出的n的取值範圍,我們可以估算出n^2的數量級僅在萬的取值範圍中,並沒有到達10^7,因此使用氣泡排序在該題的1s執行時間內是完全可以接受的;同時氣泡排序的空間複雜度為o(n),即大致需要100*32bit的記憶體,這樣所需的記憶體也不會超過限定大小(32mb)。

#includeint main()

}} for(int i=0;i(2)快速排序 

如果修改n的取值範圍,使其最大能達到10000,那氣泡排序因其較高的時間複雜度就不能被採用,於是我們不得不使用諸如快速排序、歸併排序等具有更優複雜度的排序演算法。

c++已經為我們編寫了快速排序庫函式,只需呼叫該函式,便能輕易地完成快速排序。

#include#includeusing namespace std;

int main()

int main()

buf[1000];

bool cmp(e a,e b)

} buf[1000];

int main()

sort(buf, buf+n);

for( int i=0; i}

return 0;

}

排序 快速排序

快速排序由c a r hoare 1962 開發的,該演算法在陣列中選擇一個稱為主元 pivot 的元素,將陣列分為兩部分,是的第一部分中的...

排序 快速排序

快速排序的話,說先要要用一個隨機的函式rand ,解決好時間複雜度在最壞的情況下出現的o n 2 的問題。 思想 選擇第i個數 由隨機函式生...

排序 快速排序

這種演算法是對氣泡排序的改進喲,算是比較快的排序了 這裡有原理講解,嘿嘿嘿 演算法8 5 快速排序 include using namespace std define maxsize 20 順序表的最大長度 typedef struct elemtype 順序表的儲存結構 typedef struct...