直接選擇排序演算法復雜

❶ 選擇排序法復雜度

穩定性比較
插入排序、冒泡排序、二叉樹排序、二路歸並排序及其他線形排序是穩定的。
選擇排序、希爾排序、快速排序、堆排序是不穩定的。

時間復雜性比較
插入排序、冒泡排序最優為O(n),最壞為O(n^2),平均O(n^2）；
快速排序最優為O(nlogn),最壞為O(n^2),平均O(nlogn);
堆排序最優為O(nlogn),最壞為O(nlogn),平均O(nlogn);
線形排序的時間復雜性為O(n)。

輔助空間的比較
線形排序、歸並排序的輔助空間為O(n),快速排序的輔助空間為O(logn),其它排序的輔助空間為O(1)。

其它比較
插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。
反而在這種情況下，快速排序反而慢了。當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。
若待排序的記錄的關鍵字在一個明顯有限范圍內時,且空間允許時用桶排序。
當n較大時，關鍵字元素比較隨機，對穩定性沒要求宜用快速排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性有要求時，空間允許的情況下宜用歸並排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性沒有要求時宜用堆排序。

演算法描述太長了。
binary seach 二分查找啊。

6 層排序 乘3加1 Shell Sort Times 3 plus 1

7 層排序 乘4 Shell Sort Times 4
層排序？ 看名字是 希爾排序吧。

還有上面的名字也翻譯錯了。。。
這些演算法都很容易搜到的。

給你個網址吧：

http://www.nocow.cn/index.php/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

不過是用PASCAL語言描述的，部分C++語言描述。

// 直接插入排序
void insertionSort( int *array )
{
int i, j;
int key;

for( i = 1; i < size; ++i )
{
key = array[i];
j = i - 1;
while( j >= 0 && array[j] > key )
{
array[j+1] = array[j];
--j;
}
array[j+1] = key;
}
}

// 折半插入排序
void binary_insertiont_sort( int *array )
{
for( int i = 1; i < size; ++i )
{
int key = array[i];
int low = 0;
int high = i - 1;
while( low <= high )
{
int mid = ( low + high ) / 2;
if( array[mid] > key )
high = mid - 1;
else
low = mid + 1;
}
for( int j = i - 1; j > high + 1; --j )
array[j+1] = array[j];
array[j] = key;
}
}

// 選擇排序
void selectSort( int *array )
{
int i, j, k;

for( i = 0; i < size - 1; ++i )
{
k = i;
for( j = i + 1; j < size; ++j )
if( array[k] > array[j] )
k = j;
if( k != i )
{
j = array[k];
array[k] = array[i];
array[i] = j;
}
}
}

// 二分查找法
void binarySeach( int *array, int key )
{
int low = 0;
int high = n - 1; // n是array的長度
int flag = 0;
while( low <= high )
{
int mid = ( low + high ) / 2;
if( array[mid] > key )
high = mid - 1;
else if( array[mid] < key )
low = mid + 1;
else
{
printf( "%d\n", mid+1 );
flag = 1;
break;
}
}
if( !flag )
printf( "NOFOUND!\n" );
}

其他的還沒寫。。

❷ 求各種查找和排序的時間復雜度

冒泡排序是穩定的，演算法時間復雜度是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)。

2.7 希爾排序

在直接插入排序演算法中，每次插入一個數，使有序序列只增加1個節點，並且對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為 增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換。D.L.shell於1959年在以他名字命名的排序演算法中實現了這一思想。演算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。

希爾排序是不穩定的，其時間復雜度為O(n ^2)。

排序類別
時間復雜度
空間復雜度
穩定

1
插入排序
O(n2)
1
√

2
希爾排序
O(n2)
1
×

3
冒泡排序
O(n2)
1
√

4
選擇排序
O(n2)
1
×

5
快速排序
O(Nlogn)
O(logn)
×

6
堆排序
O(Nlogn)
1
×

7
歸並排序
O(Nlogn)
O(n)
√

❸ 排序演算法的時間復雜度

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序演算法，就是如何使得記錄按照要求排列的方法。排序演算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。

一個優秀的演算法可以節省大量的資源。在各個領域中考慮到數據的各種限制和規范，要得到一個符合實際的優秀演算法，得經過大量的推理和分析。

