原地排序

原地排序就是指在排序過程中不申請多餘的存儲空間，只利用原來存儲待排數據的存儲空間進行比較和交換的數據排序。

基本介紹

• 中文名：原地排序
• 外文名：sort in place
• 性質：排序
• 屬性：原地
• 不申請多餘的：空間來進行的排序

原地排序

原地排序就是指不申請多餘的空間來進行的排序，就是在原來的排序數據中比較和交換的排序。例如堆排序等都是原地排序，合併排序（根據TAOCP，合併排序也有原地排序的版本），計數排序等不是原地排序。

屬於原地排序的是：希爾排序、冒泡排序、插入排序、選擇排序、堆排序、快速排序。

排序

希爾排序

希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell於1959年提出而得名。

冒泡排序

冒泡排序，是指計算機的一種排序方法，它的時間複雜度為O（n^2），雖然不及堆排序、快速排序的O（nlogn，底數為2），但是有兩個優點：1.“編程複雜度”很低，很容易寫出代碼；2.具有穩定性，這裡的穩定性是指原序列中相同元素的相對順序仍然保持到排序後的序列，而堆排序、快速排序均不具有穩定性。不過，一路、二路歸併排序、不平衡二叉樹排序的速度均比冒泡排序快，且具有穩定性，但速度不及堆排序、快速排序。冒泡排序是經過n-1趟子排序完成的，第i趟子排序從第1個數至第n-i個數，若第i個數比後一個數大（則升序，小則降序）則交換兩數

插入排序

有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入後此數據序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據，算法適用於少量數據的排序，時間複雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外，而第二部分就只包含這一個元素。在第一部分排序後，再把這個最後元素插入到此刻已是有序的第一部分里的位置

選擇排序

每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

堆排序

堆積排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序算法，可以利用數組的特點快速定位指定索引的元素。