[数据结构与算法]十大排序算法(Java实现)

1.冒泡排序(Bubble Sort)

1.1 冒泡排序意指经过层层排序后，较小的数会慢慢浮到最前面。冒泡排序是一种简单且稳定的排序算法。

1.2 算法描述

• 比较相邻的元素，如果第一个比第二个数据大，就交换第二个元素的位置；
• 对每一对相邻元素做相同的工作，从开始第一对到结尾的最后一对，这样结束一轮比较后最后一个元素是此序列最大的元素；
• 针对所有的元素重复以上的步骤，除了最后已确定顺序的元素；
• 重复步骤1~3，直到排序完成。

1.3 代码实现

public class BubbleSort {
    public static int[] bubbleSort(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }

        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                /*
                 j比较的次数为数组长度减去i的原因是：
                 每遍历一次后总会确定此次遍历中的最大的数并放在数组尾部，
                 故j每次只需遍历这些已确定数据前面的一部分数据
                 */
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }

    public static void main(String[] args){
        int[] array = {5,7,9,1,2,3};
        int[] sort = bubbleSort(array);
        for (int value : sort) {
            System.out.println(value);
        }
    }

}

2.选择排序(Selection Sort)

1.1 选择排序即首先在未排序列中找到最小(大)的元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小(大)的元素，然后放到已排序列末尾，以此类推，直到所有元素均排序完毕。

1.2 算法描述

