【Java面试题】常见算法总结

常见算法

  • 1、7种常见排序算法
    • 1.1、冒泡排序
    • 1.2、简单选择排序
    • 1.3、直接插入排序
    • 1.4、希尔排序
    • 1.5、归并排序
    • 1.6、快速排序
    • 1.7、堆排序

1、7种常见排序算法

7种常见排序算法的时间复杂度辅助空间以及稳定性对照表。

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
简单选择排序 O(n^2) O(n^2) O()n^2 O(1) 稳定
直接插入排序 O(n^2) O(n) O()n^2 O(1) 稳定
希尔排序 O(nlogn)~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~O(n) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定

1.1、冒泡排序

原理: 最简单的一种排序算法。假设长度为n的数组arr,要按照从小到大的排序,则冒泡排序的具体过程可以描述为:首先从数组的第一个元素开始到数组的最后一个元素为止,对数组中相邻的两个元素进行比较,如果相邻两个元素中左边的元素大于右边的元素,则交换两个元素的位置,此时数组最右端的元素即为该数组中所有元素的最大值。接着对该数组剩下的(n-1)个元素进行冒泡排序,直到整个数组有序排列。

时间复杂度: O(n^2)。

动态直观图:
【Java面试题】常见算法总结_第1张图片

代码实现:

import java.util.Arrays;

public class BubbleSort {
     
    public static void main(String[] args) {
     
        int[] arr = new int[]{
     3,78,34,50,89,1,45,7};
        System.out.println("排序之前:" + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序之后:" + Arrays.toString(arr));
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
     
        for(int i = arr.length - 1; i >= 0; i--){
     
            for(int j = 0; j < i; j++){
     
                if(arr[j] > arr[j + 1]){
     
                    int tem = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tem;
                }
            }
        }
    }
}

结果:

排序之前:[3, 78, 34, 50, 89, 1, 45, 7]
排序之后:[1, 3, 7, 34, 45, 50, 78, 89]

1.2、简单选择排序

**原理:**在严蔚敏版本的《数据结构》中对选择排序的基本描述为:每一轮在n-i+1(i1,2,…,n-1)个记录中选择关键字最小的记录作为有序序列中第 i个记录。假设长度为n的数组arr,要按照从小到大排序,那么先从n个数字中找到最小值min1,如果最小值min1的位置不在数组的最左端(也就是min1不等于arr[0]),则将最小值arr[0] = min1,接着在剩下的(n-1)个数字中找到最小值min2,如果最小值min2不等于arr[1],那么则arr[1] = min2,依次类推,知道数组arr有序排列。

时间复杂度: O(n^2)。

直观图解:
【Java面试题】常见算法总结_第2张图片
代码实现:

import java.util.Arrays;

public class SelectSort {
     
    public static void main(String[] args) {
     
        int[] arr = new int[]{
     3,78,34,50,89,1,45,7};
        System.out.println("排序之前:" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序之后:" + Arrays.toString(arr));
    }

    /**
     * 简单选择排序
     * @param arr
     */
    static void selectSort(int[] arr){
     
        for(int i=0;i<arr.length; i++){
     
            int index = i;
            for(int j=i+1;j<arr.length;j++){
     
                if(arr[index] > arr[j]){
     
                    index = j;
                }
            }

            if(index == i){
     
                continue;
            } else {
     
                int tem = arr[index];
                arr[index] = arr[i];
                arr[i] = tem;
            }
        }
    }
    
}

结果:

排序之前:[3, 78, 34, 50, 89, 1, 45, 7]
排序之后:[1, 3, 7, 34, 45, 50, 78, 89]

1.3、直接插入排序

原理: 插入排序的基本思想就是将无序序列插入到有序序列中。例如:将数组arr=[4,2,8,0,5,1]排序,可以将4看做是一个有序序列(图中用蓝色标出),将[2,8,0,5,1]看做是一个无序序列,无序序列中2比4小,于是将2插入到4的左边,于是将2插入到4的左边,此时有序序列变成了[2,4],无序序列变成了[8,0,5,1]。无序序列中8比4大,所以将8插入到4的右边,有序序列变成了[2,4,8],无序序列变成了[0,5,1]。依次类推最终数组按照从小到大的排序。

时间复杂度: O(n^2)。

直观图:
【Java面试题】常见算法总结_第3张图片
【Java面试题】常见算法总结_第4张图片
代码实现:

import java.util.Arrays;

public class InsertSort {
     
