整理好的java面试八大常用算法

原创不易，如果有转载需要的话，请在首行附上本文地址，谢谢。

文中整理了八大常见的排序算法，冒泡排序、选择排序、快速排序、插入排序、堆排序、希尔排序、归并排序和基数排序的简单思想，每种算法配有动图分析和相应的java代码，为了方便有缘人进一步地了解各种算法，本文也附上了相应算法详细介绍的链接地址。在本文的文末，对这八种排序算法的稳定性，时间复杂度和排序算法的大致选择做了一个简单的总结。（本文的动图转载于https://blog.csdn.net/yushiyi6453/article/details/76407640）

1、冒泡排序

**简单思想：**冒泡排序从小到大排序：一开始交换的区间为0_{N-1，将第1个数和第2个数进行比较，前面大于后面，交换两个数，否则不交换。再比较第2个数和第三个数，前面大于后面，交换两个数否则不交换。依次进行，最大的数会放在数组最后的位置。然后将范围变为0}N-2，数组第二大的数会放在数组倒数第二的位置。依次进行整个交换过程，最后范围只剩一个数时数组即为有序。

动图参考：

具体详解参考：https://www.cnblogs.com/sincoolvip/p/5449202.html

实现代码：

    public void bubbleSort(int []a){
        int len=a.length;
        for(int i=0;i<len-1;i++){
            for (int j = 0; j < len - 1 - i; j++) {
                if(a[j]>a[j+1]){
                    int temp;
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }

        }
    }

2、选择排序

选择排序从小到大排序：一开始从0_{n-1区间上选择一个最小值，将其放在位置0上，然后在1}n-1范围上选取最小值放在位置1上。重复过程直到剩下最后一个元素，数组即为有序。

动图参考：

具体详解参考：https://www.cnblogs.com/shen-hua/p/5424059.html

实现代码

    public void selectSort(int []a){

        int len=a.length;
        int value;int position;
        for (int i=0;i<len-1;i++){
            value=a[i];
            position=i;
            for(int j=i+1;j<len;j++){
                if(a[j]<value){
                    value=a[j];
                    position=j;
                }
            }
            a[position]=a[i];
            a[i]=value;
        }
    }

3、快速排序

快速排序从小到大排序：在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边，大于此数的放在右边，再对数组两边递归调用快速排序，重复这个过程。

动图参考：

具体详解参考：快速排序（java实现）_大数据指北的博客-CSDN博客

实现代码:

    public void quickSort(int []a,int low ,int high)
    {
        if(low>high){
            return;
        }
         int i=low;
         int j=high;
         int temp=a[i];
         while(i<j){
             while(temp<=a[j]&&i<j){
                    j--;
                }
             while(temp>=a[i]&&i<j){
                    i++;
                }
              if(i<j) {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
            }
            a[low]=a[i];
            a[i]=temp;
            quickSort(a,low,i-1);
            quickSort(a,i+1,high);
    }

4、插入排序

插入排序从小到大排序：首先位置1上的数和位置0上的数进行比较，如果位置1上的数大于位置0上的数，将位置0上的数向后移一位，将1插入到0位置，否则不处理。位置k上的数和之前的数依次进行比较，如果位置K上的数更大，将之前的数向后移位，最后将位置k上的数插入不满足条件点，反之不处理。

具体详解参考：https://www.cnblogs.com/yver/p/5987109.html

动图参考：

实现代码：

    public void  insertSort(int []a){
        int len=a.length;
        for (int i = 1; i < len; i++) {
            int insertNum=a[i];
            int j=i;
            while(j>0&&a[j-1]>insertNum){
                a[j]=a[j-1];
                j--;
            }
            a[j]=insertNum;
        }
    }

5、堆排序

堆排序从小到大排序：首先将数组元素建成大小为n的大顶堆，堆顶（数组第一个元素）是所有元素中的最大值，将堆顶元素和数组最后一个元素进行交换，再将除了最后一个数的n-1个元素建立成大顶堆，再将最大元素和数组倒数第二个元素进行交换，重复直至堆大小减为1。

动图参考：