一 、排序算法概述

1.1 排序算法分类

比较类排序：
交换排序：冒泡排序、快速排序
插入排序：简单插入排序、希尔排序
选择排序：简单选择排序、堆排序
归并排序：二路归并排序、多路归并排序

非比较类排序：
计数排序、桶排序、基数排序

排序算法.png

1.2 算法复杂度分析

算法复杂度.png

1.3稳定性分析

稳定的排序算法为排序前后相等元素元素的顺序不变。即是稳定的排序算法。

二、冒泡排序

2.1 算法分析

冒泡排序顾名思义，泡泡在水中是一个个冒出水面，冒泡排序为每次循环列表，每次将当前最大（最小）的元素找出来，然后交换到已排序列表的末尾。比较的次数为N+(N-1)+（N-2）....+1。 实现的流程为先比较相邻的元素，如果第一个比第二个大（小）就交换，以此类推知道末尾。最后会将本次最大（最小的元素交换到末尾）是一个稳定的排序，相同元素排序靠前的会先被找到，但是如果判断条件写为>= 就交换则会变为不稳定的算法。

冒泡排序.gif

2.2 实现代码

/**
 * 冒泡排序
 * 循环找到最小（大）的元素交换位置
 *
 * @param arr
 * 稳定的排序算法
 * 最好情况0（n）
 * 最坏情况o(n*n)
 */
public static Integer[] bubbleSort(Integer[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = arr.length - 1; j > i; j--) {
            if (arr[j] > arr[j - 1]) {
                Integer temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

三、快速排序

3.1算法分析

快排的思想主要为通过找到一个中间元素，将列表元素分为两部分，然后递归将左边和右边同理带入，采用分治的思想，这里和二路归并排序不同，二路归并是由小的有序列表合并为大的有序列表，快排则是先将列表分为两部分，保证整体区间有序。
不是一个稳定的排序算法，因为排序过程涉及到元素的交换，可能改变元素的位置。

快速排序.gif

3.2实现代码

public static Integer[] quickSort(Integer[] arr) {
    quickSortPartition(arr, 0, arr.length - 1);
    return arr;
}

/**
 * 分区
 * @param arr
 * @param low
 * @param height
 */
public static void quickSortPartition(Integer[] arr, Integer low, Integer height) {
    if (low >= height) {
        return;
    }
    Integer i = low;
    Integer j = height;
    Integer temp = arr[low];
    while (i < j) {
        //向左寻找大于temp的从起始点相反的方向查找
        while (arr[j] <= temp && j > i) {
            j--;
        }
        //向右寻找小于temp 的元素
        while (arr[i] >= temp && i < j) {
            i++;
        }
        if (i < j) {
            Integer temp2 = arr[i];
            arr[i] = arr[j];
            arr[j] = temp2;
        }
    }
    //交换最后一个元素
    arr[low] = arr[i];
    arr[i] = temp;
    quickSortPartition(arr, low, i - 1);
    quickSortPartition(arr, i + 1, height);
}

四、插入排序

4.1算法分析

插入排序基本思想为将列表分为有序区间和无序区间，遍历无序区间，将元素插入到有序区间的某个位置。是一个稳定的排序算法，从第一个元素开始，默认此元素已经有序，取下一个元素找到相应位置插入。

插入排序.gif

4.2实现代码

/**
 * 插入排序，循环未排序期间。将值与已排序期间进行比较，已排序期间向后移动
 * 是稳定的算法 遍历已经排序的区域将元素插入
 * @param arr
 * @return
 */
public static Integer[] insertSort(Integer[] arr) {
    for (int i = 1; i < arr.length; i++) {
        Integer value = arr[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if (value > arr[j]) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
            arr[j] = value;
        }
    }
    return arr;
}

五、希尔排序

5.1算法分析

希尔排序核心思想为缩小增量排序，将列表划分为几组，保证组内元素有序，当将列表划分为一组时候，也就是整体有序的，会优先比较距离比较远的元素。

希尔排序.png

希尔排序.gif

5.2实现代码

/**
 * 希尔排序
 * @param arr
 * @return
 */
public static int[] sort(int[] arr) {
    // 首先设定为两个元素一组，下次迭代*2
    for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
        //从分组位置开始循环判断
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            // 保证分组内元素位置
            while (j - gap >= 0 && arr[j] > arr[j - gap]){
                swap(arr,j,j-gap);
                j-=gap;
            }
        }
    }
    return arr;
}

public static void swap(int[] arr, int a, int b) {
    arr[a] = arr[a] + arr[b];
    arr[b] = arr[a] - arr[b];
    arr[a] = arr[a] - arr[b];
}

六、选择排序

6.1算法分析

选择排序的基本思想为将列表分为有序区间和无序区间，循环无序区间找到当前最大（最小）的元素，然后放入到有序区间的末尾。

选择排序.gif

6.2实现代码

/**
 * 同样分为排序期间和未排序期间
 * 是不稳定的算法，当两个相同元素时候选择其中一个优先插入
 * 在未排序期间选择最大（小的元素插入已经排序的末尾）
 *
 * @param arr
 * @return
 */
public static Integer[] selectSort(Integer[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {

        Integer temp = arr[i];
        Integer max = i;
        for (Integer j = i + 1; j < arr.length; j++) {
            if (arr[j] > temp) {
                temp = arr[j];
                max = j;
            }
        }
        Integer temp2 = arr[max];
        arr[max] = arr[i];
        arr[i] = temp2;
    }
    return arr;
}

七、堆排序

7.1算法分析

堆排序的核心思想为将列表构造为大根堆或者小跟堆，一般情况下升序选择构建大根堆，降序选择构造小根堆。原因在于构建完毕堆之后，堆顶元素即当前元素的最大（最小）值，将堆顶元素依次与未排序期间的末尾元素交换，最终列表有序。

堆排序.gif

7.2实现代码

public static int[] heapSort(int[] arr) {
    //完全二叉树的节点为2n-1 第一个非叶节点为length/2 再减取数组从0开始
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        //构造堆
        reBuidHeap(arr, i);
    }

    //堆顶元素和队尾元素交换
    for (int j = arr.length - 1; j > 0; j--) {
        swap(arr, 0, j);
        //交换完之后再调整堆
        reBuidHeap(arr, 0);
    }
    return arr;
}

/**
 * 构造堆
 *
 * @param arr
 * @param position
 */
public static void reBuidHeap(int[] arr, int position) {
    //左节点位置
    int left = position * 2 + 1;
    //右节点位置
    int right = position * 2 + 2;
    //暂定最大值为父节点
    int largest = position;

    if (left < arr.length && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right > arr.length && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != position) {
        swap(arr, largest, position);
        reBuidHeap(arr, largest);
    }
}

public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

八、归并排序

8.1算法分析

归并排序的思想主要为将列表分为两个区间，然后再将区间划分为更小的区间，区间合并时候保证合并后的区间有序。采用分治的思想。

归并排序.gif

8.2实现代码

public static Integer[] sort(Integer[] arr, int low, int height) {
    int mid = (low + height) / 2;
    if (low < height) {
        sort(arr, low, mid);
        sort(arr, mid + 1, height);
        merge(arr, low, mid, height);
    }
    return arr;
}

public static void merge(Integer[] arr, Integer low, Integer mid, Integer height) {
    int[] temp = new int[height - low + 1];
    int i = low;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= height) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    //插入左边剩余的
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    //插入右边剩余的
    while (j <= height) {
        temp[k++] = arr[j++];
    }

    //临时数组copy到原数组
    for (int x = 0; x < temp.length; x++) {
        arr[x + low] = temp[x];
    }
}

