排序

排序

排序这东西可太重要了，去年学数据结构就晓得有那么多排序了，现在好像连冒泡和选择都还没彻底搞明白。

这篇文章的主要内容：

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 归并排序
• 快速排序
• 堆排序

还有一些排序，比如基数排序和桶排序，代码还没写过，感觉好像挺恶心的，先不管了。

冒泡排序

冒泡排序的英语名是Bubble Sort，是一种最基础的交换排序。

说白了，就是两层循环，外面一层从0到len-1，里面一层从0到 len-i-1，内层for里面进行j与j+1的比较。

这样内层for循环结束之后，最大的值就会冒泡到最右边，以此类推……

public static void sort(int[] arr){
    for (int i = 0; i < arr.length-1; i++) {
        for (int j = 0; j < arr.length-1-i; j++) {
            if(arr[j]>arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

冒泡优化：冒泡有一个最大的问题就是这种算法不管不管你有序还是没序，闭着眼睛把你循环比较了再说。有时候本来就是一个有序的或者冒泡几次就已经有序了，没必要在进行循环了。针对这个问题，我们可以设定一个临时遍历来标记该数组是否已经有序，如果有序了就不用遍历了。

//冒泡优化
public static void sortImprove(int[] arr){
    for (int i = 0; i < arr.length-1; i++) {
        boolean isSorted = true;
        for (int j = 0; j < arr.length-1-i; j++) {
            if(arr[j]>arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                isSorted = false;
            }
        }
        if(isSorted)
            break;
    }
}

选择排序

首先，找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置，第二步，在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置，如此循环，直到整个数组排序完成。

public static void sort(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        int min = i;
        for (int j = i+1; j < arr.length; j++) {
            if(arr[j]<arr[min])
                min = j;
        }
        int temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

插入排序

插入排序的思想和我们打扑克摸牌的时候一样，从牌堆里一张一张摸起来的牌都是乱序的，我们会把摸起来的牌插入到左手中合适的位置，让左手中的牌时刻保持一个有序的状态。

public static void sort(int[] arr){
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j;
        for (j = i-1; j >= 0; j--) {
            if(arr[j]>temp){
                arr[j+1] = arr[j];
            }else {
                break;
            }
        }
        arr[j+1] = temp;
    }
}

希尔排序

插入排序在小规模数据或者基本有序时十分高效，怎么对插入排序进行改进，是的它对较大规模并且无序的数据也非常有效率，希尔排序就可以实现它。

• 首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高。

• 每个分组进行插入排序后，各个分组就变成了有序的了（整体不一定有序）

• 然后缩小增量为上个增量的一半；继续划分分组，此时，每个分组元素个数多了，但是，数组变的部分有序了，插入排序效率同样比高

• 同理对每个分组进行排序（插入排序），使其每个分组各自有序

• 依次类推，则整个数组被分为一组，此时，整个数组已经接近有序了，插入排序效率高，对这仅有的一组数据进行排序，排序完成

public static void sort(int[] arr){
    int len = arr.length;
    int gap = len/2;//间隔从长度的一半开始
    while (gap>0){
        //前面gap个其实就是每个数组的第一位，然后每个数组从后面进行插入排序
        for (int i = gap; i < len; i++) {
            //这里面其实就是插入排序
            int temp = arr[i];
            int j = i-gap;
            while (j>=0 && temp<arr[j]){
                arr[j+gap] = arr[j];
                j-=gap;
            }
            arr[j+gap] = temp;
        }
        gap/=2;
    }
}

归并排序

归并字面上的意思是合并，归并算法的核心思想是分治法，就是将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{5,1,6,3,7,2,4,8};
        int[] tempArr = new int[arr.length];
        sort(arr,tempArr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    //归并排序
    public static void sort(int[] arr,int[] tempArr,int start,int end){
        if(start>=end)//先判断
            return;
        //使用分治递归
        int middle = start + (end-start)/2;
        sort(arr,tempArr,start,middle);
        sort(arr,tempArr,middle+1,end);
        merge(arr,tempArr,start,middle,end);
    }
    //把两个有序数组合并
    public static void merge(int[] arr,int[] tempArr,int start,int middle,int end){
        for (int i = start; i <= end; i++)
            tempArr[i] = arr[i];
        int k = start;
        int left = start;//左边首位下标
        int right = middle+1;//右边首位下标
        //合并两个有序数组
        while (left<=middle && right<=end){
            arr[k++] = tempArr[left]<tempArr[right] ? tempArr[left++] : tempArr[right++];
        }
        while (left<=middle)
            arr[k++] = tempArr[left++];
        while (right<=end)
            arr[k++] = tempArr[right++];
    }
}

快速排序

快速排序的核心思想也是分治法，分而治之。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边，然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。

是冒泡排序的升级，和冒泡排序一样，都属于交换排序的一种。

public class No6QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{5,6,1,2,8,7,4,3};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left,int right){
        if(left >= right)
            return;
        //切分然后递归
        int pivotIndex = partition(arr,left,right);
        quickSort(arr,left,pivotIndex-1);
        quickSort(arr,pivotIndex+1,right);
    }
}

partition 交换方法有两种，一种是单边循环法，一种是双边循环法。

/**单边循环法
 * 思想就是先定义一个基准值为；left，然后遍历，遇到比pivot小的：mark加1，交换arr【i】与arr【mark】
 * 这样遍历完成之后，mark以及mark之前的值全部都是比pivot小的，mark之后的值全部都是比pivot大的
 * 最后还要交换arr【left】与arr【mark】
 */
public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];//取基准值
    int mark = left;//mark初始化为其实下标
    //要把pivot前全是比它小的，pivot之后全是比它大的
    for (int i = left+1; i <= right; i++) {
        if(arr[i]<pivot){
            mark++;
            int temp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = temp;
        }
    }
    //交换arr【left】与arr【mark】
    arr[left] = arr[mark];
    arr[mark] = pivot;
    return mark;
}

