每月归档: 2018年6月

6 篇

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

定义

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

代码

    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);
        }
    }

继续阅读

数据结构与算法(一)——二分查找

定义

接受一个整数键和一个已经有序的int数组作为参数。如果该键存在于数组中则返回它的索引,否则返回-1。

将数组的中间键和被查找的键比较,如果被查找的键等于中间键,则返回中间键的索引;如果被查找的键小于中间键,则在左半部分继续查找;如果被查找的键大于中间键,则在右半部分查找。直到找到或者范围为空。

继续阅读