【45期】盘点那些必问的数据结构算法题之基础排序

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 【45期】盘点那些必问的数据结构算法题之基础排序

点击上方“Java面试题精选”,关注公众号

面试刷图,查缺补漏

号外:****往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅。

0 概述

排序算法也是面试中常常提及的内容,问的最多的应该是快速排序、堆排序。这些排序算法很基础,但是如果平时不怎么写代码的话,面试的时候总会出现各种bug。

虽然思想都知道,但是就是写不出来。本文打算对各种排序算法进行一个汇总,包括插入排序、冒泡排序、选择排序、计数排序、归并排序,基数排序、桶排序、快速排序等。快速排序比较重要,会单独写一篇,而堆排序见本系列的即可。

需要提到的一点就是:插入排序,冒泡排序,归并排序,计数排序都是稳定的排序,而其他排序则是不稳定的。

本文代码:https://github.com/shishujuan/dsalg/tree/master/code/alg/sort

1 插入排序

插入排序是很基本的排序,特别是在数据基本有序的情况下,插入排序的性能很高,最好情况可以达到O(N),其最坏情况和平均情况时间复杂度都是 O(N^2)。代码如下:


/**
 * 插入排序
 */
void insertSort(int a[], int n)
{
    int i, j;
    for (i = 1; i  n; i++) {
        /*
         * 循环不变式:a[0...i-1]有序。每次迭代开始前,a[0...i-1]有序,
         * 循环结束后i=n,a[0...n-1]有序
         * */
        int key = a[i];
        for (j = i; j  0 && a[j-1]  key; j--) {
            a[j] = a[j-1];
        }
        a[j] = key;
    }
}

2 希尔排序

希尔排序内部调用插入排序来实现,通过对 N/2,N/4…1阶分别排序,最后得到整体的有序。


/**
 * 希尔排序
 */
void shellSort(int a[], int n)
{
    int gap;
    for (gap = n/2; gap  0; gap /= 2) {
        int i;
        for (i = gap; i  n; i++) {
            int key = a[i], j;
            for (j = i; j = gap && key  a[j-gap]; j -= gap) {
                a[j] = a[j-gap];
            }
            a[j] = key;
        }
    }
}

3 选择排序

选择排序的思想就是第i次选取第i小的元素放在位置i。比如第1次就选择最小的元素放在位置0,第2次选择第二小的元素放在位置1。

选择排序最好和最坏时间复杂度都为 O(N^2)。

代码如下:


/**
 * 选择排序
 */
void selectSort(int a[], int n)
{
    int i, j, min, tmp;
    for (i = 0; i  n-1; i++) {
        min = i;
        for (j = i+1; j  n; j++) {
            if (a[j]  a[min])
                min = j;
        }
        if (min != i)
            tmp = a[i], a[i] = a[min], a[min] = tmp; //交换a[i]和a[min]
    }
}

