912. Sort an Array.md

// quickSort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    
    void quickSort (vector<int>& nums, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = nums[lo], i = lo + 1, j = hi;
        while (i <= j) {
            if (nums[i] > pivot && nums[j] < pivot) {
                std::swap(nums[i++], nums[j--]);
            }
            if (nums[i] <= pivot) ++i;
            if (nums[j] >= pivot) --j;
        }
        std::swap(nums[lo], nums[j]);
        quickSort(nums, lo, j - 1);
        quickSort(nums, j + 1, hi);
    }
};

// bubble sort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for (int i = nums.size() - 1; i >= 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums[j], nums[j + 1]);
                }
            }
        }
        return nums;
    }
};

// selection sort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            int min = i;
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[j] < nums[min]) min = j;
            }
            swap(nums[min], nums[i]);
        }
        return nums;
    }
};

// heap sort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = n / 2 - 1; i >= 0; --i) {
            heapify(nums, n, i);
        }
        for (int i = n - 1; i >= 0; --i) {
            swap(nums[i], nums[0]);
            heapify(nums, i, 0);
        }
        return nums;
    }
    
    void heapify(vector<int>& nums, int n, int i) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int largest = i;
        if (left < n && nums[left] > nums[la	rgest]) {
            largest = left;
        }
        if (right < n && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(nums[largest], nums[i]);
            heapify(nums, n, largest);
        }
    }
};

// insertion sort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            int num = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > num) {
                nums[j + 1] = nums[j--];
            }
            nums[j + 1] = num;
        }
        return nums;
    }
};

// merge sort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    
    void merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> arr(right - left + 1);
        int i = left, j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] < nums[j]) {
                arr[k++] = nums[i++];
            } else {
                arr[k++] = nums[j++];
            }
        }
        while (i <= mid) arr[k++] = nums[i++];
        while (j <= right) arr[k++] = nums[j++];
        for (int i = 0; i < arr.size(); ++i) {
            nums[left + i] = arr[i];
        }
    }
};