摆动排序-归并排序-归并排序

排序

- 摆动排序

给你一个没有排序的数组，请将原数组就地重新排列满足如下性质:

nums[0] <= nums[1] >= nums[2] <= nums[3]....

答案：

public class Solution {
    /**
     * @param nums a list of integer
     * @return void
     */
    public void wiggleSort(int[] nums) {
        for(int i=1; i<nums.length; i++){
            if ((i%2==1 && nums[i-1]>nums[i])||
            (i%2==0 && nums[i-1]<nums[i]))
                swap(nums, i-1, i);
        }

    }

    /**
     * Swap two values
     * */
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

-归并排序

原理： 给一组整数，按照升序排序。样例: 给出 [3, 2, 1, 4, 5], 排序后的结果为 [1, 2, 3, 4, 5]。

/**
 * Created by kevin on 17-8-21.
 */
public class MergeSort {

    /**
     * Constructive function
     * @param target
     */
    MergeSort(int target[]){
        internalMergeSort(target, 0, target.length-1);
        for (int value :
                target) {
            System.out.println(value);
        }
    }

    /**
     *  Split the dataset and iterator
     * @param target  the target array
     * @param left  left pointer
     * @param right  right pointer
     */
    void internalMergeSort(int target[], int left, int right){
        if (left < right){
            int middle = (left + right)/2;
            System.out.println(left+"-"+middle+"-"+right);
            try {
                internalMergeSort(target, left, middle);
                internalMergeSort(target, middle+1, right);
            }catch (StackOverflowError e){

            }

            merge(target, left, middle, right);
        }
    }

    /**
     * Merge sets
     * @param target the target array
     * @param left  left pointer
     * @param middle the middle
     * @param right  right pointer
     */
    void merge(int target[], int left, int middle, int right){
        int l =left;
        int m = middle+1;  // Notice the m need to start from middle+1
        int result[] = new int[right-left+1];
        int k = 0;

        while(l<=middle && m <= right){
            if (target[l]>target[m])
                result[k++] = target[m++];
            else
                result[k++]= target[l++];
        }

        while(l<=middle){
            result[k++] = target[l++];
        }

        while (m <= right){
            result[k++] = target[m++];
        }

        for (int i=left; i<=right;i++){  // Notice the i need be iterated from left to right
            target[i] = result[i-left];
        }
    }

    /**
     * main
     * @param args
     */
    public static void  main (String args[]){
        int target[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
        for (int value :
                target) {
            System.out.println(value);
        }
        new MergeSort(target);
    }
}

-快速排序

/**
 * Created by kevin on 17-8-22.
 */
public class QuickSort {

    public QuickSort(int[] targetArr) {
        recursionMethod(targetArr, 0, targetArr.length - 1);
        for (int r : targetArr) {
            System.out.println(r);
        }
    }

    void recursionMethod(int[] partArr, int start, int end) {
        if (start >= end) return;
        int pivot = (start + end) / 2;
        int pivotValue = partArr[pivot];
        int lefP = start;
        int rigP = end;
        // left pointer move to right, and right pointer move to left.
        // left pointer stopped moving when encounter a number larger than or equal with pivot.
        // right pointer stopped moving when encounter a number smaller than pivot.
        while (lefP <= rigP) {
            // moving left pointer
            while (lefP <= rigP && partArr[lefP] < pivotValue)
                lefP++;
            while (lefP <= rigP && partArr[rigP] > pivotValue)
                rigP--;
            // Now, lefP point at a bigger value, and rigP point at a littler value.

            if (lefP <= rigP) {
                // Then swap these two values.
                swapValues(partArr, lefP, rigP);
                // move pointer
                lefP++;
                rigP--;
            }
        }

        recursionMethod(partArr, start, rigP);
        recursionMethod(partArr, lefP, end);

    }

    void swapValues(int[] partArr, int left, int right) {
        // swap the left larger value and the right smaller value.
        int temp = partArr[left];
        partArr[left] = partArr[right];
        partArr[right] = temp;
    }

    public static void main(String args[]) {
        int target[] = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50, 4, 6, 77, 8, 32, 2, 1, 754, 7347, 2352, 656, 75467, 2534, 6436, 2342, 73, 25, 253, 654, 2542,
                34252, 6453, 345, 736, 5623, 2345234, 25, 34534, 456, 7456, 776, 567, 4564, 34, 345, 456, 345, 2, 745, 453, 7643625, 25};
        try {
            new QuickSort(target);
        } catch (StackOverflowError e) {

        }
    }
}