Leetcode Sort

[zxw018018]

Sort

Quick Sort

    private void quicksort(int[] array) {
        quicksort(array, 0, array.length - 1);
    }
    
    private void quicksort(int[] array, int left, int right) {
        if (left < right) {
            int pivot = array[(left + right) / 2];
            int index = partition(array, left, right, pivot);
            quicksort(array, left, index - 1);
            quicksort(array, index, right);
        }
    }
    
    private int partition(int[] array, int left, int right, int pivot) {
        while (left <= right) {
            while (array[left] < pivot) {
                left++;
            }
            while (array[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(array, left, right);
                left++;
                right--;
            }
        }
        return left;
    }
    
    private void swap(int[] array, int left, int right) {
        int tmp = array[right];
        array[right] = array[left];
        array[left] = tmp;
    }

Problems

21. Merge Two Sorted Lists

Description

• Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Analysis

• Create a new linked list link them together.

23. Merge k Sorted Lists

Description

• Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Analysis

• Use merge two sorted list function.

41. First Missing Positive

Description

• Given an unsorted integer array, find the smallest missing positive integer.

Analysis

• Use bucket sort.

75. Sort Colors

Description

• Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
• Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Analysis

• Set red and blue index and do swap during iteration.

88. Merge Sorted Array

Description

• Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Analysis

• Iterate from the end of nums1

147. Insertion Sort List

Description

Analysis

• Linked list

148. Sort List

Description

• Sort a linked list in O(n log n) time using constant space complexity.

Analysis

• Find middle and split the list into two and sort and merge them.

164. Maximum Gap

Description

• Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
• Return 0 if the array contains less than 2 elements.

Analysis

• Use radix sort.

179. Largest Number

Description

• Given a list of non negative integers, arrange them such that they form the largest number.

Analysis

• Convert to string first then sort.

215. Kth Largest Element in an Array

Description

• Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Analysis

• Use quicksort.

274. H-Index

Description

• Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

Analysis

• Use count sort.