---
# System prepended metadata

title: 912. Sort an Array
tags: [LeetCode]

---

<style>
    /* 頁面整體設定 */
    html, body, .ui-content {
    background: #2C2C2C;
    color: #00FFD5;
}
    /* tag顏色設定 */
.markdown-body h6 {
    font-size: .85em;
    color: #A5FFE5;
    -webkit-animation: discolor 5s linear infinite,
                      glint 2s ease infinite;
          animation: discolor 5s linear infinite,
                      glint 2s ease infinite;
    /*animation: discolor 5s linear infinite,
               glint 2s ease infinite;*/
}   
    /* 設定右上角留言按鈕 */
#comment-app .open-comments {
    background: transparent;
}
.btn-default {
  background: transparent;
  border-color: #A5FFE599;
    -webkit-animation: discolor 5s linear infinite,
                      glint 2s ease infinite;
          animation: discolor 5s linear infinite,
                      glint 2s ease infinite;
}
.btn-default:hover {
  background: transparent;
}
.ui-comment-app .open-comments .btn.ui-open-comments {
  color: #A5FFE599;
}
.ui-comment-app .open-comments .btn.ui-open-comments:hover {
  color: #A5FFE5;
}
    /* 設置愛心、收藏、小鈴鐺按鈕 */
.community-button {
  color: #A5FFE580;
    -webkit-animation: discolor 5s linear infinite,
                      glint 2s ease infinite;
          animation: discolor 5s linear infinite,
                      glint 2s ease infinite;
}
.community-button:hover {
  color: #A5FFE5;
  background: transparent;
}
    /* 設定 code 模板 */
    .markdown-body code,
.markdown-body tt {
    background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
    color: #ddd;
    background-color: #00000080;
}
.hljs-tag {
    color: #ddd;
}
.token.operator {
  background-color: transparent;
}
    /* h1, h2 樣式 */
.markdown-body h1,
.markdown-body h2 {
    border-bottom-color: #ffffff80;
    text-shadow: 3px 3px 3px #009B67;
}

    /* 設定小目錄的背景顏色 */
.ui-toc-dropdown {
    background-color: #2C2C2C;
}
    /* 設定行動裝置中，小目錄按鈕 */
.ui-toc-label.btn {
    background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
    color: #ffffff90;
}
.ui-toc-label.btn:hover {
    background: linear-gradient(180deg, #2BE8CF90 0%, #2B83E890 100%);
    color: #ffffff;
}
    /* 設定小目錄內連結 */
.ui-toc-dropdown .nav>li>a,
.toc-menu>a {
    color: #D4F9FF;
    font-weight: bold;
}
.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
    color: #00FFD5;
    border-left: 1px solid #00FFD5;
}

.ui-toc-dropdown .nav>.active:focus>a,
.ui-toc-dropdown .nav>.active:hover>a,
.ui-toc-dropdown .nav>.active>a {
    color: #00FFD5;
    border-left: 1px solid #00FFD5;
/*     -webkit-animation: discolor 5s linear infinite,
                        glint 2s ease infinite;
            animation: discolor 5s linear infinite,
                        glint 2s ease infinite; */
}

.toc-menu>a:focus,
.toc-menu>a:hover {
    color: #00FFD5;
}
    /* 回到最上面的按鈕 */
.markdown-body a > .fa-chevron-up {
    position: fixed;
    bottom: 20px;
    right: 20px;
    padding: 4px;
    border-radius: 4px;
    color: #fff;
    background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
}
.markdown-body a:hover > .fa {
    background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
    -webkit-animation: discolor 5s linear infinite,
                        glint 2s ease infinite;
            animation: discolor 5s linear infinite,
                        glint 2s ease infinite;
}
    /* 右邊滾動軸 */
::-webkit-scrollbar {
    width: 10px;
}
::-webkit-scrollbar-track {
    background: transparent;
}
::-webkit-scrollbar-thumb {
    background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
    border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
    background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
    /* 設定連結 */
a,
.open-files-container li.selected a {
    color: #89FFF8;
    
}
a:hover,
.open-files-container li.selected a:hover {
    color: #89FFF8;
}
    /* 上面的名字顏色修改 */
.text-gray-900 {
    --tw-text-opacity: 1;
    color: #95FFFF;
    animation: discolor 5s linear infinite,
               glint 2s ease infinite;
}

/* 下面的名字顏色修改 */
/* 這個會修改到最下面的HackMD 但不會閃爍*/   
.footer a {
    color: #95FFFF;
}
.text-black-brand {
    --tw-text-opacity: 1;
    animation: discolor 5s linear infinite,
               glint 2s ease infinite;
}
/* 動畫 */
@keyframes discolor {
    0%, 100% {filter: hue-rotate(0);}
    50% {filter: hue-rotate(180deg);}
}
</style>

###### tags: `LeetCode`
# 912. Sort an Array

## 題目
將陣列中數字排序，且時間複雜度在O(nlog(n))以下。


<a href = "https://leetcode.com/problems/sort-an-array/description/"><i class="	fa fa-bug"></i> 題目連結</a>

## 程式碼
merge sort
```cpp=
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums);
        return nums;
    }
private:
    void mergeSort(vector<int>& nums){
        if(nums.size() == 1)
            return;
        vector<int> left, right;
        const int n = nums.size();
        for(int i = 0;i < n / 2;i ++)    //分一半
            left.push_back(nums[i]);
        for(int i = n / 2;i < n;i ++)
            right.push_back(nums[i]);
        mergeSort(left);
        mergeSort(right);
        merge(nums, left, right);    //合併並排序
    }
    void merge(vector<int>& nums, vector<int>& left, vector<int>& right){
        const int l = left.size(), r = right.size(), n = nums.size();
        for(int i = 0, j = 0, now = 0;now < n;now ++){
            if(i == l)
                nums[now] = right[j ++];
            else if(j == r)
                nums[now] = left[i ++];
            else if(left[i] < right[j])
                nums[now] = left[i ++];
            else
                nums[now] = right[j ++];
        }
    }
};
```

counting sort
```cpp=
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        countingSort(nums);
        return nums;
    }
private:
    void countingSort(vector<int>& nums) {
        map<int, int> counting;
        for(int n : nums)
            counting[n] ++;
        int now = 0;
        for(auto m : counting)
            for(int i = 0;i < m.second;i ++)
                nums[now ++] = m.first;
    }
};
```
## DATE

2023/03/01