现在使用的排序都有对应的封装库，详细了解一下排序算法的逻辑的必要性，包括但不限于冒泡排序、快速排序；二叉树的前中遍历是什么排序？

算法总结：十大排序算法

一、冒泡排序（BubbleSort）

假设给出的待排序列表长度为n，我们需要知道的是n-1表示遍历的趟数，每一趟我们需要做什么操作呢？就是判断相邻的两个数的大小，如果是升序的话，当前一个数大于后一个数的时候，就交换两个这两个数，然后继续向后遍历。

冒泡排序是稳定排序方法，如果当数据已经是排序好了的话， 我们可以定一个swap的标识，当我们进行数据交换的时候把swap设置成true，如果之后发现swap是false的话，就表示经历了一轮变换后，swap没有变化，就表示数据已经是排序好了，可以直接break。

Java0

public int[] bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        // 为什么是n-1，因为最后一个数在倒数第二趟排完之后就是有序的了
        for (int j = 0; j < arr.length - 1; j++) {
            // 这里可以优化成 for (int j = 0; j < arr.length - 1 - i; j++)  因为遍历几趟，就有几个数是已经排好了的
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    return arr;
}

Java1

public int[] bubbleSort(int[] arr) {
    for (int i = arr.length - 1; i >= 0; i--) {  // 趟数，从后往前遍历
        for(int j=0;j<i;j++){  // 控制第二层的遍历数量
            if(arr[j] > arr[j+1]){
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
    return arr;
}

二、选择排序（SelectionSort)

选择排序算法的主要思路还是遍历，和冒泡排序类似，假设数据的长度为n，那么需要遍历n-1趟，我们每一趟选取里面最小的数据和趟数对应下标的数据进行交换。

Java

package org.sortIndex;

/**
 * 选择排序
 *
 * @author 邓聪
 */
public class SelectionSort {

    public int[] selectionSort(int[] arr) {
        int min = 0;
        for (int i = 0; i < arr.length - 1; i++) {  // 趟数
            min = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;  // 记录最小的数的下标
                }
            }
            if(min != i){
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, -2};
        SelectionSort selectionSort = new SelectionSort();
        arr = selectionSort.selectionSort(arr);
        for(int dt: arr){
            System.out.println(dt);
        }

    }
}

三、插入排序（InsertionSort）

大概的思路就是，把第一个元素看做是有序的，从第二个元素开始遍历，然后把后面的元素插入到前面已经排好顺序的数组里面。怎样实现插入呢？就是先保留当前待插入的数据，然后将前面大于待插入的数据都往后移动一个位，找到待插入数据的位置，让将待插入数据插入到指定位置。

适用场景：

在JDK7 java.util.Arrays所用的sort方法的实现中，当待排数组的长度小于47是，会使用插入排序。

Java

package org.sortIndex;

/**
 * 插入排序
 *
 * @author 邓聪
 */
public class InsertionSort {

    public void insertionSort(int[] arr){
        for(int i = 1;i<arr.length;i++){
            int tmp = arr[i];
            int j = i-1;  // 从下标i的前面一个开始找
            while(j >= 0 && arr[j] > tmp){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, -2};
        InsertionSort insertionSort = new InsertionSort();
        insertionSort.insertionSort(arr);
        for (int dt : arr) {
            System.out.println(dt);
        }
    }

}

四、归并排序（MergeSort）

归并排序典型的分治思想的体现，就是将数组的所有元素拆分到只有一个的时候，因为只有一个元素的时候，本质上是有序的；然后再将这些有序的单个元素合并起来的一个过程。

Java

/**
 * 归并排序
 *
 * @author 邓聪
 */
public class MergeSort {

    public void mergeSort(int[] arr){
        int[] tmpArr = new int[arr.length];
        msort(arr, tmpArr, 0, arr.length-1);
    }

    private void msort(int[] arr, int[] tmpArr, int left, int right) {
        // 拆分数组，当数组数据大于2的时候才进行拆分
        if(left<right){
            int mid = (right - left) / 2 + left;
            msort(arr, tmpArr, left, mid);
            msort(arr, tmpArr, mid + 1, right);
            merge(arr,tmpArr, left, mid, right);
        }
    }

    private void merge(int[] arr, int[] tmpArr, int left, int mid, int right) {
        // 合并
        int l = left, r = mid+1;
        int pos = left;

        while(l<=mid && r <= right){
            if(arr[l] < arr[r]){
                tmpArr[pos++] = arr[l++];
            }else{
                tmpArr[pos++] = arr[r++];
            }
        }
        while(l <= mid){
            tmpArr[pos++] = arr[l++];
        }
        while(r <= right){
            tmpArr[pos++] = arr[r++];
        }
        // 把临时数组中合并后的元素复制到原来的数组中
        while(left<=right){
            arr[left] = tmpArr[left];
            left++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, -2};
        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(arr);
        for(int dt: arr){
            System.out.println(dt);
        }
    }
}

五、快速排序（QuickSort）

快速排序的话，就是选定一个基准pivot，保存到临时变量里面，然后将大于pivot的数据都放到pivot的右边，把小于pivot的数据放到pivot的左边，然后在对做子集进行相同的操作就可以得到最后的排序结果。

public class QuickSort{

    public void quickSort(int[] arr){
        qsort(arr, 0, arr.length-1);
    }

    public void qsort(int[] arr, int left, int right){
        if(left >= right){
            return;
        }
        int pivot = partation(arr, left, right);
        qsort(arr, left, pivot-1);
        qsort(arr, pivot+1, right);
    }

    public int partation(int[] arr, int left, int right){
        int pivot = arr[left];
        while(left<right){
            while(left < right && arr[right] >= pivot){
                right--;
            }
            arr[left] = arr[right]; // 为什么这里left不用++， 因为下面是arr[left] <= pivot， 等于的话还是会left++的
            while(left<right && arr[left] <= pivot){
                left++;
            }
            arr[right] = arr[left];

        }
        arr[left] = pivot;
        return left;
    }

    public static void main(String[] args){
        int[] arr = {2,1,3,4,7,6,5};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr);
        for(int dt: arr){
            System.out.println(dt);
        }
    }
}

六、堆排序（HeapSort）

对需要满足是完全二叉树，什么是完全二叉树？完全二叉树除了最后一层都是满节点的。

堆序性：大根堆和小根堆；大根堆就是父节点元素要大于他的所有子节点元素，小根堆就是父节点元素

堆的存储方式：用数组进行存储

堆节点与数组下标之间的关系：如果父节点为i，做子节点就是2*i+1, 右子节点下标为2*i+2

堆的基本操作：上滤和下滤，上滤的话，就是将下面的节点向上移动，保持堆序性，多用于向堆中添加元素；下滤就是把上面的节点向下移动，使其满足堆序性。

建堆：自顶向下，自底向上

堆应用：优先级队列 Java优先级队列

堆排序主要的思路就是，我们以大根堆，降序输出为例；因为大根堆的性质，根节点的值是最大的，我们每次输出根节点的值，然后在把剩余的元素维护成大根堆，继续输出根节点的值，这样的话，我们就得到一个降序的数组。

所以堆排序有两步操作，一步是建堆， 一个是维护堆的性质。

建堆的话有两种方式，一种是自顶向下，一种是自底向上，我们以自顶向上为例操作，就是把最大值上滤到根节点。

Java

package org.sortIndex;

/**
 * 堆排序
 *
 * @author 邓聪
 */
public class HeapSort {
    public void swap(int[] arr, int left, int right) {
        // 交换数组中两个下标的值
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }

    public void heapSort(int[] arr) {
        int n = arr.length;

        // 建堆
        int i;
        for (i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 排序
        for (i = n - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }

    }

    /**
     * 维护堆性质
     *
     * @param arr 数组
     * @param n   数组长度
     * @param i   处理的节点
     */
    public void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[largest] < arr[left]) {
            largest = left;
        }
        if (right < n && arr[largest] < arr[right]) {
            largest = right;
        }
        if (largest != i) {
            swap(arr, largest, i);
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, -2};
        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(arr);
        for (int dt : arr) {
            System.out.println(dt);
        }
    }
}

