写点什么

面试考试可用，十大排序算法

用户头像
我不自豪谁志豪
关注
发布于: 2020 年 05 月 07 日
面试考试可用，十大排序算法

微信公众号：一起学习大数据呀

关注可学习更多奇怪的知识！



前言

本文收集整理常见的十大排序算法，配套 Java 代码和视频短视频教程。帮助小伙伴们更快的理解和掌握。



不管你是为了应付考试，还是面试用，本文都可以帮到你，降低学习门槛，作者水平有限，难免遗漏错误，欢迎读者们留言指正。



1、冒泡排序

基本思想

每次比较两个相邻的元素，若顺序（从小到大或从大到小）“错误”就交换位置。



视频讲解

冒泡排序



代码实现

public static void bubbleSort(int[] arr)  {
    for (int i = 1; i < arr.length; i++) {
// 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
        boolean flag = true;
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) { //前面的数字大于后面的数字就交换
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                flag = false;
            }
        }
        if (flag) { //没有数据交换，数组已经有序，退出排序
            break;
        }
    }
}



2、选择排序



基本思想

每一趟从待排序的记录中选出最大（小）的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。



视频讲解



选择排序 （空降06:33）



代码实现

//1  找到数组最大的数字,并且返回下标
public static int findMaxPos(int[] arr , int n){
     int max = arr[0];
     int pos = 0;
     for (int i = 0; i < n; i++){
         if (max < arr[i]){
             max = arr[i];
             pos = i;
         }
     }
     return pos;
 }
 //2  让最大值与最后一个元素交换
public static void selectionSort(int[] arr, int n){
     while(n > 1) {  // 3 不断循环 1 和 2 步骤
         int pos = findMaxPos(arr, n);
         int temp = 0;
         temp = arr[n - 1];
         arr[n - 1] = arr[pos];
         arr[pos] = temp;
         n-- ;
     }
 }



3、插入排序



基本思想



将数组分为“已排序区间”和“未排序区间”。核心思想是提取“未排序区间”中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复该过程，直到排序区间中元素为空。



视频讲解



插入排序 空降(12:27)



代码实现

//1 选择已排序区间的后一个元宵插入
public void insert(int[] arr, int n){
    int key = arr[n];
    int i = n;
    while (arr[i - 1] > key){ //若前面的元素 > 后面元素
        arr[i] = arr[i -1]; // 前面元素抄写到后面元素位置
        i--;
        if (i == 0){//防止数组越界
            break;
        }
    }
    arr[i] = key; // 把要插入的元素归位
}
// 2 多趟插入
public void insertSort(int[] arr, int n){
     if (n <= 1){
        return ;
    }
    for (int i = 1; i < n; i++){ // 从第二个元素开始，第一个看成有序区域就好
        insert(arr, i);
    }
}



4、快速排序



基本思想

在数组中找到一个基准数,一般来说选第一个,然后加两个哨兵, i 和 j ,一个头一个尾.

i 从左到右扫描遇到大于 基准数 的数字停下, j 从右到左扫描,遇到小于 基准数 的停下.

然后 i 坐标的数与 j 坐标的数交换.



视频讲解

快速排序



代码实现

static void qucikSort(int left, int right) {
    if (left > right){
        return;
    }
    int i = left;
    int j = right;
    int povit = arr[left]; // 基准数
    int temp;
    while (i != j) {
        while (arr[j] >= povit && i < j) {
            j--;
        }
        while (arr[i] <= povit && i < j) {
            i++;
        }
        if (i < j) {
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    //基准数归位
    arr[left] = arr[i];
    arr[i] = povit;
    //递归
    qucikSort(left, i - 1);
    qucikSort(i + 1, right);
    return;
}



快排的优化方案

1) 基准数优化

随机取基准数

三位数取中: 选取数组开头，中间和结尾的元素，通过比较，选择中间的值作为快排的基准。

2) 序列长度达到一定大小时，使用插入排序

3) 尾递归优化

4) 聚集元素



5、希尔排序



基本思想

希尔排序是插入排序的一种改进版，通过比较相距一定距离（增量）的元素工作（交换；各趟比较所用的距离随着算法减小而减小，当增量减至1时，整个文件恰被分成一组，算法便终止。