九、计数排序

9.1算法分析

计数排序顾名思义，就是通过统计元素的个数来排名。不过要求输入的数据需要有一个给定的整数范围，然后会开辟范围内大小的空间。统计数组中元素的出现次数。

计数排序.gif

9.2实现代码

public static int[] countingSort(int[] arr){
    int max = arr[0];
    int min=arr[0];
    for (int i = 0; i <arr.length ; i++) {
        if (arr[i]>max){
            max = arr[i];
        }
        if (arr[i]<min){
            min = arr[i];
        }
    }

    //找到区间
    int length = max - min;
    ArrayList<ArrayList<Integer>> temp = new ArrayList<>();
    for (int i = 0; i <= length; i++) {
        temp.add(new ArrayList<Integer>());
    }

    for (int i = 0; i < arr.length; i++) {
        int index = arr[i] - min;
        ArrayList<Integer> queue = temp.get(index);
        queue.add(arr[i]);
    }
    return arr;
}

十、桶排序

10.1算法分析

桶排序核心思想为将元素分发到各个桶之中，每个桶存储的元素的范围固定，保证桶列表的有序，桶中的元素可以使用其他排序算法保证有序，然后依次将元素从桶中拿出，就保证了元素的有序性

桶排序.gif

10.2实现代码

public static Integer[] bucketSort(Integer[] arr,int bucketNum) {
    //找到最大的元素和最小的元素保证范围
    Integer max = arr[0];
    Integer min = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }

    //每个桶决定存放的元素范围
    double split = (max - min) /((bucketNum-1)*1.0);
    List<List<Integer>> allBucket = new ArrayList<>();

    for (int i = 0; i < bucketNum; i++) {
        allBucket.add(new ArrayList<Integer>());
    }

    //将元素进行分发，分发结束后allBucket中存储的就是有序的元素
    for (int i = 0; i < arr.length; i++) {
        int val = arr[i];
        int bucketIndex = (int)Math.floor((val-min)/split);
        insertSort(allBucket.get(bucketIndex),arr[i]);
    }
    return null;
}

十一、基数排序

11.1算法分析

基数排序主要为先将列表元素根据个位进行排序，然后收集，收集完毕后进行十位排序，依次类推

基数排序.gif

11.2实现代码

public static Integer[] radixSort(int[]arr){
    int max = 0;
    for (int i = 0; i < arr.length; i++) {
        if (max<arr[i]){
            max = arr[i];
        }
    }
    //计算最大数的位数intint
    int times = 0;
    while (max>0){
        max = max/10;
        times++;
    }
    
    ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < 10; i++) {
        temp.add(new ArrayList<Integer>());
    }

    //抽取各组数
    for (int i = 0; i < times; i++) {
        for (int j = 0; j < arr.length; j++) {
            int x = arr[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
            List s = temp.get(x);
            s.add(arr[j]);
        }

        //开始收集排序
        int count = 0;
        for (int j = 0; j < 10; j++) {
            while (temp.get(j).size()>0){
                ArrayList<Integer> q = temp.get(j);
                arr[count] = q.get(0);
                q.remove(0);
                count++;
            }
        }
    }
    return null;
}