/**
 * 双边循环法
 *我们随意抽取一个数作为基准值，然后从数组左右两边进行扫描，先从左往右找到一个大于基准值的元素，将下标指针记录下来，
 * 然后转到从右往左扫描，找到一个小于基准值的元素，交换这两个元素的位置，
 * 重复步骤，直到左右两个指针相遇，再将基准值与左侧最右边的元素交换。
 */
public static int partitionV2(int[] arr, int start, int end) {
    int pivot = arr[start];
    int left = start;
    int right = end;
    while (left!=right){
        while (left<right && arr[right]>pivot)
            right--;
        while (left<right && arr[left]<=pivot)
            left++;
        if(left<right){
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    arr[start] = arr[left];
    arr[left] = pivot;
    return left;
}

堆排序

堆排序顾名思义，是利用堆这种数据结构来进行排序的算法。

堆的特性：

• 必须是完全二叉树
• 任一结点的值是其子树所有结点的最大值或最小值

构建二叉堆的过程其实就是让所有非叶子节点依次下沉

二叉堆插入节点就是最后一个位置不断上浮

二叉堆删除头结点就是用最后一个元素代替头结点然后下沉

public class No7HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{8,4,1,6,3,7,5,2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int len = arr.length;
        //构建堆
        buildHeap(arr,len);
        //构建堆完成之后，交换arr【0】与arr【len-1】，隐藏arr【len-1】
        //将a【0】下沉，主要将最大元素浮上来
        for (int i = len-1; i >0 ; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            sink(arr,0,i);
        }
    }
    //构建最大堆，让所有非叶子节点一次下沉
    public static void buildHeap(int[] arr, int len) {
        for (int i = len/2; i >= 0; i--) {
            sink(arr,i,len);
        }
    }

    /***
     *   下沉调整
     * @param arr 数组
     * @param i 调整位置
     * @param len 数组范围
     */
    public static void sink(int[] arr, int i, int len) {
        int parent = i;
        int temp = arr[i];//节点值
        int child = 2*i+1;//左孩子
        while (child<len){//这里的判断条件一定要是这
            //这里的判断条件，要考虑没有右孩子节点的情况
            if(child+1<len && arr[child+1]>arr[child])//右边大于左边，定位到右边
                child++;
            if(temp>arr[child])//如果父节点大于左边和右边，则直接跳出
                break;
            //无序真正交换，直接遍历赋值
            arr[parent] = arr[child];
            parent = child;
            child = 2*child+1;
        }
        //最后要换回来
        arr[parent] = temp;
    }
}