1樓：匿名使用者
氣泡排序，選擇排序，插入排序一般情況下要經過兩次迴圈，每次迴圈必須經歷時則需要o（n^2）。而歸併排序，快速排序則是o（n log2 n）。
而最壞情況下，快速排序會變成o（n^2），其餘不變（優化除外）。
望採納！！
以下排序演算法最壞情況下時間複雜度最低的是 a.氣泡排序 b.插入 c.選擇 d.快排
2樓：木頭釋然
在氣泡排序，插入排序，選擇排序，快速排序中，在最最壞情況下，快速排序的時間複雜為o(n2) ，插入排序o(n2)，選擇排序o(n2)，氣泡排序o(n2)。所以abcd時間複雜度是一樣的。
在快速排序演算法中，最為關鍵的就是選取乙個基值，將陣列分為大於基值以及小於基值兩部分，並返回基值所以在位置以利用於遞迴劃分。
對陣列a，設需要劃分的其中一段為a[p]~a[r]，我們期待的結果是得到乙個q，其中p<=q<=r，使得a[p]~a[q-1]<=a[q]<=a[q+1]~a[r]，這個時候原先的一段陣列被分成了三部分。
首先，設基值為這段陣列的最後乙個元素a[r]，我們希望最後得到的結果是a[r]現在對應的值在演算法結束後可以排在比他大和小的兩部分的中間愛。
然後令i=p-1; j=p，當發現有a[j]>x時，j繼續前進，不需要任何移動。當發現a[j]<=x時，我們需要將這個元素放到小於基值的一邊，於是將i自加1，並交換此時a[i]，與a[j]的元素，然後j自加1。這個時候i指向的是比基值小的那段資料的最後乙個元素，j指向的是第乙個還沒有判斷的剩餘元素。
上面一步不斷迴圈直到j指向了r，此時只剩下r沒有和基值判斷了，而a[r]本來就是基值，而除了a[r]以外，a[p]~a[i]是小於基值的部分，a[i+1]~a[r-1]是大於基值的部分，所以此時只需交換a[i+1]和a[r]即可。
由於對陣列a從頭到尾掃瞄一次就可以得到結果，因此這一部分演算法複雜度為o(n)
3樓：匿名使用者
1.選擇排序：不穩定，時間複雜度 o(n^2)
選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將l[i..n]中最小者與l[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。
2.插入排序：穩定，時間複雜度 o(n^2)
插入排序的基本思想是，經過i-1遍處理後,l[1..i-1]己排好序。第i遍處理僅將l[i]插入l[1..
i-1]的適當位置，使得l[1..i] 又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。
首先比較l[i]和l[i-1]，如果l[i-1]≤ l[i]，則l[1..i]已排好序，第i遍處理就結束了；否則交換l[i]與l[i-1]的位置，繼續比較l[i-1]和l[i-2]，直到找到某乙個位置j(1≤j≤i-1)，使得l[j] ≤l[j+1]時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。
3.氣泡排序：穩定，時間複雜度 o(n^2)
氣泡排序方法是最簡單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的「氣泡」，較小的元素比較輕，從而要往上浮。在氣泡排序演算法中我們要對這個「氣泡」序列處理若干遍。
所謂一遍處理，就是自底向上檢查一遍這個序列，並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對，即「輕」的元素在下面，就交換它們的位置。顯然，處理一遍之後，「最輕」的元素就浮到了最高位置；處理二遍之後，「次輕」的元素就浮到了次高位置。
在作第二遍處理時，由於最高位置上的元素已是「最輕」元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前面i-1遍的處理，它們已正確地排好序。
4.堆排序：不穩定，時間複雜度 o(nlog n)
堆排序是一種樹形選擇排序，在排序過程中，將a[n]看成是完全二叉樹的順序儲存結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關係來選擇最小的元素。
5.歸併排序：穩定，時間複雜度 o(nlog n)
設有兩個有序（公升序）序列儲存在同一陣列中相鄰的位置上，不妨設為a[l..m]，a[m+1..h]，將它們歸併為乙個有序數列，並儲存在a[l..h]。
6.快速排序：不穩定，時間複雜度 最理想 o(nlogn) 最差時間o(n^2)
快速排序是對氣泡排序的一種本質改進。它的基本思想是通過一趟掃瞄後，使得排序序列的長度能大幅度地減少。在氣泡排序中，一次掃瞄只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。
快速排序通過一趟掃瞄，就能確保某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基準點的左右只有乙個元素為止。
幾種排序的時間複雜度，可以參考一下
4樓：匿名使用者
這幾個的最壞情況下的時間複雜度都是一樣的，一定要比較的話快排比較快，但氣泡排序比較穩定，最壞的話都是一樣的
5樓：匿名使用者
顯然都一樣，如果論平均時間就是快排最快o(nlogn)，其餘的都是o(n^2)，但快排最壞時間也是o(n^2)
6樓：匿名使用者
最壞的情況下好像都是n^2吧。
在最壞的情況下，下列排序方法中時間複雜度最小的是（）a.氣泡排序 b.快速排序 c.插入排序d.堆排序
7樓：匿名使用者
答案是d，堆排序。
選項中的四種排序方法的最壞時間複雜度、最好時間複雜度 、平均時間複雜度分別為：
a、氣泡排序： o(n2) 、o(n) 、o(n2)。
b、快速排序： o(n2) 、o(nlog2n)、 o(nlog2n)。
c、插入排序： o(n2)、 o(n) 、o(n2)。
d、堆排序： o(nlog2n)、 o(nlog2n)、 o(nlog2n)。
所以，在最壞情況下，氣泡排序時間複雜度=快速排序時間複雜度=插入排序時間複雜度= o(n2)>堆排序時間複雜度= o(nlog2n)。答案選d。
8樓：匿名使用者
排序方法 最壞時間複雜度 最好時間複雜度
平均時間複雜度
直接插入 o(n2) o(n) o(n2)
簡單選擇 o(n2) o(n2) o(n2)
起泡排序 o(n2) o(n) o(n2)
快速排序 o(n2) o(nlog2n) o(nlog2n)
堆排序 o(nlog2n) o(nlog2n) o(nlog2n)
歸併排序 o(nlog2n) o(nlog2n) o(nlog2n)
所以選d
排序技術中 冒泡法和快速排序法的最壞情況下的比較次數是多少 其時間複雜度分別是多少
9樓：
冒泡和快排最壞情況下比較次數是一樣的：
1+2+3+...+(n-1)
時間複雜度：
插入，冒泡，選擇：o(n^2)
希爾：o(n^1.2)
快排，堆排：o(nlogn)
二分法插入排序 快速排序 歸併排序 堆排序 的時間複雜度分別是多少？
10樓：carry_小小
二分法插入排序 複雜度 o(nlogn)
快速排序 o(nlogn) 有可能退化歸併排序 o(nlogn) 比較快
堆排序 o(nlogn)最穩定的
11樓：匿名使用者
排序演算法
所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。 分類 在電腦科學所使用的排序演算法通常被分類為： 計算的複雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。
一般而言，好的表現是o。(n log n)，且壞的行為是ω(n2)。對於乙個排序理想的表現是o(n)。
僅使用乙個抽象關鍵比較運算的排序演算法總平均上總是至少需要ω(n log n)。 記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是乙個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄r和s，且在原本的串列中r出現在s之前，在排序過的串列中r也將會是在s之前。
一般的方法：插入、交換、選擇、合併等等。交換排序包含氣泡排序（bubble sort）和快速排序（quicksort）。
選擇排序包含shaker排序和堆排序（heapsort）。 當相等的元素是無法分辨的，比如像是整數，穩定度並不是乙個問題。然而，假設以下的數對將要以他們的第乙個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6) 在這個狀況下，有可能產生兩種不同的結果，乙個是依照相等的鍵值維持相對的次序，而另外乙個則沒有： (3, 1) (3, 7) (4, 1) (5, 6) (維持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的乙個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作乙個同分決賽。
然而，要記住這種次序通常牽涉到額外的空間負擔。 排列演算法列表 在這個**中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的氣泡排序（bubble sort） — o(n2)
雞尾酒排序 (cocktail sort, 雙向的氣泡排序) — o(n2)
插入排序 （insertion sort）— o(n2)
桶排序 （bucket sort）— o(n);
需要 o(k) 額外 記憶體
計數排序 (counting sort) — o(n+k); 需要 o(n+k) 額外 記憶體
歸併排序 （merge sort）— o(n log n); 需要 o(n) 額外記憶體
原地歸併排序 — o(n2) 二叉樹排序 （binary tree sort） — o(n log n); 需要 o(n) 額外記憶體
鴿巢排序 (pigeonhole sort) — o(n+k); 需要 o(k) 額外記憶體
基數排序 （radix sort）— o(n·k); 需要 o(n) 額外記憶體
gnome sort — o(n2) library sort — o(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定選擇排序 （selection sort）— o(n2)
希爾排序 （shell sort）— o(n log n)
如果使用最佳的現在版本 ***b sort — o(n log n)
堆排序 （heapsort）— o(n log n) **oothsort — o(n log n)
快速排序 （quicksort）— o(n log n)
期望時間, o(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序 introsort — o(n log n) patience sorting — o(n log n + k) 最外情況時間, 需要 額外的 o(n + k) 空間, 也需要找到最長的遞增子串行（longest increasing subsequence） 不實用的排序演算法 bogo排序 — o(n × n!) 期望時間, 無窮的最壞情況。 stupid sort — o(n3); 遞迴版本需要 o(n2) 額外記憶體 bead sort — o(n) or o(√n), 但需要特別的硬體 pancake sorting — o(n), 但需要特別的硬體 排序的演算法 排序的演算法有很多，對空間的要求及其時間效率也不盡相同。
下面列出了一些常見的排序演算法。這裡面插入排序和氣泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在乙個較小範圍內的排序演算法。
插入排序 氣泡排序 選擇排序 快速排序 堆排序 歸併排序 基數排序 希爾排序 插入排序 插入排序是這樣實現的： 首先新建乙個空列表，用於儲存已排序的有序數列（我們稱之為"有序列表"）。 從原數列中取出乙個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重複2號步驟，直至原數列為空。 插入排序的平均時間複雜度為平方級的，效率不高，但是容易實現。它借助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
氣泡排序 氣泡排序是這樣實現的： 首先將所有待排序的數字放入工作列表中。 從列表的第乙個數字到倒數第二個數字，逐個檢查：
若某一位上的數字大於他的下一位，則將它與它的下一位交換。 重複2號步驟，直至再也不能交換。 氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序 選擇排序是這樣實現的： 設陣列內存放了n個待排數字，陣列下標從1開始，到n結束。 i=1 從陣列的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。 如果i=n－1演算法結束，否則回到第3步 選擇排序的平均時間複雜度也是o(n²)的。 快速排序 現在開始，我們要接觸高效排序演算法了。
實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。
這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關係，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何乙個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查詢資料得另當別論了。
堆排序 堆排序與前面的演算法都不同，它是這樣的： 首先新建乙個空列表，作用與插入排序中的"有序列表"相同。 找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重複2號步驟，直至原數列為空。 堆排序的平均時間複雜度為nlogn,效率高（因為有堆這種資料結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要o(1)的時間複雜度，維護需要logn的時間複雜度），但是實現相對複雜（可以說是這裡7種演算法中比較難實現的）。 看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。
至少，他們的時間複雜度差了乙個數量級，乙個是平方級的，乙個是對數級的。 平均時間複雜度 插入排序 o(n2) 氣泡排序 o(n2) 選擇排序 o(n2) 快速排序 o(n log n) 堆排序 o(n log n) 歸併排序 o(n log n) 基數排序 o(n) 希爾排序 o(n1.25)
在插入排序希爾排序選擇排序快速排序堆排序歸併排序中
在插入排序 希爾排序 選擇排序 快速排序 堆排排序 歸併排序和基數排序中，平均比較次數最少的排序是快速排序，需要記憶體容量最多的是基數排序。時間複雜度 時間複雜度為 o nlogn 快速排序 堆排序和歸併排序 時間複雜度為 o n2 直接插入排序 起泡排序和 簡單選擇排序 時間複雜度為 o n 基數...
寫排序的幾種演算法,簡單選擇排序,直接插入排序,氣泡排序,詳細點
樓主留郵箱吧，我給你發過去 插入 void insert sort int a,int n 冒泡 int bubble sort int a,int n 選擇 int select sort int a,int n tmp min a min i a i a i tmp 選擇排序演算法與氣泡排序演算...
c 氣泡排序法，C 氣泡排序方法
define true 1 define false 0 typedef int keytype typedef struct recordtype void bubblesort recordtype r,int length include void reversal int x,int n i...