Quicksort and MergeSort总结

总结下常考的排序算法。

Quick Sort

/**
 * Created by dylan on 10/29/16.
 * Reference: https://www.youtube.com/watch?v=SLauY6PpjW4
 * Time Complicity Average O(nlogn), Worst O(n^2)
 *
 */
public class QuickSort {
    public void quicksort(int[] array) {
        quicksort(array, 0, array.length - 1);
    }

    public void quicksort(int[] array, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        int pivot = array[mid];
        // return dividing point of the partition
        int index = partition(array, left, right, pivot);
        quicksort(array, left, index - 1); // sort left side
        quicksort(array, index, right); // sort right side
    }

    public 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;
    }

    public void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[right] = array[left];
        array[left] = tmp;
    }
}

Merge Sort

/**
 * Created by dylan on 10/29/16.
 *
 * O(n) space
 */
public class MergeSort {

    public void mergesort(int[] array) {
        mergesort(array, 0, array.length - 1, new int[array.length]);
    }

    public void mergesort(int[]array, int leftStart, int rightEnd, int[] tmp) {
        if (leftStart >= rightEnd) return;
        int middle = leftStart + (rightEnd - leftStart) / 2;
        mergesort(array, leftStart, middle, tmp);
        mergesort(array, middle + 1, rightEnd, tmp);
        mergeHalves(array, leftStart, rightEnd, tmp);
    }

    /**
     *
     * @param array
     * @param leftStart
     * @param rightEnd
     * @param tmp
     *
     * void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
     * src -- This is the source array.
     * srcPos -- This is the starting position in the source array.
     * dest -- This is the destination array.
     * destPos -- This is the starting position in the destination data.
     * length -- This is the number of array elements to be copied.
     */

    public void mergeHalves(int[] array, int leftStart, int rightEnd, int[] tmp) {
        int leftEnd = leftStart + (rightEnd - leftStart) / 2;
        int rightStart = leftEnd + 1;
        int size = leftEnd - leftStart + 1;

        int left = leftStart;
        int right = rightStart;
        int index = leftStart;
        // copy over each smaller elements to tmp array
        while(left <= leftEnd && right <= rightEnd) {
            if (array[left] <= array[right]) {
                tmp[index] = array[left];
                left++;
            } else {
                tmp[index] = array[right];
                right++;
            }
            index++;
        }
        System.arraycopy(array, left, tmp, index, leftEnd - left + 1);
        System.arraycopy(array, right, tmp, index, rightEnd - right + 1);
        System.arraycopy(tmp, leftStart, array, leftStart, size);
    }



}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s