---
tags: data structure and algorithm
---

# 排序演算法
---
## 以比較為基礎的排序演算法
### Insertion Sort
1. 將待排序的資料分為已排序完成與未排序完成兩個子集合。
2. 在排序過程中，由未排序完成的子集合中任取一個元素，插入已排序完成的子集合中。
3. 重複步驟 2 直到未排序完成的子集合成為空集合為止。

在排序小量資料時， insertion sort 是個有效率的排序演算法。
當輸入資料已陣列儲存時， insertion sort 可在原輸入陣列中完成排序。所以， insertion sort 的空間複雜度為 $O(1)$ 。
#### C++ Code

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for (int j = 1; j < nums.size(); ++j) {
            // nums[0..i] is the sorted subarray.
            // nums[j..len-1] is the unsorted subarray.
            int i = j - 1;
            int key = nums[j];
            while (i >= 0 && nums[i] > key) {
                nums[i + 1] = nums[i];
                --i;
            }
            // case 1: i < 0
            // case 2: nums[i] <= key
            
            if (i < 0) {
                // The original subarray, nums[0..i], was sorted and 
                // key is less than nums[0].
                // The original sorted subarray, nums[0..i], has been
                // moved to nums[1..j].
                // nums[0] is the right position for key to make
                // nums[0..j] the new sorted subarray.
                nums[i + 1] = key;
            } else {
                // Now, nums[i] <= key and we have move the original
                // subarray, nums[i+1 .. j-1], to nums[i+1 .. j].
                // nums[i+1] is the right position for key to make
                // the new sorted subarray, nums[0..j]
                nums[i + 1] = key;
            }
        }
        return nums;
    }
};

#### Time Complexity
* Worst Case (輸入資料反向排序)
$O(n^{2})$
$n$ is the length of `nums`.
* Average Case
$O(n^{2})$
* Best Case (輸入資料已排序完成)
$O(n)$
#### Space Complexity
$O(1)$
### Merge Sort
#### C++ Code

class Solution {
public:
    vector<int> sortArray(vector<int> &nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    
private:
    void mergeSort(vector<int> &nums, int left, int right) {
        if (left < right) {
            int middle = left + (right - left) / 2;
            mergeSort(nums, left, middle);
            mergeSort(nums, middle + 1, right);
            merge(nums, left, middle, right);
        }
    }
    
    void merge(vector<int> &nums, int left, int middle, int right) {
        vector<int> numsLeft(middle - left + 1), numsRight(right - middle);
        for (int i = 0; i < numsLeft.size(); ++i) {
            numsLeft[i] = nums[left + i];
        }
        for (int i = 0; i < numsRight.size(); ++i) {
            numsRight[i] = nums[middle + 1 + i];
        }
        numsLeft.push_back(INT_MAX);
        numsRight.push_back(INT_MAX);
        
        int leftIdx = 0, rightIdx = 0;
        for (int i = left; i <= right; ++i) {
            if (numsLeft[leftIdx] < numsRight[rightIdx]) {
                nums[i] = numsLeft[leftIdx++];
            } else {
                nums[i] = numsRight[rightIdx++];
            }
        }
    }
};

#### Time Complexity
$O(nlogn)$
$n$ is the length of `nums`.
#### Space Complexity
$O(n)$
### Quick Sort
#### C++ Code

#### Time Complexity
#### Space Complexity
### Heap Sort
#### C++ Code

class Solution {
public:
    vector<int> sortArray(vector<int> &nums) {
        buildHeap(nums);
        heapSort(nums);
        return nums;
    }
    
private:
    void buildHeap(vector<int> &nums) {
        for (int parentIdx = (nums.size() >> 1) - 1; parentIdx >= 0; --parentIdx) {
            maxHeapify(nums, parentIdx, nums.size());
        }
    }
    
    void maxHeapify(vector<int> &nums, int rootIdx, int len) {
        int maxIdx = rootIdx, leftIdx = (rootIdx << 1) + 1, rightIdx = (rootIdx << 1) + 2;
        
        if (leftIdx < len && nums[maxIdx] < nums[leftIdx]) {
            maxIdx = leftIdx;
        }
        
        if (rightIdx < len && nums[maxIdx] < nums[rightIdx]) {
            maxIdx = rightIdx;
        }
        
        if (maxIdx != rootIdx) {
            swap(nums[maxIdx], nums[rootIdx]);
            maxHeapify(nums, maxIdx, len);
        }
    }
    
    void heapSort(vector<int> &maxHeap) {
        for (int i = maxHeap.size() - 1; i >= 0; --i) {
            swap(maxHeap[0], maxHeap[i]);
            maxHeapify(maxHeap, 0, i);
        }
    }
};

#### Time Complexity
* Best Case:
$O(n)$
$n$ is the length of `num`.
This is the runtime when everything in the input is identical.
* Worst Case:
$O(nlogn)$
$n$ is the length of `num`.
* Average Case:
$O(nlogn)$
$n$ is the length of `num`.
#### Space Complexity
$O(1)$
## 不是以比較為基礎的排序演算法