一揖闸、排序概念
排序：對(duì)一序列對(duì)象根據(jù)某個(gè)關(guān)鍵字進(jìn)行排序矿卑。
穩(wěn)定：如果 a 原本在 b 前面，而 a 與 b 的值相等审残，排序之后 a 仍然在 b 的前面；
不穩(wěn)定：如果 a 原本在 b 的前面斑举，而 a 與 b 的值相等搅轿，排序之后 a 可能會(huì)出現(xiàn)在b的后面；內(nèi)排序：所有排序操作都在內(nèi)存中完成富玷；
外排序：由于數(shù)據(jù)太大璧坟，因此把數(shù)據(jù)放在磁盤中既穆，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行；排序耗時(shí)的操作：比較雀鹃、移動(dòng)幻工；
-
排序分類：
- 交換類：冒泡排序、快速排序黎茎；此類的特點(diǎn)是通過不斷的
比較和交換進(jìn)行排序囊颅； - 插入類：簡(jiǎn)單插入排序、希爾排序傅瞻；此類的特點(diǎn)是通過
插入的手段進(jìn)行排序踢代； - 選擇類：簡(jiǎn)單選擇排序、堆排序俭正；此類的特點(diǎn)是
看準(zhǔn)了再移動(dòng)奸鬓； - 歸并類：歸并排序；此類的特點(diǎn)是
先分割后合并掸读；
- 交換類：冒泡排序、快速排序黎茎；此類的特點(diǎn)是通過不斷的
歷史進(jìn)程：一開始排序算法的復(fù)雜度都是在
O(n^2)串远，希爾排序的出現(xiàn)打破了這個(gè)僵局。
二儿惫、排序算法
最簡(jiǎn)單的排序算法
最簡(jiǎn)單的排序?qū)崿F(xiàn)澡罚，缺點(diǎn)是每次找最小值都是單純的找，而沒有為下一次尋找做出鋪墊肾请；
C 代碼
//最簡(jiǎn)單的排序, arr表示數(shù)組首地址留搔，count表示數(shù)組的元素個(gè)數(shù)
void simpleSort(int *arr, int count)
{
for (int i = 0; i < count; i++) {
for (int j = i+1; j < count; j++) {
if (arr[i] > arr[j]) {
swap(arr+i, arr+j);
}
}
}
}
Swift 代碼
func simpleSort(_ arr: [Int]) -> [Int] {
var sortArr = arr;
for i in 0..<sortArr.count {
for j in (i+1)..<sortArr.count {
if sortArr[i] > sortArr[j] {
swap(&sortArr[i], &sortArr[j]);
}
}
}
return sortArr;
}
1. 冒泡排序
- 冒泡排序相對(duì)于最簡(jiǎn)單的排序有了改進(jìn)，即每次交換都是對(duì)后續(xù)有幫助的铛铁，大數(shù)將會(huì)越來越大隔显，小的數(shù)將會(huì)越來越小饵逐；
- 思想：兩兩相鄰元素之間的比較括眠，如果前者大于后者，則交換倍权；
C 代碼
//arr表示數(shù)組的首地址掷豺，count表示數(shù)組元素的個(gè)數(shù)
void bubbleSort(int *arr, int count)
{
for (int i = 0; i < count; i++) {
for (int j = 0; j < count - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr+j, arr+j+1);
}
}
}
}
Swift 代碼
func bubbleSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
//循環(huán)按照從后往前的順序確定位置，依次確定最后一個(gè)位置薄声、倒數(shù)第二個(gè)位置...
for i in 0..<sortArray.count {
for j in 0..<(sortArray.count-i-1) {
if sortArray[j] > sortArray[j+1] {
swap(&sortArray[j], &sortArray[j+1]);
}
}
}
return sortArray;
}
改進(jìn)冒泡排序
- 如果出現(xiàn)一個(gè)序列当船，此序列基本是有序的，如果是標(biāo)準(zhǔn)的冒泡排序默辨，則還是需要進(jìn)行不斷的比較德频；
- 改進(jìn)方法：通過填加一個(gè)
boolean類型的變量，如果一次循環(huán)中沒有交換過元素缩幸，則說明已經(jīng)排好序抱婉。
C 代碼
//最好：n-1次比較档叔，不移動(dòng)桌粉。因此時(shí)間復(fù)雜度為O(n)蒸绩，不占用輔助空間。
//最壞：n(n-1)/2次比較和移動(dòng)铃肯，因此為O(n^2)患亿，占用交換的臨時(shí)空間，大小為1押逼；
void bubbleSort1(int *arr, int count)
{
bool isChanged = true;
for (int i = 0; i < count && isChanged; i++) {
isChanged = false;
for (int j = 0; j < count - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr+j, arr+j+1);
isChanged = true;
}
}
}
}
Swift 代碼
//改進(jìn)冒泡排序
//最好：n-1次比較步藕，不移動(dòng)位置。時(shí)間復(fù)雜度為O(n)挑格，不占用輔助空間咙冗。
//最壞：n(n-1)/2次比較和移動(dòng)，因此O(n^2)漂彤，占用交換的臨時(shí)空間雾消，大小為1。
func bubbleSort2(_ arr: [Int]) -> [Int] {
var sortArray = arr;
var isChanged = true;
for i in 0..<sortArray.count {
if !isChanged {
break;
}
isChanged = false;
for j in (i..<sortArray.count-1).reversed() {
if sortArray[j] > sortArray[j+1] {
swap(&sortArray[j], &sortArray[j+1]);
isChanged = true;
}
}
}
return sortArray;
}
2. 簡(jiǎn)單選擇排序
- 特點(diǎn)：每次循環(huán)找到最小值挫望，并交換立润。因此交換次數(shù)始終為n-1次。
- 相對(duì)于最簡(jiǎn)單的排序媳板，對(duì)不必要的交換做了改進(jìn)桑腮，每個(gè)循環(huán)不斷比較后記錄最小值，只做了一次交換蛉幸。（也可能不交換破讨，當(dāng)最小值已經(jīng)在正確的位置）
C 代碼
void selectSort(int *arr, int count)
{
for (int i = 0; i < count; i++) {
int min = i;
for (int j = i+1; j < count; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
swap(arr+i, arr+min);
}
}
}
Swift 代碼
//最差：n(n-1)/2次比較，n-1次交換奕纫，因此時(shí)間復(fù)雜度為O(n^2)
//最好：n(n-1)/2次比較提陶，不交換，因此時(shí)間復(fù)雜度為O(n^2)
//好于冒泡排序
func selectSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
for i in 0..<sortArray.count {
var min = i;
for j in i+1..<sortArray.count {
if sortArray[min] > sortArray[j] {
min = j;
}
}
if min != i {
swap(&sortArray[min], &sortArray[i]);
}
}
return sortArray;
}
3. 簡(jiǎn)單插入排序
- 思想：給定序列若锁，存在一個(gè)分界線搁骑，分界線的左邊被認(rèn)為是有序的，分界線的右邊還沒被排序又固。每次取沒被排序的最左邊一個(gè)和已排序的做比較仲器，并插入到正確位置；我們默認(rèn)索引 0 的子數(shù)組有序仰冠；每次循環(huán)將分界線右邊的一個(gè)元素插入到有序數(shù)組中乏冀，并將分界線向右移一位；
C 代碼
void insertSort(int *arr, int count)
{
int j;
for (int i = 1; i < count; i++) {
int temp = arr[i];
for (j = i; j > 0 && temp < arr[j-1]; j--) {
arr[j] = arr[j-1];
}
//注意要插入的位置
arr[j] = temp;
}
}
Swift 代碼
//最好：n-1次比較洋只，0次移動(dòng)辆沦，時(shí)間復(fù)雜度為O(n)
//最差：n(n-1)/2次比較昼捍，n(n-1)/2次移動(dòng)，時(shí)間復(fù)雜度為O(n^2)
func insertSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
for i in 1..<sortArray.count {
if sortArray[i] < sortArray[i-1] {
let temp = sortArray[i];
var index = i;
for j in (0..<i).reversed() {
if sortArray[j] > temp {
//如果沒找到位置肢扯，繼續(xù)尋找
sortArray[j+1] = sortArray[j];
//記錄位置
index = j;
continue;
}
}
//找到位置, 插入數(shù)值
sortArray[index] = temp;
}
}
return sortArray;
}
4. 希爾排序
- 希爾排序是第一個(gè)突破O(n^2)的排序算法妒茬，是簡(jiǎn)單插入排序的改進(jìn)版；
- 思想：由于簡(jiǎn)單插入排序?qū)τ谟涗涊^少或基本有序時(shí)很有效蔚晨，因此我們可以通過將序列進(jìn)行分組排序乍钻，使得每組容量變小，再進(jìn)行分組排序铭腕，然后進(jìn)行一次簡(jiǎn)單插入排序即可银择；
- 增量的選擇十分重要，可以選擇length/2這樣的方式累舷，也是希爾建議的增量浩考，稱為希爾增量。另外被盈，增量最小為1析孽。
C 代碼
//希爾排序的步長(zhǎng)選擇從length/2開始，每次再減半害捕，直到最后為1绿淋。其實(shí)也可以有另外的更高效的步長(zhǎng)選擇，不過最后需要保證增量為1尝盼。
void shellSort(int *arr, int count)
{
int increment = count;
do {
//設(shè)置希爾初始增量為數(shù)組長(zhǎng)度的一半
increment = increment / 2;
if (increment == 0) {
increment = 1;
}
int j;
for (int i = increment; i < count; i++) {
int temp = arr[i];
//j指向有序區(qū)的最后一個(gè)元素
for (j = i-increment; j >= 0 && temp < arr[j]; j -= increment) {
arr[j+increment] = arr[j];
}
//找到合適的位置吞滞，插入元素
arr[j+increment] = temp;
}
} while (increment > 1);
}
Swift 代碼
//希爾排序的步長(zhǎng)選擇從length/2開始，每次再減半盾沫，直到最后為1裁赠。其實(shí)也可以有另外的更高效的步長(zhǎng)選擇，不過最后需要保證增量為1赴精。
func shellSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
var increment = arr.count;
repeat {
//設(shè)置希爾初始增量為數(shù)組長(zhǎng)度的一半
increment = increment / 2;
if increment == 0 {
increment = 1;
}
for i in increment..<sortArray.count {
let temp = sortArray[i];
//j指向有序區(qū)的最后一個(gè)元素
var j = i - increment;
//循環(huán)找到合適的位置插入元素
while j >= 0 && temp < sortArray[j] {
sortArray[j+increment] = sortArray[j];
j -= increment;
}
sortArray[j+increment] = temp;
}
} while increment > 1;
return sortArray;
}
5. 堆排序
- 大根堆：任意父結(jié)點(diǎn)都比子結(jié)點(diǎn)大佩捞；
小根堆：任意父結(jié)點(diǎn)都比子結(jié)點(diǎn)小蕾哟； - 堆排序是不穩(wěn)定的排序算法箱沦，是簡(jiǎn)單選擇排序的改進(jìn)版峡懈。
- 堆的存儲(chǔ)：一般用數(shù)組來表示堆，若根結(jié)點(diǎn)存在序號(hào) 0 處，i 結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為 (i-1)/2米辐。i 結(jié)點(diǎn)的左颂鸿、右子結(jié)點(diǎn)下標(biāo)分別為 2*i+1 和 2*i+2吗冤。如果根節(jié)點(diǎn)是從 1 開始便贵，則左、右子結(jié)點(diǎn)分別是 2i 和 2i+1昂秃。
- 完全二叉樹有 n 個(gè)結(jié)點(diǎn)禀梳，則擁有 n/2 個(gè)非葉子結(jié)點(diǎn)杜窄。（取整）
- 思想：構(gòu)建一顆完全二叉樹。首先構(gòu)建大根堆算途，然后每次把根節(jié)點(diǎn)（最大值）和最后的節(jié)點(diǎn)（最小值）互換塞耕，然后將數(shù)組長(zhǎng)度減一。之后重新構(gòu)建大根堆郊艘，以此類推荷科。
- 注意：此排序方法不適用于個(gè)數(shù)少的序列，因?yàn)槌跏紭?gòu)建需要時(shí)間纱注。
C 代碼
//堆排序
void heapSort(int *arr, int count)
{
//1.首先構(gòu)建大根堆
for (int i = (count-1)/2; i >= 0; i--) {
heapAdjust(arr, i, count);
}
//2.將根結(jié)點(diǎn)與尾結(jié)點(diǎn)互換，數(shù)組長(zhǎng)度減去1胆胰，重新構(gòu)建大根堆
for (int i = 1; i < count; i++) {
swap(arr, arr+count-i);
heapAdjust(arr, 0, count-i);
}
}
//調(diào)整數(shù)組為大根堆狞贱，parent表示根節(jié)點(diǎn)的下標(biāo)，count表示要調(diào)整的數(shù)組長(zhǎng)度
void heapAdjust(int *arr, int parent, int count)
{
//保存根結(jié)點(diǎn)的數(shù)值
int temp = arr[parent];
//獲取根節(jié)點(diǎn)的左子節(jié)點(diǎn)（下標(biāo)從0開始）
for (int i = parent * 2 + 1; i < count; i = i * 2 + 1) {
//找到左蜀涨、右子結(jié)點(diǎn)的較大者
if (i < count-1 && arr[i] < arr[i+1]) {
i = i + 1;
}
//根結(jié)點(diǎn)大于等于左瞎嬉、右子結(jié)點(diǎn)
if (temp >= arr[i]) {
break;
}
//將根結(jié)點(diǎn)與左、右子結(jié)點(diǎn)較大者替換
arr[parent] = arr[i];
//再次檢查子結(jié)點(diǎn)的子結(jié)點(diǎn)
parent = i;
}
arr[parent] = temp;
}
Swift 代碼
func heapSort(_ arr: [Int]) -> [Int] {
var sortArray = arr;
let count = sortArray.count;
//首先建立大根堆
//先找到最后一個(gè)擁有子結(jié)點(diǎn)的根結(jié)點(diǎn)
var i = count / 2 - 1;
while i >= 0 {
heapAdjust(&sortArray, parent: i, count: count);
i -= 1;
}
//進(jìn)行排序
for i in 1..<count {
//將最后一個(gè)元素和第一個(gè)元素進(jìn)行交換
swap(&sortArray[0], &sortArray[count-i]);
//數(shù)組的長(zhǎng)度減一厚柳，然后將剩下的無序數(shù)組調(diào)整為大根堆
//由于只是頭結(jié)點(diǎn)無序氧枣，所以只需要調(diào)整頭結(jié)點(diǎn)即可，其他結(jié)點(diǎn)不需要調(diào)節(jié)
heapAdjust(&sortArray, parent: 0, count: count-i);
}
return sortArray;
}
//調(diào)整指定結(jié)點(diǎn)以下為大根堆别垮，parent表示父結(jié)點(diǎn)的下標(biāo)便监，count表示要調(diào)整的數(shù)組長(zhǎng)度
func heapAdjust(_ arr: inout [Int], parent: Int, count: Int) {
//保存根結(jié)點(diǎn)的數(shù)值
let temp = arr[parent];
var parent = parent;
//獲取根結(jié)點(diǎn)的左子結(jié)點(diǎn)
var i = parent * 2 + 1;
while i < count {
if i < count-1 && arr[i] < arr[i+1] {
//記錄左右子結(jié)點(diǎn)的較大者
i = i + 1;
}
//如果根節(jié)點(diǎn)數(shù)大于子結(jié)點(diǎn)數(shù)，則中止循環(huán)碳想，否則沿著一路循環(huán)下去
if temp >= arr[i] {
break;
}
//將較大值賦值到根結(jié)點(diǎn)
arr[parent] = arr[i];
//更新當(dāng)前根結(jié)點(diǎn)的位置
parent = i;
//尋找parent的左子結(jié)點(diǎn)進(jìn)行下一輪循環(huán)
i = i * 2 + 1;
}
arr[parent] = temp;
}
6. 歸并排序
- 穩(wěn)定的排序算法
- 思想：利用遞歸進(jìn)行分割和合并烧董，分割直到長(zhǎng)度為1為止，并在合并前保證兩序列原本各自有序胧奔，合并后也有序逊移。
C 代碼
//歸并排序
void mergeSort(int *arr, int count)
{
for (int gap = 1; gap < count; gap = 2 * gap) {
mergePass(arr, gap, count);
}
}
//gap表示字表的長(zhǎng)度，count表示數(shù)組的個(gè)數(shù)
void mergePass(int *arr, int gap, int count)
{
//需要合并的兩個(gè)序列的計(jì)算：
//low = 2 * gap * i;
//mid = low + gap - 1;
//high = low + 2 * gap - 1;
//這里的i就代表low龙填，要合并的第一個(gè)序列的最小下標(biāo)
int i = 0;
for (i = 0; i + 2 * gap - 1 < count; i = i + 2 * gap) {
mergeArray(arr, i, i + gap - 1, i + 2 * gap - 1);
}
//可能有奇數(shù)個(gè)元素胳泉，有則合并剩下的序列
if (i + gap - 1 < count) {
mergeArray(arr, i, i + gap - 1, count - 1);
}
}
//合并數(shù)組元素，low表示第一段序列的最小下標(biāo)岩遗，mid表示第一段序列的最大下標(biāo)扇商，high表示第二段序列的最高下標(biāo)
void mergeArray(int *arr, int low, int mid, int high)
{
int i = low; //第一段序列的下標(biāo)
int j = mid + 1; //第二段序列的下標(biāo)
int k = 0; //k是存放合并序列的下標(biāo)
int *array = (int *)malloc((high - low + 1) * sizeof(int)); //申請(qǐng)臨時(shí)空間
//掃描第一段和第二段序列，直到有一個(gè)掃描結(jié)束
while(i <= mid && j <= high) {
//判斷第一段和第二段取出的數(shù)哪個(gè)更小喘先，將其加入合并序列钳吟，并繼續(xù)向下掃描
if (arr[i] < arr[j]) {
array[k] = arr[i];
i++;
k++;
} else {
array[k] = arr[j];
j++;
k++;
}
}
//若第一段序列還沒掃描完，將其全部復(fù)制到合并序列
while (i <= mid) {
array[k] = arr[i];
i++;
k++;
}
//若第二段序列還沒掃描完窘拯，將其全部復(fù)制到合并序列
while (j <= high) {
array[k] = arr[j];
j++;
k++;
}
//將合并序列復(fù)制到原始序列中
for (k = 0, i = low; i <= high; i++, k++) {
arr[i] = array[k];
}
//釋放空間
free(array);
}
Swift 代碼
//歸并排序
func mergeSort(_ arr: inout [Int]) {
var gap = 1;
while gap < arr.count {
mergePass(&arr, gap: gap);
gap *= 2;
}
}
//分解合并序列
func mergePass(_ arr: inout [Int], gap: Int) {
var i = 0;
let count = arr.count;
while i + 2 * gap - 1 < count {
mergeArray(&arr, low: i, mid: i + gap - 1, high: i + 2 * gap - 1);
i += 2 * gap;
}
//合并剩余的序列
if i + gap - 1 < count {
mergeArray(&arr, low: i, mid: i + gap - 1, high: count - 1);
}
}
//合并兩個(gè)序列
func mergeArray(_ arr: inout [Int], low: Int, mid: Int, high: Int) {
var i = low;
var j = mid + 1;
var k = 0;
var array = Array<Int>(repeating: 0, count: high - low + 1);
while i <= mid && j <= high {
if arr[i] < arr[j] {
array[k] = arr[i];
i += 1;
k += 1;
} else {
array[k] = arr[j];
j += 1;
k += 1;
}
}
while i <= mid {
array[k] = arr[i];
i += 1;
k += 1;
}
while j <= high {
array[k] = arr[j];
j += 1;
k += 1;
}
//將排序好的序列復(fù)制回原數(shù)組
k = 0;
for i in low...high {
arr[i] = array[k];
k += 1;
}
}
7. 快速排序
- 冒泡排序的升級(jí)版红且，現(xiàn)在用的最多的排序方法坝茎；
- 思想：選取pivot，將pivot調(diào)整到一個(gè)合理的位置暇番，使左邊的值都小于它嗤放，右邊的值都大于它；
- 注意壁酬，如果序列基本有序或者序列個(gè)數(shù)較少次酌，則可以采用簡(jiǎn)單插入排序。因?yàn)榭焖倥判驅(qū)@些情況效率不高舆乔。
C 代碼
//快速排序
void quickSort(int *arr, int low, int high)
{
if (low < high) {
int key = partition(arr, low, high);
//對(duì)數(shù)組左邊進(jìn)行排序
quickSort(arr, 0, key-1);
//對(duì)數(shù)組右邊 進(jìn)行排序
quickSort(arr, key+1, high);
}
}
//劃分?jǐn)?shù)組岳服，左邊的數(shù)據(jù)都小于piovt，右邊的數(shù)據(jù)都大于piovt
int partition(int *arr, int low, int high)
{
int piovtKey = arr[low]; //這個(gè)地方可以優(yōu)化
while (low < high) {
//遍歷右邊希俩，直到小于piovtKey
while (low < high && arr[high] >= piovtKey) {
high--;
}
arr[low] = arr[high];
//遍歷左邊吊宋，直到大于piovtKey
while (low < high && arr[low] <= piovtKey) {
low++;
}
arr[high] = arr[low];
}
//將piovtKey賦值到中間位置
arr[low] = piovtKey;
//返回中間位置，low和high都可以颜武，此時(shí)low與high相等
return low;
}
Swift 代碼
//快速排序
func quickSort(_ arr: inout [Int], low: Int, high: Int) {
if low < high {
let p = partition(&arr, low: low, high: high);
//左邊遞歸排序
quickSort(&arr, low: 0, high: p-1);
//右邊遞歸排序
quickSort(&arr, low: p+1, high: high);
}
}
//將數(shù)組分成兩部分璃搜，左邊部分小于pivotKey的值，右邊部分大于pivotKey的值
func partition(_ arr: inout [Int], low: Int, high: Int) -> Int {
var low = low;
var high = high;
let pivotKey = arr[low];
while low < high {
//循環(huán)右邊鳞上，直到小于pivotKey
while low < high && arr[high] >= pivotKey {
high -= 1;
}
arr[low] = arr[high];
//循環(huán)左邊这吻，直到大于pivotKey
while low < high && arr[low] <= pivotKey {
low += 1;
}
arr[high] = arr[low];
}
//將pivotKey放置到中間的位置，返回劃分的位置
arr[low] = pivotKey;
return low;
}
快速排序優(yōu)化方案
- 選取pivot：選取pivot的值對(duì)于快速排序至關(guān)重要篙议，理想情況唾糯，pivot應(yīng)該是序列的中間數(shù)。前面我們只是簡(jiǎn)單的取第一個(gè)數(shù)作為pivot涡上，這點(diǎn)可以進(jìn)行優(yōu)化趾断。
- 優(yōu)化方法：抽多個(gè)數(shù)后取中位數(shù)作為pivot。
- 對(duì)于小數(shù)組使用插入排序：因?yàn)榭焖倥判蜻m合大數(shù)組排序吩愧。如果是小數(shù)組芋酌，則效果沒有簡(jiǎn)單插入排序效果好。
三雁佳、排序總結(jié)
- 數(shù)組長(zhǎng)度不大的情況下不宜使用歸并排序脐帝，其它排序差別不大。
- 數(shù)組長(zhǎng)度很大情況下希爾排序最快糖权，快速排序其次堵腹，冒泡排序最慢。
總結(jié)：每個(gè)排序都有各自的特點(diǎn)星澳，我們需要在適當(dāng)?shù)臅r(shí)候用適當(dāng)?shù)乃惴ň吻辍１热缭?code>基本有序、數(shù)組規(guī)模小的時(shí)候用直接插入排序；比如在大數(shù)組時(shí)用快速排序腿堤；比如想要穩(wěn)定性阀坏，則使用歸并排序；
| 排序方法 | 平均情況 | 最好情況 | 最壞情況 | 輔助空間 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 簡(jiǎn)單選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(n^1.3) | O(n) | O(n^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩(wěn)定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) ~ O(n) | 不穩(wěn)定 |