循环不变式:在外层循环执行前,a[0…i-1]包含 a 中最小的 i 个数,且有序。

  • 初始时,i=0,a[0…-1] 为空,显然成立。
  • 每次执行完成后,a[0…i] 包含 a 中最小的 i+1 个数,且有序。即第一次执行完成后,a[0…0] 包含 a 最小的 1 个数,且有序。
  • 循环结束后,i=n-1,则 a[0…n-2]包含 a 最小的 n-1 个数,且已经有序。所以整个数组有序。
  • 4 冒泡排序

    冒泡排序时间复杂度跟选择排序相同。其思想就是进行 n-1 趟排序,每次都是把最小的数上浮,像鱼冒泡一样。最坏情况为 O(N^2)。代码如下:

    
    /**
     * 冒泡排序-经典版
     */
    void bubbleSort(int a[], int n)
    {
        int i, j, tmp;
        for (i = 0; i  n; i++) {
            for (j = n-1; j = i+1; j--) {
                if (a[j]  a[j-1])
                    tmp = a[j], a[j] = a[j-1], a[j-1] = tmp;
            }
        }
    }
    

    循环不变式:在循环开始迭代前,子数组 a[0…i-1] 包含了数组 a[0..n-1] 的 i-1 个最小值,且是排好序的。

    对冒泡排序的一个改进就是在每趟排序时判断是否发生交换,如果一次交换都没有发生,则数组已经有序,可以不用继续剩下的趟数直接退出。改进后代码如下:

    
    /**
     * 冒泡排序-优化版
     */
    void betterBubbleSort(int a[], int n)
    {
        int tmp, i, j;
        for (i = 0; i  n; i++) {
            int sorted = 1;
            for (j = n-1; j = i+1; j--) {
                if (a[j]  a[j-1]) {
                    tmp = a[j], a[j] = a[j-1], a[j-1] = tmp;
                    sorted = 0;
                }   
            }   
            if (sorted)
                return ;
        }   
    }
    

    5 计数排序

    假定数组为 a[0…n-1] ,数组中存在重复数字,数组中最大数字为k,建立两个辅助数组 b[] 和 c[],b[] 用于存储排序后的结果,c[] 用于存储临时值。时间复杂度为 O(N),适用于数字范围较小的数组。

    【45期】盘点那些必问的数据结构算法题之基础排序

    计数排序原理如上图所示,代码如下:

    
    /**
     * 计数排序
     */
    void countingSort(int a[], int n) 
    {
        int i, j;
        int *b = (int *)malloc(sizeof(int) * n);
        int k = maxOfIntArray(a, n); // 求数组最大元素
        int *c = (int *)malloc(sizeof(int) * (k+1));  //辅助数组
    
        for (i = 0; i = k; i++)
            c[i] = 0;
    
        for (j = 0; j  n; j++)
            c[a[j]] = c[a[j]] + 1; //c[i]包含等于i的元素个数
    
        for (i = 1; i = k; i++)
            c[i] = c[i] + c[i-1];  //c[i]包含小于等于i的元素个数
    
        for (j = n-1; j = 0; j--) {  // 赋值语句
            b[c[a[j]]-1] = a[j]; //结果存在b[0...n-1]中
            c[a[j]] = c[a[j]] - 1;
        }
    
        /*方便测试代码,这一步赋值不是必须的*/
        for (i = 0; i  n; i++) {
            a[i] = b[i];
        }
    
        free(b);
        free(c);
    }
    

    扩展:如果代码中的给数组 b[] 赋值语句 for (j=n-1; j=0; j–) 改为 for(j=0; j=n-1; j++),该代码仍然正确,只是排序不再稳定。

    6 归并排序

    归并排序通过分治算法,先排序好两个子数组,然后将两个子数组归并。时间复杂度为 O(NlgN)。

    代码如下:

    
    /*
     * 归并排序-递归
     * */
    void mergeSort(int a[], int l, int u) 
    {
        if (l  u) {
            int m = l + (u-l)/2;
            mergeSort(a, l, m);
            mergeSort(a, m + 1, u);
            merge(a, l, m, u);
        }
    }
    
    /**
     * 归并排序合并函数
     */
    void merge(int a[], int l, int m, int u) 
    {
        int n1 = m - l + 1;
        int n2 = u - m;
    
        int left[n1], right[n2];
        int i, j;
        for (i = 0; i  n1; i++) /* left holds a[l..m] */
            left[i] = a[l + i];
    
        for (j = 0; j  n2; j++) /* right holds a[m+1..u] */
            right[j] = a[m + 1 + j];
    
        i = j = 0;
        int k = l;
        while (i  n1 && j  n2) {
            if (left[i]  right[j])
                a[k++] = left[i++];
            else
                a[k++] = right[j++];
        }
        while (i  n1) /* left[] is not exhausted */
            a[k++] = left[i++];
        while (j  n2) /* right[] is not exhausted */
            a[k++] = right[j++];
    }
    

    扩展:归并排序的非递归实现怎么做?

    归并排序的非递归实现其实是最自然的方式,先两两合并,而后再四四合并等,就是从底向上的一个过程。

    代码如下:

    
    /**
     * 归并排序-非递归
     */
    void mergeSortIter(int a[], int n)
    {
        int i, s=2;
        while (s = n) {
            i = 0;
            while (i+s = n){
                merge(a, i, i+s/2-1, i+s-1);
                i += s;
            }
    
            //处理末尾残余部分
            merge(a, i, i+s/2-1, n-1);
            s*=2;
        }
        //最后再从头到尾处理一遍
        merge(a, 0, s/2-1, n-1);
    }
    

    7 基数排序、桶排序

    基数排序的思想是对数字每一位分别排序(注意这里必须是稳定排序,比如计数排序等,否则会导致结果错误),最后得到整体排序。

    假定对 N 个数字进行排序,如果数字有 d 位,每一位可能的最大值为 K,则每一位的稳定排序需要 O(N+K) 时间,总的需要 O(d(N+K)) 时间,当 d 为常数,K=O(N) 时,总的时间复杂度为O(N)。

    【45期】盘点那些必问的数据结构算法题之基础排序

    而桶排序则是在输入符合均匀分布时,可以以线性时间运行,桶排序的思想是把区间 [0,1) 划分成 N 个相同大小的子区间,将 N 个输入均匀分布到各个桶中,然后对各个桶的链表使用插入排序,最终依次列出所有桶的元素。

    【45期】盘点那些必问的数据结构算法题之基础排序

    这两种排序使用场景有限,代码就略过了,更详细可以参考《算法导论》的第8章。

    参考资料

    《算法导论》 https://www.cnblogs.com/liushang0419/archive/2011/09/19/2181476.html

    来源:juejin.im/post/5bacdd2b5188255c3f6be3c2

    最近五期

    与其在网上拼命找题?** 不如马上关注我们~**

    【45期】盘点那些必问的数据结构算法题之基础排序

    原文始发于微信公众号(Java面试题精选):

    本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

    本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

    原文链接:blog.ouyangsihai.cn >> 【45期】盘点那些必问的数据结构算法题之基础排序


     上一篇
    【43期】盘点那些必问的数据结构算法题之二叉树基础 【43期】盘点那些必问的数据结构算法题之二叉树基础
    点击上方“Java面试题精选”,关注公众号 面试刷图,查缺补漏 号外:****往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅。 0 概述在说二叉树前,先来看看什么是树。树中基本单位是结点,结点之间的链接,称为分支
    2021-04-05
    下一篇 
    【46期】盘点那些必问的数据结构算法题之快速排序 【46期】盘点那些必问的数据结构算法题之快速排序
    点击上方“Java面试题精选”,关注公众号 面试刷图,查缺补漏 号外:****往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅。 0 概述快速排序也是基于分治模式,类似归并排序那样,不同的是快速排序划分最后不需要m
    2021-04-05