空間復雜度(Space Complexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時間復雜度是O(n^2),空間復雜度是O(1) 。

而一般的遞歸演算法就要有O(n)的空間復雜度了，因為每次遞歸都要存儲返回信息。一個演算法的優劣主要從演算法的執行時間和所需要佔用的存儲空間兩個方面衡量。

(3)直接選擇排序演算法復雜擴展閱讀：

排序演算法經過了很長時間的演變，產生了很多種不同的方法。對於初學者來說，對它們進行整理便於理解記憶顯得很重要。每種演算法都有它特定的使用場合，很難通用。因此，我們很有必要對所有常見的排序演算法進行歸納。

排序大的分類可以分為兩種：內排序和外排序。在排序過程中，全部記錄存放在內存，則稱為內排序，如果排序過程中需要使用外存，則稱為外排序。下面講的排序都是屬於內排序。

內排序有可以分為以下幾類：

(1)、插入排序：直接插入排序、二分法插入排序、希爾排序。

(2)、選擇排序：直接選擇排序、堆排序。

(3)、交換排序：冒泡排序、快速排序。

(4)、歸並排序

(5)、基數排序

❹ 常見排序演算法以及對應的時間復雜度和空間復雜度

排序 ：將雜亂無章的數據，按照一定的方法進行排列的過程叫做排序。

排序大的分類可分為 內排序 和 外排序 ，不需要訪問外存就能進行排序的叫做內排序。

排序也可以分為 穩定排序 和 不穩定排序

穩定排序 ：假設在待排序的文件中，存在兩個或兩個以上的記錄具有相同的關鍵字，在用某種排序法排序後，若這些相同關鍵字的元素的相對次序仍然不變，則這種排序方法是穩定的。即；若 a[i]=a[j] , a[i] 在 a[j] 之前，經過排序後 a[i] 依然在 a[j] 之前。冒泡排序、直接插入排序、二分插入排序、歸並排序，基數排序都是穩定排序。
不穩定排序 ：直接選擇排序、堆排序、快速排序、希爾排序，猴子排序。

以升序為例，比較相鄰的元素，如果第一個比第二個大，則交換他們兩個。如果兩個元素一樣大，則繼續比較下一對。所以冒泡排序是一種穩定排序。

選擇一個基準元素,通常選擇第一個元素或者最後一個元素,通過一趟掃描，將待排序列分成兩部分,一部分比基準元素小,一部分大於等於基準元素,此時基準元素在其排好序後的正確位置,然後再用同樣的方法遞歸地排序劃分的兩部分。快速排序是不穩定排序。

將序列分為兩個部分{{有序序列},{無序}}，每次處理就是將無序數列的第一個元素與有序數列的元素從後往前逐個進行比較，找出插入位置，將該元素插入到有序數列的合適位置中。如果碰到相等的元素，就會把它插入到想等元素後面，順序不會改變，所以直接插入排序是穩定排序。

在直接插入排序的基礎上，對有序序列進行劃分。例如：序列為 {{a[0]......a[i-1]},a[i]} 其中 {a[0]......a[i-1]} 為有序序列，取 a[(i-1)/2] ，將其與 a[i] 比較，即可確定 a[i] 的范圍 (a[0]...a[(i-1)/2] 或者 a[(i-1)/2]...a[i-1]) ,然後繼續在已確定的范圍內進行二分。范圍依次縮小為： 1/2、1/4、1/8、1/16...... 可快速確定a[i]應該插入的位置。二分插入排序也是穩定排序。

將整個序列分割成若干個小的子序列，每個子序列內分別進行插入排序。一般情況下步長取n/2。直到最後一次步長為1，即所有元素在一個組中進行排序。由於希爾排序是先將整個序列劃分為多個子序列進行排序，相同的元素順序在這個過程中順序可能會被打亂，所以希爾排序是不穩定排序。

從待排序的數據元素中，選出最小或最大的元素與序列第一個數交換。直到所有數據排完。直接選擇排序是不穩定排序。例如： {3，3，1} ，第一次排序就將1和第一個3交換，想等元素的順序改變了。

以n=10的一個數組49, 38, 65, 97, 26, 13, 27, 49, 55, 4為例

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。
最大堆:每個節點的值都大於等於它的孩子節點。
最小堆:每個節點的值都小於等於它的孩子節點。
最大堆第0個數據是最大數，最小堆第0個數據是最小數。
堆排序是不穩定排序

思想

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
如何將兩個有序序列合並？(升序)
{a[0]......a[i-1]},{b[0]......b[j-1]}
若 b[0]<a[0] ，取 b[0] 放入數組 c 中，然後繼續比較數組 a 和 b 中的第一個元素，直到數組 a 和 b 中最後一對元素比較完成。

思想

將數組分成二組 a , b 如果這二組組內的數據都是有序的，那麼就可以按照上述方法對這二組數據進行排序。如果這二組數據是無序的？
可以將 a , b 組各自再分成二組。遞歸操作，直到每個小組只有一個數據，每個小組只有一個元素所以我們可以認為它已經是有序序列，然後進行合並。
先分解後合並。
歸並排序是穩定排序

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。從最低位起從0-9依次掃描序列，一邊掃描一邊將掃描到的數據加到新的序列中，得到一個序列。然後比較高一位，重復上述操作，直到最高位排序完成。數列就變成一個有序序列。基數排序是穩定排序。

以全是二位數的序列舉例

無限猴子定理 :指一隻猴子隨機在打字機鍵盤上按鍵，最後必然可以打出法國國家圖書館的每本圖書。

時間復雜度最低1次，最高可執行到世界的盡頭。。。

❺ 八大排序演算法與復雜度

  在處理大批量數據時，有序化的數據可以在很大程度上提高演算法效率。
直接插入排序  先總結一下數據結構的八大排序，分別是插入排序中的 直接插入排序 ， 希爾排序 ，交換排序中的 起泡排序 ， 快速排序 ，選擇排序中的 直接選擇排序 ， 堆排序 ，以及 歸並排序 和 基數排序 。
  如何評價排序的優劣呢？除了正確，易讀和容錯（自動檢錯，報錯並通過與用戶對話來糾錯）以外，性能是一個重要指標。

  演算法性能是指運行一個演算法所需要的時間長短和內存多少，他們分別稱為 時間復雜性 和 空間復雜性 。

  1）有些計算機需要用戶提供程序運行時間的上限。一旦達到這個上限，程序將被強制結束。
  2）一個正在開發的程序可能需要一個令人滿意的實時響應。
  選擇什麼樣的時間單位（程序步）來度量演算法運行時間呢？對少量的輸入，演算法瞬間就運行完了。所以對演算法性能的評價總是對大的輸入量而言的。
  假設輸入量是n，演算法運行時間是n的函數T(n)，我們研究當很大時，T(n)是什麼級別。這里就用到了 大O記法 ：如果存在正常數c和n ₀ ，使得當n≥n ₀ 時，T(n)≤ c*f(n)，則記為T(n)=O(f(n))。

  演算法所需空間包括固定部分和變動部分。固定部分與輸入量或規模無關，主要包括程序碼空間和常量，變數和對象的定長所佔的空間。變動部分與輸出量有關，主要包括遞歸棧空間和中間處理所需空間。如果用P表示演算法，S(P)表示空間需求，那麼S(P)=c（固定部分）+S _p （變動部分）。演算法的空間復雜性分析重點是變動部分S _p 。

  此外，如果一種排序實施前後，關鍵碼相同的任意兩個數據元素其前後次序沒有發生變化，那麼這個排序方法就被稱作是 穩定的 ，否則就是 不穩定的 。

原理：從待排序集的第1個數據元素開始，依次選擇數據元素，與有序子集的數據元素依次從後往前進行比較，選擇插入位置。

穩定性： 穩定 。

原理：以增量為步長劃分子序列，即同一子序列的數據元素，其下標步長等於增量。對每個子序列實施直接插入排序。不斷縮小增量，當增量為1時，所有數組元素都在一個子序列中，成為有序集。
   通俗來講，增量即為數組中元素下表的差值，假設步長為4，及a[0]，a[4]，a[8]…為一個子序列。實行直接插入排序後，將增量縮小為一半，直至增量縮小為1。

穩定性： 不穩定

原理：把數組分為左右兩個半區，左半區為有序子集，右半區為無序子集。開始時，左半區為空。在無序子集中，從後往前，兩兩相鄰元素比較，逆序則交換。最後交換的位置成為有序子集的上界。直到一趟起泡排序中沒有發生交換，排序停止。

穩定性： 穩定 。

原理：取無序子集中的第一個數據元素作為基準，將無序子集分為左右兩個半區，左半區不大於基準，右半區不小於基準；然後對左右半區重復上述操作，知道各半區元素個數為1.

穩定性： 不穩定 ，主要是劃分演算法Partition造成的。

原理：將數組分為左右兩個半區，左半區為有序子集，右半區為無序子集。開始時，有序子集為空。在無序子集中，選出最小元素，與無序子集第一個元素交換，再將第一個元素並入有序子集中。重復上述操作。

穩定性： 穩定 。

原理：
1）將數組分為左右兩個半區，左半區為有序子集，右半區為無序子集。開始時，有序子集為空。
2）將無序子集創建為大根堆。
3）將堆化為無序子集首位數據元素交換，將交換後的尾元素並入有序子集，然後把縮小的無序子集調整為大根堆。
4）重復步驟3）n-2次。

穩定性： 不穩定 。

原理：
1） 歸並 （一般指二路歸並）：將兩個有序表合成一個新的有序表。包含關鍵碼的原始數組ini分為左右兩個有序分區（歸並段）[s,m]和[m+1,e]，將他們按序歸並，一個歸並段存儲到一個輔助數組（merge）中。
2） 迭代歸並 ：包含關鍵碼的原始數組ini按長度len劃分為幾個連續的歸並段，每一個歸並段都有序，用二路歸並將相鄰歸並段合成一個長度為2len的歸並段並存入輔助數組，這個過程稱為 一趟歸並 。重復上述步驟。
 ①剩下一個長度為len的歸並段和一個長度不足len的歸並段，繼續調用二路歸並。
 ②只剩下一個長度為len或不足len的歸並段，直接移至輔助數組merge。

穩定性： 穩定 。

原理：採用「分配」和「收集」技術，從關鍵碼的低位到高位進行比較。有十個隊列作為分配用的」箱子「，編號0~9。遵照先進先出原則，從個位開始排序，到十位，百位，以此類推。

穩定性： 穩定 。

❻ 各種排序演算法的總結和比較

排序演算法是《數據結構與演算法》中最基本的演算法之一。

排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等。用一張圖概括：

點擊以下圖片查看大圖：

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸並排序；

O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。

關於穩定性

穩定的排序演算法：冒泡排序、插入排序、歸並排序和基數排序。

不是穩定的排序演算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

包含以下內容：

排序演算法包含的相關內容具體如下：

冒泡排序演算法

冒泡排序（Bubble Sort）也是一種簡單直觀的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。

選擇排序演算法

選擇排序是一種簡單直觀的排序演算法，無論什麼數據進去都是 O(n?) 的時間復雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不佔用額外的內存空間。

插入排序演算法

插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序演算法，它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

希爾排序演算法

希爾排序，也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序演算法。

歸並排序演算法

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

快速排序演算法

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。

堆排序演算法

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。

計數排序演算法

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

桶排序演算法

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在於這個映射函數的確定。

基數排序演算法

基數排序是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。

❼ 直接選擇排序演算法在最好情況下的時間復雜度為多少

關鍵字比較次數永遠是n(n-1)/2，記錄移動次數最多為3(n-1)，最少0次，前者起主導作用，因此實際上時間復雜度還是O(n^2)。

在直接選擇排序中，共需要進行n-1次選擇和交換，每次選擇需要進行 n-i 次比較 (1<=i<=n-1),而每次交換最多需要3次移動，因此，總的比較次數C=(n*n - n)/2,總的移動次數 3(n-1).由此可知，直接選擇排序的時間復雜度為 O(n2) 。

(7)直接選擇排序演算法復雜擴展閱讀：

直接選擇排序的基本思想是：第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R[1]~R[n-1]中選取最小值，與R[1]交換，....，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，.....，第n-1次從R[n-2]~R[n-1]中選取最小值。

與R[n-2]交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。當記錄佔用位元組數較多時，通常比直接插入排序的執行速度快些。由於在直接選擇排序中存在著不相鄰元素之間的互換，因此，直接選擇排序是一種不穩定的排序方法。