视频讲解

希尔排序



代码实现

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {1, 3, 7, 2, 8, 6, 4, 9};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
 
  /**
  * 希尔排序 针对有序序列在插入时采用移动法。
  *
  * @param arr
  */
 static void shellSort(int[] arr) {
        //增量 gap，并逐步缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
 
            //从第 gap 个元素，逐个对其所在组进行直接插入排序操作
            for (int i = gap; i < arr.length; i++) {
 
                int j = i;
                int temp = arr[j];
                //j - gap  同组相隔的元素没数组越界；
                //arr[j - gap] > temp  前面的元素 > 后面的元素
                while (j - gap >= 0 && arr[j - gap] > temp) {
                    //把前面元素抄写到后面的位置
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
 
            }
 
        }
    }
}



6、归并排序



基本思想

该算法采用经典的分治（divide-and-conquer）策略，它将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。



视频讲解



归并排序



代码实现

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {6, 8, 10, 9, 4, 5, 2, 7};
        int L = 0;
        int R = a.length - 1;
        mergSort(a, L, R);
        System.out.println(Arrays.toString(a));
    }
 
    static void mergSort(int[] arr, int L, int R) {
        // 递归出口
        if (L == R) {
            return;
        } else {
            int M = (L + R) / 2;
            mergSort(arr, L, M);
            mergSort(arr, M + 1, R);
            merge(arr, L, M + 1, R);
        }
    }
 
    static void merge(int[] arr, int L, int M, int R) {
 
        int left_size = M - L;
        int right_size = R - M + 1;
        int[] L_arr = new int[left_size];
        int[] R_arr = new int[right_size];
 
        // 1  填充左边的数组
        for (int i = L; i < M; i++) {
            L_arr[i - L] = arr[i];
        }
        // 2 右边填充数组
        for (int i = M; i <= R; i++) {
            R_arr[i - M] = arr[i];
        }
 
        // 3 合并
        int i = 0, j = 0, k = L;
        while (i < left_size && j < right_size) {
            if (L_arr[i] > R_arr[j]) {
                arr[k] = R_arr[j];
                k++;
                j++;
            } else {
                arr[k] = L_arr[i];
                i++;
                k++;
            }
        }
        // 4 若右边数组已空,把剩余左边数组补上
        while (i < left_size) {
            arr[k] = L_arr[i];
            i++;
            k++;
        }
        // 5 若左边数组已空,同上
        while (j < right_size) {
            arr[k] = R_arr[j];
            k++;
            j++;
        }
    }
}



7、堆排序



基本思想

1）将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。

2）将其与末尾元素进行交换，此时末尾就为最大值。

3）将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。



视频讲解



堆排序



代码实现

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {2,5,3,1,10,4};
        heapSort(arr,arr.length);
       for (int i : arr){
           System.out.println(i + " ");
       }
    }
 
    /***
     *  交换函数
     * @param arr
     * @param i
     * @param j
     */
   static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /***
     * 构建大顶堆 (父节点大于子节点)
     * @param tree 数组(树)
     * @param n  数组长度
     * @param i  父节点
     */
    static void heapify(int tree[], int n, int i){
       // 递归出口
        if (i >= n){
           return;
        }
        //左孩子节点
        int c1 = 2*i + 1;
        //右孩子节点
        int c2 = 2*i + 2;
        // 假设 i 为最大值
        int max = i;
        // c1 < n 保证 c1 不出界
        if (c1 < n && tree[c1] > tree[max]){
            max = c1;
        }
        if (c2 < n && tree[c2] > tree[max]){
            max = c2;
        }
        if (max != i){
            swap(tree, max, i);
            heapify(tree, n, max);
        }
    }
 
    /***
     *  自下而上构建堆
     * @param tree  数组
     * @param n     数组长度
     */
    static void buidHeap(int[] tree, int n){
        // 最后一个叶子节点
        int last_node = n - 1;
        // 对应的父节点
        int parent = (last_node - 1)/2;
        for (int i = parent; i >= 0 ; i--){
            heapify(tree, n, i);
        }
    }
 
    /***
     * 堆排序
     * @param tree
     * @param n
     */
    static void heapSort(int[] tree, int n){
        // 1) 建一个堆
        buidHeap(tree, n);
        // 2) 从最后一个节点出发
        for (int i = n - 1; i >= 0; i--){
            // 3) 先交换一下根节点和最后一个节点
            // i 表示最后一个节点
            // 0  表示根节点
            swap(tree, i, 0);
            heapify(tree, i, 0);
        }
    }
}



