[数据结构与算法]超详细总结归纳一下常见十种排序算法

更多文章欢迎来我的博客https://endwas.cn交流、评论;

之前在学校学习数据结构的时候，学不太懂也没太认真学，最近找了个时间总结归纳后自己写了一下十种排序算法，用的是Java写的，暂时只适用于非负整数的排序，在关键代码上加了注释讲解，代码可能会存在bug，如有发现希望各位指教！

1.冒泡排序

最基本的排序算法，本质是依次遍历数组找到最小的（或最大）数交换到数组首位。但时间复杂度很高因为数组一次遍历只能确定一个最小的数。

图解

代码

package com.DataStructure;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * @author endwas
 * @date Created in 2021/8/18 16:13
 */

public class BubbleSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{11, 32, 42, 53, 76, 89, 90, 100, 30, 83})));
        System.out.println(Arrays.toString(sort(new int[]{121, 63, 45, 5, 4, 61, 35, 74, 65, 3, 45})));
        System.out.println(Arrays.toString(sort(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(sort(new int[]{10, 94, 128, 32, 61, 0, 456, 312, 2021, 18})));


    }

    public static int[] sort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        int local;
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                // 两两交换：如果当前位array[i]大就需要交换
                if (array[i] > array[j]) {
                    local = array[i];
                    array[i] = array[j];
                    array[j] = local;
                }
            }
        }
        return array;
    }
}

2.选择排序

顾名思义关键在于选择，本质是从数组中找到最小的元素将他位置记录下来，遍历完与数组首位元素交换。过程和冒泡排序很相似，都是找最小元素交换的过程，

图解

代码

package com.DataStructure;

import java.util.Arrays;

/**
 * 选择排序
 *
 * @author endwas
 * @date Created in 2021/8/18 16:13
 */
public class SelectionSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{41, 63, 45, 5, 61, 121, 90, 35})));
        System.out.println(Arrays.toString(sort(new int[]{121, 63, 45, 45, 45, 61, 35, 74, 65, 3, 45})));
        System.out.println(Arrays.toString(sort(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(sort(new int[]{10, 94, 128, 32, 61, 0, 456, 312, 2021, 18})));

    }

    public static int[] sort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }

        for (int i = 0; i < array.length; i++) {
            // 记录最小元素的位置和index为i的元素交换。
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
        return array;
    }

    private static void swap(int[] array, int first, int last) {
        int swap = array[first];
        array[first] = array[last];
        array[last] = swap;
    }
}

3. 插入排序

插入排序是从数组第二个元素将该元素和前面的元素进行比较排序，使未排序元素和前面已排序序列每个元素两两比较，找到插入的位置构建排序序列的过程，但因为已排序序列是倒序排好，所以当判断已排序序列元素比该元素小时就可以停止遍历插入。

图解

代码

package com.DataStructure;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{41, 63, 45, 5, 61, 121, 90, 35})));
        System.out.println(Arrays.toString(sort(new int[]{121, 63, 45, 45, 45, 61, 35, 74, 65, 3, 45})));
        System.out.println(Arrays.toString(sort(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(sort(new int[]{10, 94, 128, 32, 61, 0, 456, 312, 2021, 18})));

    }
    public static int[] sort(int[] a) {
        int temp;
        // 从 1->末尾
        for (int i = 1; i < a.length; i++) {
            // 从当前元素到0 一一比较
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1]) {
                    temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                } else {
                	// 如果判断不符合条件就不需要继续往前判断了因为前面都比该元素小的
                    break;
                }
            }
        }
        return a;
    }
}

4.希尔排序

希尔排序是一种特殊的插入排序，对数组元素通过不同间隔分组排序，最后需以间隔为1进行排序，来达到有序序列。

图解

代码

package com.DataStructure;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author endwas
 * @date Created in 2021/8/19 15:58
 */
