排序

9 篇

数据结构与算法(十三)——堆排序

定义

我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小元素的优先队列,然后再重复调用删除最小元素的操作来将它们按顺序删去。基于堆的优先队列的这种操作就是堆排序。

堆排序可以分为两个阶段。在堆的构造阶段中,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按递减顺序取出所有元素并得到排序结果。

继续阅读

数据结构与算法(十二)——堆

定义

数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆数组中,每个元素都要保证大于等于另两个特定位置的元素。相应地,这些位置的元素又至少要大于等于数组中的另两个元素,以此类推。

  • 当一棵二叉树的每个结点都大于等于它的两个子结点时,它被称为堆有序。
  • 根结点是堆有序的二叉树中最大结点。

继续阅读

数据结构与算法(十一)——优先队列

定义

许多应用程序都需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。很多情况下我们会收集一些元素,处理当前键值最大的元素,然后再收集更多的元素,再处理当前键值最大的元素。

在这种情况下,一个合适的数据结构应该支持两种操作:删除最大元素和插入元素。这种数据类型叫做优先队列。

继续阅读

数据结构与算法(十)——快速排序

定义

一种分治算法,将一个数组分成两个数组,两部分独立地排序。弥补了归并排序需要额外空间的缺点。

归并排序将数组分成两个子数组分别排序,并将有序的子数组归并以将整个数组排序。而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。

继续阅读

数据结构与算法(八)——希尔排序

定义

一种基于插入排序的快速排序算法。

对于大规模乱序数组插入排序很慢。因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插人排序,交换不相邻的元素以对数组的局部进行排序,并最终用插人排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说,一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。

继续阅读

数据结构与算法(七)——插入排序

定义

将一个元素插入到已经排好序的有序数据中。插入位置后方的元素都要向右移动一位。

代码

    public static void sort(Object[] a, Comparator comparator) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j > 0 && less(a[j], a[j-1], comparator); j--) {
                exch(a, j, j-1);
            }
        }
    }

继续阅读

数据结构与算法(六)——选择排序

定义

首先,找到数组中最小的那个元素,其次将它和数组的第一个元素交换位置。再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。

代码

    public static void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = i+1; j < n; j++) {
                if (less(a[j], a[min])) min = j;
            }
            exch(a, i, min);
        }
    }

继续阅读