• 初始状态：无序区为R[1…n]，有序区为nul；
• 第i次排序(i = 1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R[i,n]。该次排序从当前无序区中选出最大(小)元素，将它放在有序区末尾，即于无序区的第一个元素进行交换；
• 重复第二个步骤，直到排序完成；

1.3 代码实现

public class SelectionSort {
    public static int[] selectionSort(int[] arr){
        if(arr == null || arr.length == 0){
            return null;
        }

        for(int i=0; i<arr.length; i++){
            int maxIndex = i;
            for(int j = i+1; j<arr.length; j++){
                // 该循环的目的在于找到最大元素(也可以找最小元素)所在位置，记录其索引值
                if (arr[j] > arr[maxIndex]){
                    maxIndex = j;
                }
            }
            // 将找到的目标元素替换到已排序列末尾
            int temp = arr[maxIndex];
            arr[maxIndex] = arr[i];
            arr[i] = temp;
        }

        return arr;
    }

    public static void main(String[] args){
        int[] arr = {7,2,0,8,5,1};
        int[] sort = selectionSort(arr);
        for(int ele : sort){
            System.out.println(ele);
        }
    }

}

3.插入排序(Insertion Sort)

1.1 插入排序即将未排序列中的元素依次与已排序列中的元素从后向前进行比较，插入到相应位置上。

1.2 算法描述

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已排序列中从后向前扫描；
• 如果已排序的元素大于此元素，则将已排序元素向后移一位；
• 重复步骤3，直到找到已排序列的元素小于或者等于此元素所在位置；
• 将此元素插入到该位置后；
• 重复步骤2~5.

1.3 代码实现

public class InsertionSort {
    public static int[] insertionSort(int[] arr){
        if (arr == null || arr.length == 0){
            return null;
        }

        for(int i = 1; i<arr.length; i++){
            // 取出要插入排序的元素
            int current = arr[i];
            // 记录此元素的索引
            int index = i;

            for(int j = i - 1; j >= 0 ; j--){
                // 如果比较的元素大于要插入的元素，则将比较的元素向后移动一位
                if (current < arr[j]){
                    arr[j+1] = arr[j];
                    // 记录插入元素要放置的位置
                    index = j;
                }else {
                    // 已排序列是有序的，故当从后向前比较时遇到第一个小于等于待插入元素时即可跳出循环比较
                    break;
                }
            }

            // 将要插入排序的元素放到对应的位置
            if (index != i){
                arr[index] = current;
            }
        }
        return arr;
    }

    public static void main(String[] args){
        int[] arr = {9,7,5,8,1,0};
        int[] ints = insertionSort(arr);
        for(int param : ints){
            System.out.println(param);
        }
    }

4.希尔排序

1.1 希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2)的第一批算法之一。

1.2 算法描述

• 将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序；
• 假设一个序列共有n个元素，则可以设定一个增量序列为：n/2、n/2/2、n/2/2/2…1，每趟排序中依次选取一个增量进行分组；
• 按照直接插入排序的方法对每个分组进行排序；

1.3 操作步骤

1.4 代码实现

public class ShellSort {
    public static int[] shellSort(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }

        // gap为增量序列，依次以gap为增量进行分组
        for (int gap = array.length / 2; gap > 0; gap = gap / 2) {
            // 每一分组按照直接插入法进行排序
            for (int i = gap; i < array.length; i++) {
                // current记录当前要进行比较的元素
                int current = array[i];
                // j记录当前要进行比较的元素同一分组中的前一个元素
                int j = i - gap;
                
                // 前一个元素大于要进行比较的元素，则前面一个元素在同一分组中向后移一位，对于整个序列来说需要后移gap个位置
                while (j >= 0 && array[j] > current) {
                    array[j + gap] = array[j];
                    // 继续向前找组内元素进行比较
                    j -= gap;
                }
                
                // 当向前找gap个位置发现不满足while条件时，则j+gap即为当前元素要插入的位置
                array[j + gap] = current;
            }
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = {8, 9, 1, 3, 7, 6, 5, 2, 4, 0, 2};
        int[] ints = shellSort(array);
        for (int param : ints) {
            System.out.println(param);
        }
    }

5. 归并排序(Merge Sort)

1.1 归并排序是采用分治法(Divide and Conquer)的一个非常典型的应用，且各层分治递归可以同时进行。归并排序速度仅次于快速排序，为稳定排序算法，一般也称为2-路归并，一般用于对总体无序，但是各子项相对有序的序列。

1.2 算法描述
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

• 分解(Divide)：将n个元素分成含n/2个元素的子序列；
• 解决(Conquer)：用归并排序法对子序列进行递归排序；
• 合并(Combine)：合并已排序的子序列得到已排序结果；

1.3 操作步骤
采用递归法，可想象为树结构进行递归处理，如下图：

1.4 代码实现

public class MergeSort {
    public static int[] sort(int[] a, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 递归
            sort(a, low, mid);
            sort(a, mid + 1, high);
            merge(a, low, mid, high);
        }
        return a;
    }

    public static void merge(int[] a, int low, int mid, int high) {
        if (a == null || a.length == 0) {
            return;
        }

        // 临时数组用来记录每次迭代排序后的数组
        int[] temp = new int[high - low + 1];
        // 临时数组中的索引
        int k = 0;
        // 从中间值开始比较前后两个数组
        int i = low, j = mid + 1;
        while (i <= mid && j <= high) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }

        // 当中间值后的数组全部存入到临时数组中，则直接将前半部分的数据存入到临时数组中
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        
        // 当中间值前的数组全部存入到临时数组中，则直接将后半部分的数据存入到临时数组中
        while (j <= high) {
            temp[k++] = a[j++];
        }

        // 将临时数组中的数据替换到源数组对应索引的位置
        for (int l = 0; l < temp.length; l++) {
            a[low + l] = temp[l];
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 2, 9, 4, 1};
        int[] sort = sort(arr, 0, 6);
        for (int i : sort) {
            System.out.print(i + " ");
        }

    }

6. 快速排序(Quick Sort)

1.1 快速排序是通过一趟排序将待排序元素分隔成独立的两部分，其中一部分元素比"基准"小，另一部分元素比“基准”大。使用分治法再分别对这两部分元素继续进行排序，以达到整个序列有序。

1.2 算法描述

1. 从数列中挑出一个元素，称为“基准”(pivot)；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的元素可以到任意一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作；
3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

1.3 操作步骤

1. 随机选取一个元素作为基准(一般选取队列中的第一个元素)。先从队尾开始向前扫描且当low<high时，如果a[high]>temp，则high–，但如果a[high]<temp，则将high的值赋值给low，即arr[low]=arr[high]，同时要转换数组扫描的方式，即需要从队首开始向队尾进行扫描
2. 当从队首开始向队尾进行扫描时，如果arr[low]<temp，则low++，但如果arr[low]>temp，则需要将low位置的值赋值给high位置，即arr[high]=arr[low]，同时将数组扫描方式换为由队尾进行扫描
3. 一轮循环结束后low或high的位置就是该基准元素在数组中的正确索引位置。
4. 递归的将基准元素前后的序列分别执行123步骤直至整个序列有序。

1.4 代码实现

public class QuickSort {

    private static void quickSort(int[] arr, int low, int high) {

        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getIndex(arr, low, high);

            // 迭代对基准前和基准后的数组进行相同操作
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }
    }

    private static int getIndex(int[] arr, int low, int high) {
        // 基准元素
        int tmp = arr[low];
        // low指向队首元素，high指向队尾元素，首尾一起扫描
        while (low < high) {
            // 当队尾元素大于等于基准数据时,向前挪动high指针
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            // 队尾元素小于tmp,则将其赋值给low
            arr[low] = arr[high];

            // 队首元素小于等于tmp时,向前挪动low指针
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            // 队首元素大于tmp时,则将其赋值给high
            arr[high] = arr[low];

        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        arr[low] = tmp;
        // 返回tmp的正确位置
        return low;
    }

    public static void main(String[] args) {
        int[] arr = {20, 38, 36, 21, 23, 22, 13};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

}

7. 堆排序(Heap Sort)

1.1 堆排序是指利用堆这种数据结构所设计的一种的排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：子结点的键值或索引总是小于(或者大于)它的父结点。

堆：是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；每个结点的值都小于或者等于其左右孩子结点的值称为小顶堆。

大顶堆特点：arr[i] >= arr[i2+1] && arr[i] >= arr[i2+2]
小顶堆特点：arr[i] <= arr[i2+1] && arr[i] <= arr[i2+2]

1.2 算法描述

• 将待排序序列构成一个大(小)顶堆，此时整个序列的最大(小)值就是堆顶的根结点；
• 将根结点与末尾元素进行交换，此时末尾就是最大(小)值；
• 然后将剩余n-1个元素重新构造成一个堆，就会得到n个元素的次小(大)值，如此反复执行便能得到一个有序序列。

1.3 操作步骤
使用堆排序将数组{2，8，9，6，5，3，7}进行升序排序

1.4 代码实现

public class HeapSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length == 0){
            return;
        }
        
        //构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }

        //调整堆结构,交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) {
            //将堆顶元素与末尾元素进行交换
            swap(arr, 0, j);
            //重新对堆进行调整
            adjustHeap(arr, 0, j);
        }
    }

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

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

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

