Java排序算法面试题（附答案）

在java编程的时候，往往会遇到需要进行数据处理的程序，而在数据处理时，对数据进行查找是常规操作，当我们进行数据处理的时候，将数据有序的排列好是提高效率的办法，这个时候java排序算法就体现出它的作用了。下面整理了一些常考的java排序算法面试题，因为在面试java程序员岗位的时候，会对java排序算法进行考察，是属于java基础范畴的内容。

1、java初级排序算法都有什么？

答：java排序算法有冒泡排序、选择排序、插入排序、希尔排序算法，这些都是java初级的排序算法。

2、java冒泡排序算法的步骤是什么？

答：步骤如下：（1）比较相邻的元素。如果第一个比第二个大，就交换他们两个；（2）对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上；（3）针对所有的元素重复以上的步骤，除了最后一个；（4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3、选择排序的步骤是什么？

答：（1）在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；

（2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；（3）以此类推，直到所有元素均排序完毕。

4、初级java排序算法的原理？

答：冒泡排序：重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

选择排序：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

插入排序：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

希尔排序：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

5、希尔排序算法的实现代码？

答：public class shell_sort{

    public static void ShellSort(int[] arr){

        int n=arr.length;

        int gap=n/2;

        while(gap>0){

            for(int j=gap;j0;j++){

                int i=j;

                while(i

                    if(arr[i]

                        int temp=arr[i];

                        arr[i]=arr[i-gap];

                        arr[i-gap]=temp;

                        i+=1;

                    }

                    else

                        break;

                }   

            }

            gap=gap/2;

 

        }

    }

        public static void main(String[] args){

        int a[]={38,65,97,76,13,27,49};

        ShellSort(a);

        for(int n:a)

            System.out.print(n+",");

    }

 

}

6、分析一下常见的排序算法的稳定性是怎样的？

答：（1）冒泡排序：把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会交换的；如果两个相等的元素没有相邻，即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

（2）选择排序：选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。所以选择排序不是一个稳定的排序算法。

（3）插入排序：插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

（4）基数排序：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

7、在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数对个数为4，现在给定一数组，要求统计出该数组的逆序数对个数。

答：计算数列的逆序数对个数最简单的方便就最从前向后依次统计每个数字与它后面的数字是否能组成逆序数对。代码如下：

#include  

int main()  

{      

    const int MAXN = 8;  

    int a[MAXN] = {1, 7, 2, 9, 6, 4, 5, 3};  

      

    int nCount = 0;  

    int i, j;  

    for (i = 0; i < MAXN; i++)  

        for (j = i + 1; j < MAXN; j++)  

            if (a[i] > a[j])  

                nCount++;  

  

    printf("逆序数对为: %d\n", nCount);  

}  

运行结果为：

8、简要说明一下java排序的基本概念是什么？

 答：排序主要分为两类：内部排序和外部排序，java各种排序算法其实指的是内部排序算法。内部排序是基于内存的，整个排序过程都是在内存中完成的，而外部排序指的是由于数据量太大，内存不能完全容纳，排序的时候需要借助外存才能完成（常常是算计着某一部分已经计算过的数据移出内存让另一部分未被计算的数据进入内存）。

以上就是今天为大家整理的java排序算法面试题的内容，其实java排序算法的知识肯定远不止这些，除了这篇文章中介绍的冒泡排序、选择排序、插入排序和希尔排序外，还有堆排序、快速排序等算法排序，常见的有八种java排序算法，希望大家在更多的java培训课程中仔细学习所有排序算法的原理，从而真正的掌握java排序算法的使用。