    public static void main(String[] args) {
     
        int[] arr = new int[]{
     4,2,8,0,5,1};
        System.out.println("排序之前:" + Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序之后:" + Arrays.toString(arr));
    }

    static void insertSort(int[] arr){
     
        for(int i=1;i<arr.length;i++){
     
            //如果数组长度小于1直接返回
            if(arr.length<2)
                return;
            
            //就是j之前的元素都看做是一个有序序列
            for(int j=i;j>0;j--){
     
                if(arr[j] < arr[j-1]){
     
                    int tem = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tem;
                }
            }

        }
    }
}

结果:

排序之前:[4, 2, 8, 0, 5, 1]
排序之后:[0, 1, 2, 4, 5, 8]

1.4、希尔排序

待续……

1.5、归并排序

待续……

1.6、快速排序

原理: 快速怕排序的基本思想是:通过一次排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

实际上: 快速排序 = 冒泡 + 分治 + 递归

一趟快速排序的具体过程可描述为: 从待排序列中任意取出一个记录(通常选取第一个记录)作为基准值,然后将记录中比它小的记录都安置在它的位置之前,将记录中关键字比它大的记录都安置在它的位置之后。这样,以该基准值为分界线,将待排序序列分成两个子序列。

一趟快速排序的具体做法为: 设置两个指针low和high分别指向待排序列的开始和结尾,记录下基准值baseval(待排序列的第一个记录),然后先从high所指的位置向前搜索直到找到一个小于baseval的记录并互相交换,接着从low所指向的位置向后搜索直到找到一个大于baseval的记录并互相交换,重复这两个步骤直到low=high为止。

时间复杂度: O(nlogn)。

直观图:
【Java面试题】常见算法总结_第5张图片
【Java面试题】常见算法总结_第6张图片
【Java面试题】常见算法总结_第7张图片
代码实现:

import java.util.Arrays;

public class QuickSort {
     
    public static void main(String[] args) {
     
        int[] arr = new int[]{
     4,2,8,0,5,1};
        System.out.println("排序之前:" + Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println("排序之后:" + Arrays.toString(arr));
    }

    /**
     * 快速排序
     * @param arr 数组
     * @param left 起始位置0
     * @param right 末尾位置 (arr.length-1)
     */
    static void quickSort(int arr[],int left,int right){
     
        //左右两指针相与直接返回
        if(left >= right){
     
            return;
        }
        //为了方便起见,我们将i和j分别代表左右指针
        int i = left;
        int j = right;

        //获取基准数(一般是以第一个数为基准数)
        int baseval = arr[left];
        while (i<j){
     
            //从右向左找比基准数小的记录,
            while (i<j && arr[j] >= baseval){
     
                //如果不小于,j指针就继续左移
                j--;
            }

            //从左向右找比基准数大的记录,
            while (i<j && arr[i] <= baseval){
     
                //如果不大于,i指针就继续右移
                i++;
            }

            //当j指针找打了比基准数小的值,当i指针找到比基准值大的值,交换两者的位置
            int tem = arr[i];
            arr[i] = arr[j];
            arr[j] = tem;
        }

        //当两指针相遇时,也就是i=j了,将此位置的值与基准值baseval交换
        arr[left] = arr[i];
        arr[i] = baseval;

        //递归排序左右两边的序列
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
}

执行结果:

排序之前:[4, 2, 8, 0, 5, 1]
排序之后:[0, 1, 2, 4, 5, 8]

1.7、堆排序

待续……

你可能感兴趣的