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;
        }
    }
    
  • // 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;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions