一組數據排序的最好最壞怎麼求

Ⅰ 數據結構內部排序問題

是的
在N個中排序，冒泡排序使用的時間是比較穩定的
而直接排序則視數列剛開始的排列有很大的差別
冒泡排序的時間復雜度是O（n^2）
選擇排序的時間復雜度最好為O（nlog2n）最壞為O（n^2）

二、幾種常見演算法的介紹及復雜度分析

1.基本概念

1.1穩定排序(stable sort)和非穩定排序

穩定排序是所有相等的數經過某種排序方法後，仍能保持它們在排序之前的相對次序，。反之，就是非穩定的排序。

比如：一組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序後為a1,a2,a4,a3,a5，

則我們說這種排序是穩定的，因為a2排序前在a4的前面，排序後它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩定的了。

1.2內排序( internal sorting )和外排序( external sorting)

在排序過程中，所有需要排序的數都在內存，並在內存中調整它們的存儲順序，稱為內排序； 在排序過程中，只有部分數被調入內存，並藉助內存調整數在外存中的存放順序排序方法稱為外排序。

1.3演算法的時間復雜度和空間復雜度

所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。 一個演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間。

2.幾種常見演算法

2.1冒泡排序 （Bubble Sort）

冒泡排序方法是最簡單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的「氣泡」，較小的元素比較輕，從而要往上浮。在冒泡排序演算法中我們要對這個「氣泡」序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對，即「輕」的元素在下面，就交換它們的位置。顯然，處理一遍之後，「最輕」的元素就浮到了最高位置；處理二遍之後，「次輕」的元素就浮到了次高位置。在作第二遍處理時，由於最高位置上的元素已是「最輕」元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前面i-1遍的處理，它們已正確地排好序。

冒泡排序是穩定的。演算法時間復雜度是O(n ^2)。

2.2選擇排序 （Selection Sort）

選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。

選擇排序是不穩定的。演算法復雜度是O(n ^2 )。

2.3插入排序 （Insertion Sort）

插入排序的基本思想是，經過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)三次插入。

直接插入排序是穩定的。演算法時間復雜度是O(n ^2)

2.4堆排序

堆排序是一種樹形選擇排序，在排序過程中，將A[n]看成是完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。

堆排序是不穩定的。演算法時間復雜度O(nlog n)。

2.5歸並排序

設有兩個有序（升序）序列存儲在同一數組中相鄰的位置上，不妨設為A[l..m]，A[m+1..h]，將它們歸並為一個有序數列，並存儲在A[l..h]。

其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。

2.6快速排序

快速排序是對冒泡排序的一種本質改進。它的基本思想是通過一趟掃描後，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。快速排序通過一趟掃描，就能確保某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基準點的左右只有一個元素為止。

快速排序是不穩定的。最理想情況演算法時間復雜度O(nlog2n)，最壞O(n ^2)。

Ⅱ 各種排序演算法最好和最壞情況比較

都不知道怎麼回答，各種排序說的也太多了，這里講幾種簡單的吧，希望對你有幫助！
比如n個順序存儲元素進行排序，a[0]做「哨兵」（即a[0]不存數據，而是用作輔存空間使用）的情況
1 直接插入排序：比較次數 最少n-1次；最多(n-1)(n+2)/2
移動次數 最少0； 最多(n-1)(n+4)/2
使用一個輔助存儲空間，是穩定的排序；

2 折半插入排序：比較次數 最少與最多同，都是n*log2n（其中2為底，下邊表示同），
移動次數 最少0，最多時間復雜度為O(n2);(n的平方，以下也如此表示)；
使用一個輔助存儲空間，是穩定的排序；

3 冒泡排序： 比較最少為：n-1次，最多時間復雜度表示為o(n2);
移動次數最少為0，最多時間復雜度表示為O(n2);
使用一個輔存空間，是穩定的排序；

4 簡單選擇排序： 比較次數沒有多少之分，均是n(n-1)/2;
移動次數最少為0，最多為3(n-1);
使用一個輔存空間，是穩定的排序；

5 快速排序：比較和移動次數最少時間復雜度表示為O(n*log2n);
比較和移動次數最多的時間復雜度表示為O(n2);
使用的輔助存儲空間最少為log2n，最多為n的平方；是不穩定的排序；

6 堆排序： 比較和移動次數沒有好壞之分，都是O(n*log2n);
使用一個輔存空間，是不穩定的排序；

7 2-路歸並排序：比較和移動次數沒有好壞之分，都是O(n*log2n);
需要n個輔助存儲空間，是穩定的排序；

另外還有很多的排序方法如 希爾排序，基數排序，2-路插入排序 等等很多的排序方法，這里就不一一列舉了，希望列舉的對你有幫助！！

Ⅲ 數據結構，分別求最好情況，和最壞情況，比較次數，和移動次數。感謝

這是一個簡單的直接插入排序程序，最好的情況是在初始序列就已完全有序的情況，則此時比較次數為n-1次，移動次數為0次。最壞情況為初始序列為完全逆序。此時總的比較次數為n*(n-1)/2，總的移動次數也是n*(n-1)/2

Ⅳ 快速排序方法的最壞和最好情況分別是什麼

最好的情況是樞紐元選取得當，每次都能均勻的劃分序列。 時間復雜度O(nlogn)

最壞情況是樞紐元為最大或者最小數字，那麼所有數都劃分到一個序列去了 時間復雜度為O(n^2)

快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。

它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

Ⅳ 各種排序演算法最好和最壞情況比較

最壞情況下比較次數最少的為D）堆排序：
A）冒泡排序 需要比較O(n^2)次（n(n - 1)/2次），即序列逆序的情況
B）簡單選擇排序，無論是否最壞都需要O(n^2)次（n(n - 1)/2次）
C）直接插入排序，最壞情況需要比較O(n^2)次（n(n - 1)/2次）
D）堆排序，無論是否最壞比較O(nlog2n)次
E）快速排序，最壞情況退化為冒泡排序，需要比較O(n^2)次（n(n - 1)/2次）

Ⅵ 使用冒泡排序法給一億個數排序最好和最壞的情況各需要計算幾次

最好和最壞的情況都是需要進行 （1億-1）*（1億-2）*（1億-3）*（1億-4）*（1億-5）*（1億-6）*（1億-7）*（1億-8）....................................次循環。

如果將冒泡時的交換數據算3次計算。
那麼最好的情況是（1億-1）*（1億-2）*（1億-3）*（1億-4）*（1億-5）*（1億-6）*（1億-7）*（1億-8）....................................次計算，
最壞的情況是 3*（1億-1）*（1億-2）*（1億-3）*（1億-4）*（1億-5）*（1億-6）*（1億-7）*（1億-8）....................................次計算。