算法回顾

算法回顾

[toc]

三日不弹,手生荆棘

回顾是非常好的学习方法,让自己想起OI的时光。

排序

冒泡排序 Bubble Sort

先来一个最简单的,冒泡排序。顾名思义,就像水底往上冒的气泡,离水面越近,水泡越来越大。

  1. 从第一位开始,将其和它的下一个进行比对,如果前一个大,则交换位置;然后到第二位,就变为第二位与第三位比对,以此类推,两两比对完成后,就能保证最后一位为整个序列的最大。
  2. 然后再从第一位进行相邻的两两比对,这一次比对到倒数第二位即可,因为最后一位已经是最大,无需再比,则完成后,倒数第二位为整个序列的次大。
  3. 每次两两比对交换的终点位前移一次,则此算法终止与最终位为第二位时。

冒泡排序

int[] array = {3, 5, 7, 4, 2, 1, 6};
for (int end = array.length - 1; end > 0; end--) {  // 两两比对的终点控制
    for (int index = 0; index < end; index++) {  // 当前位控制
        if (array[index] > array[index + 1]) {  // 当前位与其下一位进行比对
            int temp = array[index];
            array[index] = array[index + 1];
            array[index + 1] = temp;
        }
    }
}

插入排序 Insertion sort

这个原理应该是最简单的,即假定存在一个有序序列,将另一个数放入其中并保持最终的有序;在插入过程中为顺序扫描整个序列,当发现位置正确时进行插入。
例如手中有一副排好顺序的扑克,摸一张放里面,则需要挨个进行比较才能确定能放置的位置。

插入排序

所以当数据结构为链表时操作比较简单,而为数组时则稍微复杂一些。下面以数组为例。

  1. 将数组分为两部分,前半部分是已排好的有序数组,后半部分都是待插入的数字;开始时前半部分只有序列的第一位,其余后面都是待插入的部分。
  2. 从第二位开始,将第二位的前一位,即第一位与当前位相比,如果比当前位大,则此比较位向后移,然后一直往前找,直到找到比当前位小的,则说明当前位应该放在比较位的后面。
  3. 然后再从当前位的下一位开始,再进行插入。

插入排序

int[] array = {3, 5, 7, 4, 2, 1, 6};
for (int currPos = 1; currPos < array.length; currPos++) {  // 从第二位开始,选取数字进行插入
    int comparePos = currPos - 1;  // 比较位是从前一位开始
    int current = array[currPos];
    while (comparePos >= 0 && array[comparePos] > current) {  // 如果比较位比当前位大,则需要后移
        array[comparePos + 1] = array[comparePos];
        comparePos--;
    }
    array[comparePos + 1] = current;  // 所有比当前位大的都移动完毕,则将当前位放在比较位的后面
}

希尔排序 Shell sort

我认为希尔排序的思想是比较另类的,属于插入排序的一个变种。由于插入排序在插入新数时需要遍历整个序列,希尔排序针对这种情况做出了修改:将整个序列分为几部分分别进行插入排序,而希尔排序的分组比较有意思,并不是像切肉一样简单分为几个连续的部分,而是设定了一个小于数组长度的跨度d(d通常小于数组长度/2),每隔d长度的为一组。假设共有10个数,d为3的情况,分组即为{0,3,6,9},{1,4,7},{2,5,8}这样三组。这一步的优点一是,由于每个子序列变短了,虽然总的需要排序的个数不变,但移动次数减少;优点二是可以将较小的数尽量快的放到整个数组的前面;例如按上面的分组第一次排序后,下标为0,1,2的元素均为个分组中最小的。然后将d缩短,即子序列变短,再对每部分进行插入排序,直到d=1时,无需排序,则完成整个序列的排序。

希尔排序

  1. 设定初始跨度d=array.length/2,相隔相同跨度的为一组,进行插入排序。
  2. 缩小跨度d,d=d/2,再此进行分组与插入排序。
  3. d=1时结束。
int[] array = {6, 5, 3, 1, 8, 7, 2, 4};
int d = array.length;
while (d > 1) {  // 控制跨度
    d = d / 2;  // 每次跨度缩小一半
    for (int start = 0; start < d; start++) {  // 每个分组的起点
        for (int currPos = start + d; currPos < array.length; currPos = currPos + d) {  // 此处开始为通常的插入排序,只是由于跨度分组的不同,循环的步长会有不同。
            int comparePos = currPos - d;
            int current = array[currPos];
            while (comparePos >= 0 && array[comparePos] > current) {
                array[comparePos + d] = array[comparePos];
                comparePos = comparePos - d;
            }
            array[comparePos + d] = current;
        }
    }
}

归并排序 Merge sort

归并排序相对于上两个的思路不同,并不是遍历单条序列找最大或最小的思路,最主要的是递归思想。假定有两个有序序列,将其合并为一个有序序列,所需要做的就是不断取出两个序列中最小的,并将其中较小的放在新的序列中,则最后合并得到的序列仍然是有序的序列,这就是所谓归并。

归并排序

  1. 要归并排序一个序列,可以先将其分成两部分,分别进行排序,得到的就是两个有序序列,再按照如下步骤进行。
  2. 有两个指针分别指向两个有序序列的首位。
  3. 比较两个指针对应的大小,小的放入新序列,并且此指针向后移,再重复比较。
int[] array = {3, 5, 7, 4, 2, 1, 6};
mergeSort(array, 0, array.length - 1);  // 指定排序范围
public static void mergeSort(int[] arr, int start, int end) {
    if (start == end - 1) {  // 如果起始与终点相邻,则将两者进行比对
        if (arr[start] > arr[end]) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    } else if (start < end - 1) {  // 如果排序子集大于三个,则需要进行递归操作
        int mid = (start + end) / 2;  // 选取中间点
        mergeSort(arr, start, mid);  // 前半部分进行排序
        mergeSort(arr, mid + 1, end);  // 后半部分进行排序
        merge(arr, start, mid, end);  // 将排好序的两部分进行合并
    }
    // 这里的情形是起始等于终点,即只有一个数,所以无需排序
}
public static void merge(int[] arr, int start, int mid, int end) {
    int[] newArr = new int[end - start + 1];  // 建立一个新数组用于放置新的合并结果
    int pos1 = start;  // 前半部分的指针
    int pos2 = mid + 1;  // 后半部分的指针
    int newArrPos = 0;  // 新数组的指针
    while (pos1 <= mid && pos2 <= end) {  //控制两个指针不超界
        if (arr[pos1] < arr[pos2]) {  // 取两个指针对应较小的数,放入新数组,对应指针后移
            newArr[newArrPos] = arr[pos1];
            pos1++;
        } else {
            newArr[newArrPos] = arr[pos2];
            pos2++;
        }
        newArrPos++;
    }
    // 当某半部分的指针已经到达末尾时,另半部分可能还有剩余,所以需要全部移入新的数组
    while (pos1 <= mid) {
        newArr[newArrPos] = arr[pos1];
        pos1++;
        newArrPos++;
    }
    while (pos2 <= end) {
        newArr[newArrPos] = arr[pos2];
        pos2++;
        newArrPos++;
    }
    System.arraycopy(newArr, 0, arr, start, newArr.length);  // 将新的合并好的数组替换原有的未合并部分
}

堆排序 Heap Sort

到这里,数据结构发生了一些变更,由数组转换到树结构。

发表评论