8.计数排序

1.1 计数排序就是统计元素出现的次数，并将元素对应存储在额外开辟的数组下标中，故计数排序要求输入的数据必须是确定的且有范围的整数。

1.2 算法描述

• 找出待排序的数组中最大和最小的元素
• 统计数组中每个值为i的元素出现的次数，存入数组的第i项，并计数累加
• 反向填充目标数组：将数组中的数据按下标顺序输入到目标数组中

9.桶排序

1.1 若输入数据服从均匀分布，则将数据分到优先数量的桶里，然后每个桶再分别排序。

1.2 算法描述

• 设置一定数量的数组当做空桶
• 遍历元素，将数据根据映射关系分别放到对应的桶里
• 对每个不为空的桶进行内部排序
• 将不是空的桶里的元素拼接起来

10.基数排序

1.1 基数排序按照地位先排序后收集，然后中位排序后收集最后高位排序后收集。

1.2 算法描述

• 根据元素属性设置一定数量的空桶
• 按照元素低位到高位将元素放入桶中并收集

1.3 操作步骤

排序时间/空间复杂度与稳定性

1. 时间复杂度

• 平均情况下，快速排序、希尔排序、归并排序和堆排序的时间复杂度为O(nlog2n)，其他都是O(n^2)。特殊的计数排序为O(n+k)，桶排序为O(n)，基数排序为O(d(n+rd))。
• 最坏情况下，快速排序的时间复杂度为O(n^2)，其他都和平均情况下相同。

2. 空间复杂度

• 快速排序为O(log2n)，归并排序和桶排序为O(n)，计数排序为O(n+k)，基数排序为O(rd)，其他均为O(1)

3. 稳定性

• 快速排序、希尔排序、简单选择排序及堆排序为不稳定的，其他都是稳定的。