java排序和查找算法

一、排序算法

/**
 * 给定数组：int data[] = {9,2,7,19,100,97,63,208,55,78}
 * 一、直接插入排序(内部排序、O(n2)、稳定),
 * 复杂度：最好 - 最坏 - 平均 O(n) - O(n^2) - O(n^2) 
 * 原理：从待排序的数中选出一个来，插入到前面的合适位置。
 */
public static void insertSort() {
    int tmp, j = 0;
    for (int k = 0; k < data.length; k++) {//-----1-----
        tmp = data[k];//暂存
        j = k - 1;
        while (j >= 0 && tmp < data[j]) {//-----2-----
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = tmp;//------3-------
    }
}
/**
 * 二、选择排序（O(n2)、不稳定）最好O(n^2) - 最坏O(n^2) - 平均O(n^2)
 * 与直接插入排序正好相反，选择排序是从待排序的数中选出最小的放在已经排好的后面，这个算法选数耗时。
 */
public static void selectSort() {
    int i, j, k, tmp = 0;
    for (i = 0; i < data.length - 1; i++) {
        k = i;
        for (j = i + 1; j < data.length; j++)
            if (data[j] < data[k])
                k = j;
        if (k != i) {
            tmp = data[i];
            data[i] = data[k];
            data[k] = tmp;
        }
    }
}
/**
 * 三、快速排序（O(nlogn)、不稳定），最好O(nlgn) - 最坏O(n^2) - 平均O(nlgn)
 * 快速排序简称快排，是一种比较快的排序，适合基本无序的数据，
 * 为什么这么说呢？下面我说下快排的思路：
 * 设置两个指针：i和j，分别指向第一个和最后一个，i像后移动，j向前移动，
 * 选第一个数为标准（一般这样做，当然快排的关键就是这个“标准”的选取），
 * 从后面开始，找到第一个比标准小的数，互换位置，然后再从前面，
 * 找到第一个比标准大的数，互换位置，第一趟的结果就是标准左边的都小于标准，
 * 右边的都大于标准（但不一定有序），分成两拨后，继续递归的使用上述方法，最终有序！
 */

static class QuickSort {

    public int data[];

    private int partition(int array[], int low, int high) {
        int key = array[low];
        while (low < high) {
            while (low < high && array[high] >= key)
                high--;
            array[low] = array[high];
            while (low < high && array[low] <= key)
                low++;
            array[high] = array[low];
        }
        array[low] = key;
        return low;
    }

    public int[] sort(int low, int high) {
        if (low < high) {
            int result = partition(data, low, high);
            sort(low, result - 1);
            sort(result + 1, high);
        }
        return data;
    }
}
/**
 * 四、冒泡排序（稳定、基本有序可达O(n)，最坏情况为O(n2)）
 * 最好 - 最坏 - 平均 O(n) - O(n^2) - O(n^2) 
 * 冒泡排序是一种很简单，不论是理解还是时间起来都比较容易的一种排序算法，
 * 思路简单：小的数一点一点向前起泡，最终有序。
 * 相邻两个元素比较大小进行交换，一趟冒泡后会有一个元素到达最终位置
 */

public static void bubbleSort() {
    int i, j, tmp = 0;
    boolean flag;
    for (i = 0; i < data.length - 1; i++) {
        flag = false;
        for (j = data.length - 1; j > i; j--) {
            if (data[j] < data[j - 1]) {
                tmp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = tmp;
            }
            if (flag == false) {
                return;
            }
        }
    }
}
/**
 * 五、希尔排序（不稳定）
 * 最好O(n) - 最坏O(n^s 1<s<2) - 平均O(n^1.3)
 * 按步长进行分组，组内直接插入，缩小增量再次进行此步骤，增量为1时相当于一次直接插入。
 */

public void shellSort(int[] a) {
    if (null == a || a.length < 2) {
        return;
    }
    for (int d = a.length/2; d > 0; d/=2) {
        for (int i = d; i < a.length; i++) {
        // 内部直接插入
            int temp = a[i];
            int j = i - d;
            while (j >= 0 && temp < a[j]) {
                a[j+d] = a[j];
                j -= d;
            }
            a[j+d] = temp;
        }   
    }
}

/**
 * 六、归并排序（稳定）
 * 最好O(nlgn) - 最坏O(nlgn) - 平均O(nlgn)
 * 两个有序序列的合并，方法：分治 + 递归
 */

public void mergeSort(int[] a, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        //左边
        mergeSort(a, low, mid);
        //右边
        mergeSort(a, mid + 1, high);
        //有序序列归并
        merge(a, low, mid, high);
    }
}

private void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    // 左指针
    int i = low;
    // 右指针
    int j = mid + 1;
    // 临时数组指针
    int k = 0;

    while (i <= mid && j <= high) {
        if (a[i] < a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }

    //左边剩余
    while (i <= mid) {
        temp[k++] = a[i++];
    }

    //右边剩余
    while (j <= high) {
        temp[k++] = a[j++];
    }

    // 倒出
    for (int t = 0; t < temp.length; t++) {
        a[t + low] = temp[t]; 
    }
}

/**
 * 七、堆排序（稳定）
 * O(nlogn) [平均 - 最好 - 最坏]
 * 利用堆的特性
 */