public class ShellSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{121, 63, 45, 5, 4, 61, 35, 74, 65, 3, 45})));
        System.out.println(Arrays.toString(sort(new int[]{11, 32, 42, 53, 76, 89, 90, 100, 30, 83})));
        System.out.println(Arrays.toString(sort(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(sort(new int[]{10, 94, 128, 32, 61, 0, 456, 312, 2021, 18})));
    }
    
    public static int[] sort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        // 步长 从array.length/2开始到1
        for (int distance = array.length / 2; distance > 0; distance /= 2) {
            // 从第步长+1个元素到最后一个 一一与距离步长为distance的上一个元素比较大小
            // 即如果distance为5 当前数组元素为index为5，那么就会比较5-5 index为0的元素 依次遍历到最后一个6->1 7->2
            for (int i = distance; i < array.length ; i++) {
                /* 注意：需要对每组元素都按顺序排序，并不是只是前后元素排序
                   例：distance = 2, array.length = 10时 会分为两组元素 0-2-4-6-8和1-3-5-7-9
                   此时对于index为0一组元素 0    2    4    6    8
                                         └----┙
                                         └---------┙
                                         └--------------┙
                                         └-------------------┙
                   ↓ 将会和前一个元素比较大小小的会放到最前面，目的就是对该组元素按顺序排序 类插入思想
                 */
                for (int j = i; j >= distance && array[j] < array[j-distance]; j -= distance) {
                    // array[j] < array[j-distance] 因为前面的元素已经排序好了 所以不满足就不需要继续获取下一个distance比较
                    swap(array, j, j-distance);
                }
            }
        }        
        return array;
    }
    private static void swap(int[] array, int first, int last) {
        int swap = array[first];
        array[first] = array[last];
        array[last] = swap;
    }

}

5.归并排序

归并排序本质是一种分而治之的思想，先对数组进行对半拆分直到数组长度为1不可拆分后，对两个不可拆分数组进行排序合并然后和另外一组合并的数组继续合并直到排序完成的过程。先拆后合的思想。

图解

代码

package com.DataStructure;

import java.util.Arrays;

/**
 * 归并排序（分而治之思想）
 *
 * @author endwas
 * @date Created in 2021/8/19 14:01
 */
public class MergeSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{11, 57, 42, 53, 21, 89, 90, 100, 30, 83})));
        System.out.println(Arrays.toString(sort(new int[]{121, 63, 45, 45, 45, 61, 45, 74, 65, 3})));
        System.out.println(Arrays.toString(sort(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(sort(new int[]{10, 94, 128, 32, 61, 0, 456, 312, 2021, 18})));
    }

    public static int[] sort(int[] array) {
        int[] temp = new int[array.length];
        return sort(array, 0, array.length - 1, temp);
    }

    public static int[] sort(int[] array, int left, int right, int[] temp) {
        // bugfix: use if instead of while, otherwise it will loop forever;
        if (left < right) {
            int mid = (left + right) >> 1;
            sort(array, left, mid, temp);
            sort(array, mid + 1, right, temp);
            merge(array, left, mid, right, temp);

        }
        return array;

    }

    private static void merge(int[] array, int left, int mid, int right, int[] temp) {
        int localLeft = left;
        int localMid = mid + 1;
        int localRight = right;
        int index = 0;
        // method 1: while && to sort
        // method 2: while || to sort
        while (localLeft <= mid && localMid <= localRight) {
            // bugfix: judge array's value instead of point value.
            if (array[localLeft] <= array[localMid]) {
            	// 排序数组指针+1、当前排序数组往后+1
                temp[index++] = array[localLeft++];
            } else {
                temp[index++] = array[localMid++];
            }
        }
        /*
        *   e.g: 1??.localLeft -> mid 5 6 7
        *        2??.localMid  -> localRight 1 3 8 9
        *   下面的作用就是当其中一组数组已经完全放入temp数组后 将剩下一组还没放完数的数组追加到temp末尾
        *   1 3 5 6 7（1??已经放完，追加2 ->） 8 9
        */
        while (localLeft <= mid) {
            temp[index++] = array[localLeft++];
        }
        while (localMid <= right) {
            temp[index++] = array[localMid++];
        }
        // 将temp数组覆盖掉进行归并操作的原数组位置，即将归并数组位置排序好
        index = 0;
        // bugfix: left needs equal to right, otherwise it will miss array's right index value.
        while (left <= right){
            array[left++] = temp[index++];
        }
    }
}

6.快速排序

快速排序和归并排序有点相似，也是将数组进行拆分，但归并是拆分后对子数组进行排序后合并，而快速则是将基准元素进行交换达到左侧为小于基准元素和大于基准元素分列两边。

