排序的基本概念

插入排序

在這個(gè)算法中，除了輸入的數(shù)組本身，沒有使用額外的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)，所有的操作都是在原數(shù)組上進(jìn)行的。因此，無論輸入數(shù)組的大小 n 是多少，算法執(zhí)行過程中所占用的額外空間是固定的，即空間復(fù)雜度為 O (1)。

如果空間復(fù)雜度是 O (n)，通常意味著算法在執(zhí)行過程中會(huì)隨著輸入數(shù)據(jù)規(guī)模 n 的增加而線性地增加額外的存儲(chǔ)空間。例如，如果算法中使用了一個(gè)長度為 n 的輔助數(shù)組，那么其空間復(fù)雜度就是 O (n)。但在這個(gè)插入排序的實(shí)現(xiàn)中，并沒有這種情況。

希爾排序

冒泡排序

快速排序

?

簡(jiǎn)單選擇排序

堆排序

堆的插入刪除

歸并排序

基數(shù)排序