public void heapSort(int[] a) {
    if (null == a || a.length < 2) {
        return;
    }
    buildMaxHeap(a);

    for (int i = a.length - 1; i >= 0; i--) {
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        adjustHeap(a, i, 0);
    }
}

// 建堆
private void buildMaxHeap(int[] a) {
    for (int i = a.length/2; i >= 0; i--) {
        adjustHeap(a, a.length, i);
    }
}

// 调整堆
private void adjustHeap(int[] a, int size, int parent) {
    int left = 2 * parent + 1;
    int right = 2 * parent + 2;
    int largest = parent;

    if (left < size && a[left] > a[largest]) {
        largest = left;
    }

    if (right < size && a[right] > a[largest]) {
        largest = right;
    }

    if (parent != largest) {
        int temp = a[parent];
        a[parent] = a[largest];
        a[largest] = temp;
        adjustHeap(a, size, largest);
    }
}

二、查找算法

/**
 * 典型的二分查找
 * 对于二分查找算法要求, 查找前的数据必须是已经排好序的,
 * 然后得到数组的开始位置start和结束位置end,
 * 取中间位置mid的数据a[mid]跟待查找数据key进行比较,
 * 若 a[mid] > key, 则取end = mid - 1;
 * 若 a[mid] < key, 则取start = mid + 1;
 * 若 a[mid] = key 则直接返回当前mid为查找到的位置.
 * 依次遍历直到找到数据或者最终没有该条数据.
 */

//已经排好序的数组
public static int binarySearch(int[] nums, int key) {
    int start = 0;
    int end = nums.length - 1;
    int mid = -1;
    while (start <= end) {
        mid = (start + end) / 2;
        if (nums[mid] == key) {
            return mid;//已经查到返回！
        } else if (nums[mid] > key) {
            end = mid - 1;
        } else if (nums[mid] < key) {
            start = mid + 1;
        }
    }
    return -1;
}
//排序算法

/**
 * 务必注意: 以下所有的排序算法都是从1开始, 而不是从0开始, 有的排序算法会把0位置当作监视哨
 * 排序之前先写一个交换方法后面会用到
 */
private static void swap(int[] a, int i, int j) {
    a[i] ^= a[j];
    a[j] ^= a[i];
    a[i] ^= a[j];
}

//插入排序

/**
 * 插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。
 * 第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i] 又是排好序的序列。
 * 要达到这个目的，我们可以用顺序比较的方法。
 * 首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；
 * 否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，
 * 直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
 * 图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入
 * 稳定，时间复杂度 O(n^2)
 */
public static void insertSort(int[] a) {//a0为监视哨位置,不作为数据存储
    int len = a.length;
    for (int i = 2; i < len; i++) {
        if (a[i - 1] > a[i]) {
            a[0] = a[i];
            a[i] = a[i - 1];
            int j = 0;
            for (j = i - 2; a[j] > a[0]; j--) {
                a[j + 1] = a[j];
            }
            a[j + 1] = a[0];
        }
    }
}
//选择排序

/**
 * 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，
 * 第i遍处理是将L[i..n]中最小者与L[i]交换位置。
 * 这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
 * 不稳定, 时间复杂度 O(n^2)
 */

public static void selectSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int j = selectMinKey(a, i); //从i开始a.length中找到最小的位置
        if (i != j) {
            swap(a, i, j);
        }
    }
}

// 查找从i开始到a.length中最小的位置
private static int selectMinKey(int[] a, int i) {
    int key = i;
    for (int j = i + 1; j < a.length; j++) {
        if (a[j] < a[key]) {
            key = j;
        }
    }
    return key;
}

//冒泡排序

/**
 * 冒泡排序方法是最简单的排序方法。
 * 这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。
 * 在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。
 * 所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。
 * 如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。
 * 显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。
 * 在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。
 * 一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
 * 稳定，时间复杂度 O(n^2)
 */
//冒泡排序
public static void bubbleSort(int[] a) {
    int len = a.length;
    for (int i = 1; i < len - 1; i++) {
        for (int j = i; j < len - i; j++) {
            if (a[j + 1] < a[j]) {
                swap(a, j + 1, j);
            }
        }
    }
}

//快速排序

/**
 * 不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n^2)
 * <p>
 * 快速排序是对冒泡排序的一种本质改进。
 * 它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。
 * 在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。
 * 快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。
 * 然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
 */

//快速排序
public static void quickSort(int[] a, int low, int high) {
    //递归快速排序
    int pivotLoc = 0;//中心点
    if (low < high) {
        pivotLoc = partitionLoc(a, low, high);
        quickSort(a, low, pivotLoc - 1);
        quickSort(a, pivotLoc + 1, high);
    }
}

//获取到a的下标 low ~ high 中, a[low]的应该放的位置, 即左边的数 < a[low] 右边的数 > a[low]
private static int partitionLoc(int[] a, int low, int high) {
    a[0] = a[low];
    while (low < high) {
        while (low < high && a[high] >= a[0]) {
            high--;
        }
        a[low] = a[high];
        while (low < high && a[low] <= a[0]) {
            low++;
        }
        a[high] = a[low];
    }
    a[low] = a[0];
    return low;
}