Sorting Topics

Selection Sort(stable):

解题思路：
Loop the array and put the smallest for each inner loop.也就是每次选择后面的最小的元素放到前面。

代码：

public class SelectionSort {

    /*    time : O(n^2)    space: O(1)    * */
    public void selectionSort(int[] nums){
        if(nums == null || nums.length <= 1){
            return;
        }
        for(int i = 0; i <= nums.length - 2; i++){
            int j = i + 1;
            int min = i;
            for( ; j <= nums.length - 1; j++){
                if(nums[j] < nums[min]){
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }

    private void swap(int[] nums, int i, int min) {
        int temp = nums[i];
        nums[i] = nums[min];
        nums[min] = temp;
    }

    public static void main(String[] args){
        SelectionSort selectionSort = new SelectionSort();
        int[] nums = {64, 5, 79, 21, 1, 32, 4};
        selectionSort.selectionSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}

Insertion sort(stable):

suitable for array that is almost sorted.
解题思路：
每次把subarray最后的元素插到subarray相应的位置上。

代码：

public class InsertionSort {

    public void insertionSort(int[] nums){
        if(nums == null || nums.length <= 1){
            return;
        }
        for(int i = 1; i <= nums.length - 1; i++){
            int j = i - 1;
            while(j >= 0 && nums[j] > nums[j + 1]){
                swap(nums, j, j + 1);
                j--;
            }
        }
    }

    private void swap(int[] nums, int i, int min) {
        int temp = nums[i];
        nums[i] = nums[min];
        nums[min] = temp;
    }

    public static void main(String[] args){
        InsertionSort insertionSort = new InsertionSort();
        int[] nums = {64, 5, 79, 21, 1, 32, 4};
        insertionSort.insertionSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}

Quick Sort:

解题思路：
每次选取一个基准点，并且partition好，然后进行recursion。
时间复杂度和空间复杂度都是O(nlg(n))。

代码：

public class QuickSort {

    public void quickSort(int[] nums){
        if(nums == null || nums.length <= 1){
            return;
        }
        sort(nums, 0, nums.length - 1);
    }

    private void sort(int[] nums, int left, int right) {
        if(left >= right){
            return;
        }
        int pivot = partition(nums, left, right);
        sort(nums, left, pivot - 1);
        sort(nums, pivot + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        int i = left - 1;
        for(int j = left; j <= right - 1; j++){
            if(nums[j] <= nums[right]){
                i++;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, right);
        return i + 1;
    }

    private void swap(int[] nums, int i, int min) {
        int temp = nums[i];
        nums[i] = nums[min];
        nums[min] = temp;
    }

    public static void main(String[] args){
        QuickSort quickSort = new QuickSort();
        int[] nums = {64, 5, 79, 21, 1, 32, 4};
        quickSort.quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}

Merge Sort:

解题思路：
这里用的也是一种分治的思想，先解决小的问题，然后合并起来。

代码：

public class MergeSort {

    public void mergeSort(int[] nums){
        if(nums == null || nums.length <= 1){
            return;
        }
        internalSort(nums, 0, nums.length - 1);
    }

    private void internalSort(int[] nums, int left, int right) {
        if(left >= right){
            return;
        }
        int middle = left + (right - left) / 2;
        internalSort(nums, left, middle);
        internalSort(nums, middle + 1, right);
        merge(nums, left, middle, middle + 1, right);
    }

    private void merge(int[] nums, int left_left, int left_right, int right_left, int right_right) {
        int[] temp = new int[nums.length];
        int i = left_left;
        int j = right_left;
        int index = left_left;
        while(i <= left_right && j <= right_right){
            if(nums[i] <= nums[j]){
                temp[index++] = nums[i++];
            }
            else{
                temp[index++] = nums[j++];
            }
        }
        while(i <= left_right){
            temp[index++] = nums[i++];
        }
        while(j <= right_right){
            temp[index++] = nums[j++];
        }
        index = left_left;
        while(index <= right_right){
            nums[index] = temp[index];
            index++;
        }
    }

    public static void main(String[] args){
        MergeSort mergeSort = new MergeSort();
        int[] nums = {64, 5, 79, 21, 1, 32, 4};
        mergeSort.mergeSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}