Formatted question description: https://leetcode.ca/all/912.html

912. Sort an Array (Medium)

Given an array of integers nums, sort the array in ascending order.

 

Example 1:

Input: [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

 

Note:

  1. 1 <= A.length <= 10000
  2. -50000 <= A[i] <= 50000

Solution 1. STL

// OJ: https://leetcode.com/problems/sort-an-array/

// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums;
    }
};

Solution 2. Quick Sort

// OJ: https://leetcode.com/problems/sort-an-array/

// Time: O(NlogN) on average
// Space: O(1)
class Solution {
private:
    int partition(vector<int> &nums, int L, int R, int pivot) {
        swap(nums[pivot], nums[R]);
        for (int i = L; i < R; ++i) {
            if (nums[i] >= nums[R]) continue;
            swap(nums[i], nums[L++]);
        }
        swap(nums[L], nums[R]);
        return L;
    }
    void quickSort(vector<int> &nums, int L, int R) {
        if (L >= R) return;
        int M = partition(nums, L, R, rand() % (R - L + 1) + L);
        quickSort(nums, L, M - 1);
        quickSort(nums, M + 1, R);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand (time(NULL));
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

Solution 3. Merge Sort

// OJ: https://leetcode.com/problems/sort-an-array/

// Time: O(NlogN)
// Space: O(N)
class Solution {
private:
    vector<int> tmp;
    void mergeSort(vector<int> &nums, int start, int end) {
        if (start + 1 >= end) return;
        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid, end);
        for (int i = start, j = mid, k = 0; i < mid || j < end; ++k) {
            tmp[k] = (i >= mid || (j < end && nums[j] < nums[i])) ? nums[j++] : nums[i++];
        }
        for (int i = start; i < end; ++i) nums[i] = tmp[i - start];
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp = vector<int>(nums.size());
        mergeSort(nums, 0, nums.size());
        return nums;
    }
};

Solution 4. Heap Sort

// OJ: https://leetcode.com/problems/sort-an-array/

// Time: O(NlogN)
// Space: O(1)
class Solution {
private:
    void heapify(vector<int> &nums) {
        for (int i = nums.size() / 2 - 1; i >= 0; --i)
            siftDown(nums, i, nums.size());
    }
    void siftDown(vector<int> &nums, int hole, int end) {
        int next = 2 * hole + 1;
        while (next < end) {
            if (next + 1 < end && nums[next + 1] > nums[next]) ++next;
            if (nums[hole] > nums[next]) break;
            swap(nums[hole], nums[next]);
            hole = next;
            next = 2 * next + 1;
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        heapify(nums);
        for (int i = nums.size() - 1; i > 0; --i) {
            swap(nums[0], nums[i]);
            siftDown(nums, 0, i);
        }
        return nums;
    }
};

Java

class Solution {
    public List<Integer> sortArray(int[] nums) {
        return mergeSort(nums);
    }

    public List<Integer> mergeSort(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            List<Integer> list = new ArrayList<Integer>();
            list.add(nums[0]);
            return list;
        } else {
            int halfLength = length / 2;
            int[] nums1 = new int[halfLength];
            int[] nums2 = new int[length - halfLength];
            for (int i = 0; i < halfLength; i++)
                nums1[i] = nums[i];
            for (int i = halfLength; i < length; i++)
                nums2[i - halfLength] = nums[i];
            List<Integer> list1 = mergeSort(nums1);
            List<Integer> list2 = mergeSort(nums2);
            return merge(list1, list2);
        }
    }

    public List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        List<Integer> mergedList = new ArrayList<Integer>();
        int size1 = list1.size(), size2 = list2.size();
        int index1 = 0, index2 = 0;
        while (index1 < size1 && index2 < size2) {
            int num1 = list1.get(index1), num2 = list2.get(index2);
            if (num1 <= num2) {
                mergedList.add(num1);
                index1++;
            } else {
                mergedList.add(num2);
                index2++;
            }
        }
        while (index1 < size1) {
            mergedList.add(list1.get(index1));
            index1++;
        }
        while (index2 < size2) {
            mergedList.add(list2.get(index2));
            index2++;
        }
        return mergedList;
    }
}

All Problems

All Solutions