排序的基本概念

插入排序

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

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

希爾排序

冒泡排序

快速排序

?

簡單選擇排序

堆排序

堆的插入刪除

歸并排序

基數(shù)排序