排序算法

 * Created by Jaye on 16/9/26.
 */
public class  {
    public int partition(int[] nums, int left, int right){
        int pivot = nums[right];

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

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

    public void quickSort(int[] nums, int left, int right){
        if(left < right) {
            int index = partition(nums, left, right);
            quickSort(nums, left, index - 1);
            quickSort(nums, index + 1, right);
        }
    }

    public static void main(String[] args){
        int[] nums = {9,8,7,6,5,4,3,2,1};
        //int[] nums = {1,2,3,4,5,6};

        new QuickSort().quickSort(nums,0, nums.length - 1);

        for(int num: nums){
            System.out.println(num + " ");
        }
    }
}

 * Created by Jaye on 16/9/26.
 */
public class HeapSort {
    private int[] heap;
    private int heapsize;


    public void maxHeapify(int i){
        int l = left(i);
        int r = right(i);
        int largest = i;

        if(l < heapsize && heap[l] > heap[largest])
            largest = l;
        if(r < heapsize && heap[r] > heap[largest])
            largest = r;

        if(largest != i){
            int temp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = temp;
            maxHeapify(largest);
        }
    }

    public void buildMaxHeap(int[] nums){
        this.heap = nums;
        this.heapsize = heap.length;

        for (int i = heapsize / 2 - 1; i >= 0; i--) {
            maxHeapify(i);
        }
    }

    public void heapSort(int[] nums){
        buildMaxHeap(nums);

        for (int i = heap.length - 1; i > 0; i--) {
            int temp = heap[i];
            heap[i] = heap[0];
            heap[0] = temp;

            heapsize--;
            maxHeapify(0);
        }
    }


    private int parent(int i){
        return (i - 1) / 2;
    }

    private int left(int i){
        return 2*i + 1;
    }

    private int right(int i){
        return 2*i + 2;
    }

    public static void main(String[] args){
        int[] nums = {6,5,4,3,2,1};
        HeapSort hs =new HeapSort();
        hs.heapSort(nums);

        nums = hs.heap;

        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i] + " ");
        }

    }
}

 * Created by Jaye on 16/9/26.
 */
public class MergeSort {

    public static void mergeSort(int[] nums, int left, int right){
        if(left < right){
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid+1, right);
            merge(nums, left, mid, right);
        }
    }

    public static void merge(int[] nums, int left, int middle, int right){
        int[] temp = new int[nums.length];
        int r = middle + 1;
        int l = left;

        int index = left;
        while (l <= middle && r <= right){
            if(nums[l] <= nums[r]){
                temp[index++] = nums[l++];
            }else {
                temp[index++] = nums[r++];
            }
        }

        while (l <= middle){
            temp[index++] = nums[l++];
        }

        while (r <= right){
            temp[index++] = nums[r++];
        }

        int i = left;
        while (i <= right){
            nums[i] = temp[i++];
        }
    }

    public static void main(String[] args){
        int[] nums = {6,5,4,3,2,1};
        MergeSort.mergeSort(nums, 0, nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i] + " ");
        }
    }
}

 * Created by Jaye on 16/9/26.
 */
public class BubbleSort {
    public static void bubbleSort(int[] nums){
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if(nums[i] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }

    public static void main(String[] args){
        int[] nums = {6,5,4,3,2,1};
        BubbleSort.bubbleSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i] + " ");
        }

    }
}