图解

代码

写了两种思路：
1?? 左右两指针根据依次移动，目标元素target为数组第一个元素，右指针找到比target小的，左指针找到比target大的两者交换，直到左右指针相遇，将target元素和相遇位置元素交换，然后左右两边数组继续递归。
2?? 先右指针移动，目标元素target为数组第一个元素，遇到比target小的就将target和右指针对应元素交换，然后左指针移动找到比target元素大的数，将target和该数进行交换。直到左右指针相遇，继续上述操作递归。

package com.DataStructure;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author endwas
 * @date Created in 2021/8/19 15:58
 */
public class QuickSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{60, 32, 42, 53, 76, 89, 90, 100, 30, 83})));
        System.out.println(Arrays.toString(sort(new int[]{121, 63, 45, 45, 45, 61, 35, 74, 65, 3, 45})));
        System.out.println(Arrays.toString(sort(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(sort(new int[]{10, 94, 128, 32, 61, 0, 456, 312, 2021, 18})));

    }

    public static int[] sort(int[] array, int left, int right) {
        if (left < 0 || right > array.length - 1) {
            throw new IndexOutOfBoundsException("排序数组范围越界");
        }
        if (array == null || array.length <= 1) {
            return array;
        }
        // 快速排序递归算法1
        partition(array, left, right);
        return array;
    }

    private static void partition(int[] array, int left, int right) {

        int leftIndex = left;
        int currentIndex = left;
        int rightIndex = right;
        if (left >= right) {
            return;
        }
        while (left < right) {
            // 左右指针从left、right移动，左指针找到第一个比target大的数，右指针找到第一个比target小的数，将两者交换
            while (left < right && array[currentIndex] <= array[right]) {
                right--;
            }
            while (left < right && array[currentIndex] >= array[left]) {
                left++;
            }
            if (left < right) {
                swap(array, left, right);
            }
        }
        // 然后将target元素和左右指针相遇的元素交换，接着继续两边的递归
        swap(array, currentIndex, left);
        partition(array, leftIndex, left - 1);
        partition(array, right + 1, rightIndex);

    }

    public static void partition2(int[] array, int left, int right) {
        // 如果左指针不小于有指针 跳出递归
        if (left >= right) {
            return;
        }
        /*
            left、right是滑动指针 leftIndex、rightIndex是当前需要递归排序的数组左右边界 index
            currentIndex是当前target index，开始为数组第一个元素array[left]
         */
        int leftIndex = left;
        int currentIndex = left;
        int rightIndex = right;
        // 当前左右指针未相遇就继续移动
        while (left < right) {
            // 因为选择第一个元素作为target，所以需要从右边开始往左移动
            while (left < right && array[right] >= array[currentIndex]) {
                right--;
            }
            // 判断是因为要确定是找到了比target元素小的值，还是两个指针相遇，如果相遇就不需要交换
            if (left < right) {
                swap(array, right, currentIndex);
                // 交换后记录target元素的index。
                currentIndex = right;
            }
            // 同上理由
            while (left < right && array[left] <= array[currentIndex]) {
                left++;
            }
            if (left < right) {
                swap(array, left, currentIndex);
                currentIndex = left;
            }
        }
        // 对左右进行递归操作（此时left和right是相等的）
        partition2(array, leftIndex, left - 1);
        partition2(array, right + 1, rightIndex);
    }

    public static int[] sort(int[] array) {
        return sort(array, 0, array.length - 1);
    }

    private static void swap(int[] array, int first, int last) {
        int swap = array[first];
        array[first] = array[last];
        array[last] = swap;
    }

}

7.堆排序

堆排序是一种很巧妙的排序，将数组看作树结构，对数组依次进行大顶堆操作找出最大的元素，移到末尾，直到所有元素排序完成。

图解

代码

package com.DataStructure;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author endwas
 * @date Created in 2021/8/20 9:39
 */