8、计数排序



基本思想

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

注意：适合量大且范围小的数据



视频讲解



计数排序



代码实现

public class CountSort {
    public static void main(String[] args) {
        int[] arr = {2 , 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 3, 7, 8, 9 };
        System.out.println(Arrays.toString(countSort(arr)));
    }
 
    /***
     *  计数排序
     * @param arr
     * @return
     */
   static int[] countSort(int[] arr) {
       //目标数组
       int[] result = new int[arr.length];
        //计数数组
        int[] count = new int[10];
        //对原数组记录各元素出现的次数
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        System.out.println(Arrays.toString(count));
        //累加数组 看视频吧，我解释不了
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i - 1];
        }
        System.out.println(Arrays.toString(count));
        //有点像众神归位
        for (int i = arr.length - 1; i >= 0; i--) {
            result[--count[arr[i]]] = arr[i];
        }
        return result;
    }
}



9、桶排序



基本思想

1）将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序。

2）桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。



视频讲解



桶排序



代码实现

static void bucketSort(int[] arr) {
    //找到数组的最大值和最小值，用来计算映射函数
    int min = arr[0];
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
 
    //计算出桶的数量
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for (int i = 0; i < bucketNum; i++) {
        bucketArr.add(new ArrayList<Integer>());
    }
 
    //将属于同一个桶的元素放入对应的桶
    for (int i = 0; i < arr.length; i++) {
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
 
    //对每个桶进行排序
    for (int i = 0; i < bucketArr.size(); i++) {
        Collections.sort(bucketArr.get(i));
    }
    System.out.println(bucketArr.toString());
}



10、基数排序



基本思想

桶思想的一种，非比较排序，多关键字排序。

对数据的每一位（个位，十位，百位）进行桶排序或计数排序，对每位排序后结果就是有序的。



视频讲解

基数排序



代码实现

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {421, 240, 115, 532, 305, 430, 324};
        //1 先求最高位数
        int maxDigit = getMaxDigit(arr);
        System.out.println(Arrays.toString(radixSort(arr, maxDigit)));
    }
 
    /**
     * 获取最高位数
     */
    private static int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }
 
    private static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }
 
    static int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }
 
 
    static int[] radixSort(int[] arr, int maxDigit) {
        int[] result = new int[arr.length];
        int[] count = new int[10];
        // maxDigit 是数字中最大的位数
        for (int i = 0; i < maxDigit; i++) {
            //求余数，如个位，十位
            int division = (int) Math.pow(10, i);
            System.out.println(division);
            for (int j = 0; j < arr.length; j++) {
                int num = arr[j] / division % 10;
                System.out.println(num + " ");
                count[num]++;
            }
 
            //跟计数排序一样，先做累加数组，再复制（我也有点懵）
            for (int m = 1; m < count.length; m++) {
                count[m] = count[m] + count[m - 1];
            }
 
            for (int n = arr.length - 1; n >= 0; n--) {
                int num = arr[n] / division % 10;
                result[--count[num]] = arr[n];
            }
            System.arraycopy(result, 0, arr, 0, arr.length);
            Arrays.fill(count, 0);
        }
        return result;
    }
}





参考文献

1: 十大经典排序算法（动图演示）

2: 图解排序算法(四)之归并排序

3:【干货】史上最好的排序和数据结构入门



划线
评论
复制
发布于: 2020 年 05 月 07 日阅读数: 68

版权声明: 本文为 InfoQ 作者【我不自豪谁志豪】的原创文章。

原文链接:【http://xie.infoq.cn/article/9773e7298eba88f33ab5ddc8b】。文章转载请联系作者。

学习面试算法
用户头像

我不自豪谁志豪

关注

菜是原罪 2018.09.17 加入

一个练习两年半的 JAVA 实习生

评论

发布
暂无评论
Copyright © 2021, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
面试考试可用，十大排序算法