排序算法

1.快速排序

2.堆排序

1.原理：利用完全二叉树特性（第n个元素的孩子节点分别是2n+1,2n+2） ，实质上仍然还是一个数组，无需建树

my堆排序

package com.pengbo.mydemo.常用算法.sort;
import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr=new int[]{3, 1, 5, 7, 2, 4, 9, 6};
        System.out.println("begin: "+Arrays.toString(arr));
        new HeapSort().heapsort(arr);
        System.out.println("end: "+Arrays.toString(arr));
    }
    private void heapsort(int[] arr) {
        // 初始建堆： 从 最后一个拥有叶子节点的元素 向前遍历建堆，从右到左，从下到上
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length - 1);
            System.out.println("i="+i+","+ Arrays.toString(arr));
        }
        // 交换首尾元素，重新从根节点开始调整
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);
            adjustHeap(arr, 0, j - 1);
        }
    }
    /**
     * 调整堆
     * @param arr   
     * @param begin 开始坐标
     * @param end   结束坐标
     */
    private void adjustHeap(int[] arr, int begin, int end) {
        // 从上到下依次调整堆，以数组[begin...end]的元素作为堆
        // 如果flag不是最后一个非叶子节点 2*begin+1<end
        while (2 * begin + 1 <= end) {
            int leftChildIndex = 2 * begin + 1;
            int rightChildIndex = 2 * begin + 2;
            int maxChildIndex = rightChildIndex > end || arr[leftChildIndex] >= arr[rightChildIndex]
                    ? leftChildIndex
                    : rightChildIndex;
            if (arr[begin] >= arr[maxChildIndex]) {
                break;
            } else {
                swap(arr, begin, maxChildIndex);
                begin = maxChildIndex;
            }
        }
    }
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

other堆排序

package sortdemo;

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/17.
 * 堆排序demo
 */
public class HeapSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

3.归并排序

化整为1，分段合并

https://www.cnblogs.com/chengxiao/p/6194356.html

package sortdemo;

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/8.
 */
public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}