public class HeapSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{121, 63, 45, 5, 4, 61, 35, 74, 65, 3})));
        System.out.println(Arrays.toString(sort(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(sort(new int[]{10, 94, 128, 32, 61, 0, 456, 312, 2021, 18})));
    }

    public static int[] sort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        // 构建大顶堆，同时交换每次构建大顶堆数组最后一个数和顶部元素
        for (int i = array.length - 1; i > 0; i--) {
            // 构建大顶堆（从0-arrayLength-1、0-arrayLength-2...直到1）
            bigHeapSort(i, array);
            // 头元素和最后一个元素交换
            swap(array, 0, i);
        }
        return array;
    }

    private static void bigHeapSort(int last, int[] array) {
        // 找到最后一个非叶子节点，当前10个元素所以最后一个元素index是9那么最后一个非叶子结点index是9/2=4
        // 所以需要从4->0进行判断当前root结点是否比叶子节点大
        //          0
        //      1       2
        //    3    4   5   6
        //   7 8  9
        int root = last / 2;
        for (int i = root; i >= 0; i--) {
            // 因为需要将数组看作一颗二叉树，所以树根对应数组为0的值
            // 所以树的左右结点为 2 * root\2 * root +1 对应数组就位 2 * root +1\ 2 * root +2
            int leftChild = 2 * i + 1;
            int rightChild = 2 * i + 2;
            // 右结点index是否小于当前需要遍历数组长度且子节点大于root结点 则交换数组位置
            // （第一个判断的目的有两点 1.可能该结点只有左节点，所以要判断右节点是否存在|2.不要影响已经排好序的序列）
            if (rightChild < last + 1 && array[rightChild] > array[i]) {
                swap(array, i, rightChild);
            }
            // 左子树index是否小于当前需要遍历数组长度且子树大于root结点 则交换数组位置
            if (leftChild < last + 1 && array[leftChild] > array[i]) {
                swap(array, i, leftChild);
            }
        }

    }


    private static void swap(int[] array, int first, int last) {
        int swap = array[first];
        array[first] = array[last];
        array[last] = swap;
    }

}

8.计数排序

计数排序本质不是一种排序算法，他统计每个元素出现的次数，然后将元素依次输出到数组中，所需要额外的数组长度取决于最大和最小数的差，如果数组中分布不集中，将会浪费大量空间。

图解

代码

package com.DataStructure;

import java.util.Arrays;

/**

• 计数排序

• @author endwas

• @date Created in 2021/8/19 11:22
  */
  public class CountingSort {

  public static void main(String[] args) {
  System.out.println(Arrays.toString(sort(new int[]{11, 25, 42, 53, 76, 89, 21, 70, 33, 83})));
  System.out.println(Arrays.toString(sort(new int[]{121, 63, 45, 5, 4, 61, 35, 74, 65, 3})));
  System.out.println(Arrays.toString(sort(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1})));
  System.out.println(Arrays.toString(sort(new int[]{10, 94, 128, 32, 61, 0, 456, 312, 2021, 18})));

  }

  public static int[] sort(int[] array) {
  if (array == null || array.length <= 1) {
  return array;
  }
  int maxValue = BucketSort.getMaxValue(array);
  int minValue = BucketSort.getMinValue(array);
  // System.out.println("max: " + maxValue + " min: " + minValue);
  // 创建数组 大小为 最大数-最小数 20-12+1 = 长度9
  // 12 13 14 15 16 17 18 19 20
  int[] countingArray = new int[maxValue - minValue + 1];
  // 给每个数计数 最小的数在0的位置
  // value-minValue 15-12即在3的位置
  for (int value : array) {
  countingArray[value - minValue]++;
  }
  // 根据计数数组得到当前排序位置
  int i = array.length;
  // 倒序遍历计数数组 从最后一位 index = length-1
  for (int j = countingArray.length - 1; j >= 0; j–) {
  // 拿到当前的值 即个数 遍历次数
  // 修改array数组
  for (int k = countingArray[j]; k > 0; k–) {
  array[–i] = minValue + j;
  }
  }
  return array;
  }
  }

9.桶排序

桶排序本质是计数排序的一种优化，在计数排序中一个数将占用一个额外的储存空间，桶排序将一个桶存储一个范围的数，节省了空间。

图解

代码

package com.DataStructure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 桶排序
 *
 * @author endwas
 * @date Created in 2021/8/18 16:13
 */
