刷题（11）各种排序算法

把各种排序算法实现一遍

1. quick sort:

public void quick_sort(int[] arr, int low, int high) {

        if(low<high){

            int p = partition(arr, low, high);

            quick_sort(arr, low, p - 1);

            quick_sort(arr, p + 1, high);

        }

    }

    private void swap(int[] arr, int value1, int value2) {

        int temp = arr[value1];

        arr[value1] = arr[value2];

        arr[value2] = arrtemp;

    }

    private int partition(int[] arr, int low, int high) {

        int p = low;

        int j = low+1;

        while(j<=high) {

            if(arr[j]<arr[low]){

                swap(arr, ++p, j);

            }

            j++;

        }

        swap(arr, low, p);

        return p;

    }

2. merge sort

public void merge_sort(int[] arr) {

        int n = arr.length;

        if(n<2) {

            return;

        }

        int mid = n/2;

        int[] leftPart = new int[mid];

        int[] rightPart = new int[n-mid];

        for(int i=0;i<mid;i++) {

            leftPart[i] = arr[i];

        }

        for(int i = mid;i<n;i++) {

            rightPart[i - mid] = arr[i];

        }

        merge_sort(leftPart, mid);

        merge_sort(rightPart, mid);

        merge(arr, leftPart, rightPart);

    }

    private void merge(int[] arr, int[] left, int[] right) {

        int a = arr.length, m = left.length, n = right.length;

        int i = 0, j =  0, k =0;

        while(i<m && j< n) {

            if(left[m] < right[n]) {

                a[k++] = left[i++];

            } else {

                a[k++] = right[j++];

            }

        }

        while(i<m) {

            a[k++] = left[i++];

        }

        while(j<n) {

            a[k++] = right[j++];

        }

    }

---还有几种待续