排序

• 用java写一个冒泡排序？

考察点：冒泡排序
参考回答：

import
java.util.Comparator;
 /**
  * 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)
  */
 public interface Sorter {
    /**
     *
  */
 public interface Sorter {
    /**
     * 排序
     * @param list 待排序的数组
     */
    public <T extends Comparable<T>> void sort(T[] list);
    /**
     * 排序
     * @param list 待排序的数组
     * @param comp 比较两个对象的比较器
     */
    public <T> void sort(T[] list, Comparator<T> comp);
 }
 import java.util.Comparator;
 /**
  * 冒泡排序
  *
  */
 public class BubbleSorter implements Sorter {
     @Override
     public <T extends Comparable<T>> void sort(T[]
list) {
         boolean swapped = true;
         for (int i = 1, len = list.length; i
< len && swapped; ++i) {
             swapped =
false;
             for (int j =
0; j < len - i; ++j) {
                 
if (list[j].compareTo(list[j + 1]) > 0) {
                     
T temp = list[j];
                     
list[j] = list[j + 1];
                     
list[j + 1] = temp;
                     
swapped = true;
                 
}
             }
         }
     }
     @Override
     public <T> void sort(T[] list, Comparator<T>
comp) {
         boolean swapped = true;
         for (int i = 1, len = list.length; i
< len && swapped; ++i) {
             swapped =
false;
             for (int j =
0; j < len - i; ++j) {
                 
if (comp.compare(list[j], list[j + 1]) > 0) {
                     
T temp = list[j];
                     
list[j] = list[j + 1];
                     
list[j + 1] = temp;
                     
swapped = true;
                 
}
             }
         }

• 介绍一下，排序都有哪几种方法？请列举出来。

考察点：排序
参考回答：

排序的方法有：插入排序（直接插入排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序）， 归并排序，分配排序（箱排序、基数排序） 快速排序的伪代码。 / /使用快速排序方法对a[ 0 :n- 1 ]排序 从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点 把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点 递归地使用快速排序方法对left 进行排序 递归地使用快速排序方法对right 进行排序 所得结果为l e f t + m i d d l e + r i g h t

• 介绍一下，归并排序的原理是什么？

考察点：归并排序
参考回答：

（1）归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

（2）首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

（3）解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

• 介绍一下，堆排序的原理是什么？

考察点：堆排序
参考回答：

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

（1）最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

（2）创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆。

（3）堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

image

• 谈一谈，如何得到一个数据流中的中位数？

考察点：排序
参考回答：

数据是从一个数据流中读出来的，数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据，当有新的数据流中读出来时，这些数据就插入到数据容器中。

数组是最简单的容器。如果数组没有排序，可以用 Partition 函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度是 O(1)和 O(n)。

我们还可以往数组里插入新数据时让数组保持排序，这是由于可能要移动 O(n)个数，因此需要 O(n)时间才能完成插入操作。在已经排好序的数组中找出中位数是一个简单的操作，只需要 O(1)时间即可完成。

排序的链表时另外一个选择。我们需要 O(n)时间才能在链表中找到合适的位置插入新的数据。如果定义两个指针指向链表的中间结点（如果链表的结点数目是奇数，那么这两个指针指向同一个结点），那么可以在 O(1)时间得出中位数。此时时间效率与及基于排序的数组的时间效率一样。

如果能够保证数据容器左边的数据都小于右边的数据，这样即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个容器中找出最大数？用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据。同样，也可以快速从最小堆中找出最小数。

因此可以用如下思路来解决这个问题：用一个最大堆实现左边的数据容器，用最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是 O(logn)。由于只需 O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间效率是 O(1)。

• 你知道哪些排序算法，这些算法的时间复杂度分别是多少，解释一下快排？

考察点：快排
参考回答：

image

快排：快速排序有两个方向，左边的i下标一直往右走（当条件a[i] <= a[center_index]时），其中center_index是中枢元素的数组下标，一般取为数组第0个元素。

而右边的j下标一直往左走（当a[j] > a[center_index]时）。

如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。