public class BucketSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{11, 32, 42, 53, 76, 89, 90, 100, 30, 83})));
    }

    public static int[] sort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        int maxValue = getMaxValue(array);
        int minValue = getMinValue(array);
        System.out.println("max: " + maxValue + " min: " + minValue);
        int difference = maxValue - minValue;
        // 需要+1个桶比如 10个数 最大100 最小0那么就需要10+1个桶因为 0-9一桶 10-19...100-109所以需11个桶
        int bucketNum = difference / array.length + 1;
        List<List<Integer>> lists = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            lists.add(new ArrayList<>());
        }

        for (int value : array) {
            // 计算元素在桶的位置因为元素大的需要在后面的桶所以需要 bucketNum-1-currentBucket
            lists.get(bucketNum - 1 - ((maxValue - value) / array.length)).add(value);
        }

        int count = 0;
        System.out.println("buckets are: " + lists);
        for (List<Integer> list : lists) {
            // 对每个桶进行排序
            list.sort(Comparator.comparingInt(a -> a));
            if (!list.isEmpty()) {
                for (int integer : list) {
                    array[count++] = integer;
                }
            }
        }
        return array;
    }


    public static int getMaxValue(int[] array) {
        int maxValue = Integer.MIN_VALUE;
        for (int value : array) {
            maxValue = Math.max(value, maxValue);
        }
        return maxValue;
    }

    public static int getMinValue(int[] array) {
        int minValue = Integer.MAX_VALUE;
        for (int value : array) {
            minValue = Math.min(value, minValue);
        }
        return minValue;
    }
}

10.基数排序

基数排序是桶排序的优化，根据从个位数到最高位依次来分配桶，所以一共只会有10个桶（对应位数为0-9）但相对于桶排序，基数排序在桶内的元素是排序好顺序的。

图解

代码

package com.DataStructure;

import java.util.Arrays;

/**
 * 基数排序
 *
 * @author endwas
 * @date Created in 2021/8/18 14:24
 */
public class RadixSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{41, 63, 45, 5, 61, 121, 90, 35})));
        System.out.println(Arrays.toString(sort(new int[]{121, 63, 45, 45, 45, 61, 35, 74, 65, 3, 45})));
        System.out.println(Arrays.toString(sort(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(sort(new int[]{10, 94, 128, 32, 61, 0, 456, 312, 2021, 18})));

    }

    public static int[] sort(int[] array){
        if (array == null || array.length <= 1) {
            return array;
        }
        int maxLength = getMaxLength(array);
        //  System.out.println("maxLength: " + maxLength);
        int mod = 1;
        for (int i = 0; i < maxLength; i++) {
            // 10 * arraylength 用于排序所以需要一个表格来存放可能的情况，因为长度为0-9所以最大只可能为10
            // ======================================
            //  21 32 34 65 77 48 29
            //  31          37
            //  41
            int[][] results = new int[10][array.length];
            // 10个数 0-9用于计数 统计上面每个位置个数 如上得到的
            //  3  1  1  1  2  1  1
            int[] count = new int[10];
            for (int value : array) {
                // 取当前位数
                // 745/1 % 10 = 5
                // 745/10 % 10 = 4
                // 745/100 % 10 = 7
                int charNum = (value / mod) % 10;
                // 给当前位数的数组赋值并且当前位数计数+1
                results[charNum][count[charNum]++] = value;
            }
            // 遍历替换array
            int s = 0;
            for (int k = 0; k < count.length; k++) {
                for (int t = 0; t < count[k]; t++) {
                    // 取每一位的数字
                    array[s++] = results[k][t];
                }
            }
            mod *= 10;
        }
        return array;
    }

    private static int getNumLength(int num){
        int count = 0;
        while (num > 0){
            num /= 10;
            count++;
        }
        return count;
    }

    private static int getMaxLength(int[] array){
        int k = 0;
        for (int value : array) {
            k = Math.max(getNumLength(value), k);
        }
        return k;
    }
}

总结

十种排序算法各有各的特色，有常规的遍历排序冒泡排序、选择排序；有很巧妙的排序算法堆排序；也有通过递归完成的快速排序、归并排序；也有计数归纳排序的计数排序、桶排序、基数排序；
排序算法是算法的基础，之前一直没认真学，最近就抽空边学边总结十种排序算法，收获还是很多的，代码还是很多地方可以优化的，感觉并没有达到每种算法的最好时间、空间复杂度。