動圖演示：
https://www.runoob.com/w3cnote/bubble-sort.html

選擇排序
簡單選擇排序
在未排序的序列中，選出最小的元素和序列的首位元素交換，接下來在剩下的未排序序列中，再選出最小元素與序列的第二位元素交換，以此類推，最后形成從小到大的已排序序列

對N個記錄進行簡單選擇排序，比較次數(shù)和移動次數(shù)分別為O(N?^2??)和O(N)。

需要比較N*(N-1)/2次，時間復雜度O(N²)

空間復雜度S(N)=O(1)

穩(wěn)定性：不穩(wěn)定
堆排序
時間復雜度O(NlogN)
空間復雜度O(1)
不穩(wěn)定

實現(xiàn)堆排序的一種簡單做法是：額外開辟一個輔助的數(shù)組空間，將堆頂元素逐一放入輔助數(shù)組里，最后再把輔助數(shù)組的內(nèi)容復制回原始的數(shù)組

這種方法的額外空間復雜度為O(1)

對N個記錄進行堆排序，需要的額外空間為O(N)。F

堆排序僅需一個記錄大小供交換用的輔助存儲空間，所以空間復雜度為O(1)

插入排序
簡單插入排序
穩(wěn)定

最好情況O(N)
最壞情況O(N²)

核心思想：將待排序的一組序列分為已經(jīng)排好序的和未排好序的兩個部分
初始狀態(tài)時，已排序序列僅包含第一個元素，未排序序列中的元素為除了第一個以外的N-1個元素
此后將未排序序列中的元素逐一插入到已排序的序列中
如此往復
經(jīng)過N-1次插入后，未排序序列中元素的個數(shù)為0，則排序完成

希爾排序

交換排序
冒泡排序

快速排序
對N個記錄進行快速排序，在最壞的情況下，其時間復雜度是O(N²)

在平均狀況下，排序n 個項目要Ο(nlogn) 次比較

快速排序又是一種分而治之思想在排序算法上的典型應用

• 從數(shù)列中挑出一個元素，稱為 “基準”
• 重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作
• 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序

對N個不同的數(shù)據(jù)采用冒泡排序進行從大到小的排序，當元素基本有序時交換元素次數(shù)肯定最多。F

得看"有序"是正序還是逆序

要從50個鍵值中找出最大的3個值，選擇排序比堆排序快。

T

下列排序算法中，哪種算法可能出現(xiàn)：在最后一趟開始之前，所有的元素都不在其最終的位置上？（設待排元素個數(shù)N>2）
A.冒泡排序
B.插入排序
C.堆排序
D.快速排序

下面四種排序算法中，穩(wěn)定的算法是：
A.堆排序
B.希爾排序
C.歸并排序
D.快速排序

https://blog.csdn.net/Jessieeeeeee/article/details/107307114

總結

以上是生活随笔為你收集整理的选择排序 插入排序 交换排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。