分类 算法分析 下的文章

基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。通常用3路快排。
Sorting_quicksort


- 阅读剩余部分 -

归并排序(英语:Merge sort,或mergesort),是建立在归并操作上的一种有效的排序算法,效率為 O(nlog n)(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

Merge-sort-example

- 阅读剩余部分 -

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

Sorting_shellsort

- 阅读剩余部分 -

插入排序,先将要插入前边的元素复制一份,依次和前边的对比,如果前边的大于自己就把自己当前位置的值设置为前边的。直到前边的值小于自己当前位置的值为止,或者当前的索引位置为0。算法复杂度为O(log(N^2)),在近乎有序的数组中效率非常高。

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        // 寻找元素arr[i]合适的插入位置
        int e = arr[i];
        int j = i;
        for (; j > 0 && arr[j - 1] > arr[j]; j--)
            arr[j] = arr[j - 1];
        arr[j] = e;
    }
}

查找一维数组里面某一个元素的索引值,找不到则返回-1.

static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midValue = arr[mid];
        if (midValue < key) {
            low = mid + 1;
        } else if (midValue > key) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}