快速排序、堆排序、归并排序

1.快速排序

快速排序主要是基于分治的思想，每次寻找一个pivot，然后从后往前找比pivot小的，从前往后找比pivot小的。

 public static void quicksort(int[] nums, int low, int high){
        if(low > high)
            return;
        int pivot = nums[low];
        int i = low,j =high;
        while(i<j){
            while(i<j && nums[j]>=pivot){
                j--;
            }
            while (i<j && nums[i]<=pivot){
                i++;
            }
            if(i<j){
                swap(nums, i,j);
            }

        }
        swap(nums, low, i);
        quicksort(nums,low, i-1);
        quicksort(nums,i+1, high);
    }

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

2.堆排序

堆排序主要分三个步骤

堆调整，比较当前元素及其左右孩子，把最大的调整上来（大顶堆）,递归调整。

建堆，根据堆的性质，从nums.length/2-1 最后一个非叶子结点开始从后往前建堆。

排序，从后往前交换堆顶元素和堆最后一个元素，减少堆元素，进行堆的调整。

    public static void adjustHeadp(int[] arrray, int index ,int size){  //堆调整
        int left = 2*index+1;    //下表以0开始
        int right = 2*index+2;
        int largest = index;
        if(left < size && arrray[index]<arrray[left]){
            largest = left;
        }
        if(right < size && arrray[largest]<arrray[right]){
            largest = right;
        }
        if(largest != index){
            swap(arrray, index,largest);
            adjustHeadp(arrray, largest, size);
        }

    }

    public static void buildHeap(int[] arrray){  // 从后往前建堆
        for(int i=arrray.length/2-1;i>=0;i--){
            adjustHeadp(arrray, i, arrray.length);
        }
    }

    public static void sortByHeap(int[] array){   // 排序
        buildHeap(array);
        for(int i=array.length-1;i>=0;i--){
            swap(array, 0, i);
            adjustHeadp(array, 0, i);
        }
    }
  public static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

3.归并排序

归并排序是一种稳定排序，在归并排序中常见的是二路归并，即讲数组分成两份，各自排序再合并的过程，其中二路归并排序是一个递归的过程，即分割使得数组大小为1或者2为止，这样经过一次比较或者不比较就可以得出一个有序的子序列，代码如下。

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

    public static void merge(int[] array, int left, int mid, int right){
        int[] temp = new int[array.length];
        for(int i=0; i<array.length;i++){
            temp[i] = array[i];
        }
        int i = 0,j = 0, k=0;
        for(i=left,j=mid+1,k=left; i<=mid && j<=right; k++){
            if(temp[i]<=temp[j]){
                array[k] = temp[i++];
            }else{
                array[k] = temp[j++];
            }
        }
        while (i<=mid){
            array[k++] = temp[i++];
        }
        while (j<=right){
            array[k++] = temp[j++];
        }
    }