计数排序

计数排序（Counting Sort） 是一种线性时间复杂度的排序算法，特别适用于数据范围有限的情况，它通过统计每个元素出现的次数，然后按照次数排序，从而实现排序。

计数排序的思路其实比较简单

1、确定待排序数据的最大值和最小值，根据最大值和最小值创建相应的数据结构来存储

2、循环带排序数据，统计每个值出现的次数

3、将计数数组转化成统计数组，方便确定元素输出的位置

public class CountingSort {
    public static int[] countingSort(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int j : arr) {
            min = Math.min(min, j);
            max = Math.max(max, j);
        }
        // 先用最大值+1，后面优化count数组
        int[] count = new int[max+1];

        // 计数
        for(int i=0; i<arr.length; i++) {
            count[arr[i]]++;
        }
        // 统计
        for(int i = 1;i<max+1;i++){
            count[i] += count[i-1];
        }

        // 最终结果
        int[] output = new int[arr.length];
        for(int i=arr.length-1;i>=0;i--){
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }
        return output;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{90, 89, 23, 77, 58};
        int[] ints = CountingSort.countingSort(arr);
        for(int x: ints){
            System.out.println(x);
        }
    }
}

public class CountingSort {
    public static int[] countingSort(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int j : arr) {
            min = Math.min(min, j);
            max = Math.max(max, j);
        }
        // 先用最大值+1，后面优化count数组， count的长度是max-min+1
        // 0 ~ max-min+1, 0-67 偏移量23（min）
        int len = max - min + 1;
        int[] count = new int[len];

        // 计数
        for (int j : arr) {
            // 查询出来的arr[i]的值有一个min的偏移量
            count[j - min]++;
        }
        // 统计
        for(int i = 1;i<len;i++){
            count[i] += count[i-1];
        }

        // 最终结果
        int[] output = new int[arr.length];
        for(int i=arr.length-1;i>=0;i--){
            int valToIndex = arr[i] - min;
            output[count[valToIndex] - 1] = arr[i];
            count[valToIndex]--;
        }
        return output;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{90, 89, 23, 77, 58};
        // int[] arr = new int[]{90, 89, 23, 77, 58}的话会创建一个容量为90的一个数组，但是实际容量只有5个
        int[] ints = CountingSort.countingSort(arr);

        for(int x: ints){
            System.out.println(x);
        }
    }
}

Contributors: smartdengc

Previous page数组和字符串

Next page滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）