常见十四种的Java算法

一、简单列出常见的Java中14种算法

二、具体介绍

1、二分查找法

（1）算法原理：

/**
 * 二分查找
 * @param srcArray 源数组
 * @param des 目标元素
 * @return 如果找到则返回索引位置，找不到则返回-1
 */
public static int binarySearch(int[] srcArray, int des) {
    //定义初始最小、最大索引
    int start = 0;
    int end = srcArray.length - 1;
    //确保不会出现重复查找，越界
    while (start <= end) {
        //计算出中间索引值  >>> 逻辑右移 也就是 int middle = (end + start)/2
        int middle = (end + start)>>>1 ;//防止溢出

        if (des == srcArray[middle]) {
            return middle;
            //判断下限
        } else if (des < srcArray[middle]) {
            end = middle - 1;
            //判断上限
        } else {
            start = middle + 1;
        }
    }
    //若没有，则返回-1
    return -1;
}

2、冒泡排序算法

（1）算法原理：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。 
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 
针对所有的元素重复以上的步骤，除了最后一个。 
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 

（2）代码示例：

public static void bubbleSort(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

public static void bubbleSort2(int[] a, int n) {
    int i, j;
    for (i = 0; i < n; i++) {//表示 n 次排序过程。
        for (j = 1; j < n - i; j++) {
            if (a[j - 1] > a[j]) {//前面的数字大于后面的数字就交换
                //交换 a[j-1]和 a[j]
                int temp;
                temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
            }
        }
    }
}

3、插入排序算法

（1）概念：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

（2）一个通俗的比喻：

插入排序就类似于斗地主时，整理扑克牌的情况。第一次摸牌时，左收是空的，之后每次摸牌插入到左手的牌时，都会将这张牌和左手中已经排好序的牌，从右到左比较，确认这张牌该放的位置。

public static void insertionSort(int arr[]) {
    for (int i = 1; i < arr.length; i++) {
        //插入的数
        int insertVal = arr[i];
        //被插入的位置(准备和前一个数比较)
        int index = i - 1;
        //如果插入的数比被插入的数小
        while (index >= 0 && insertVal < arr[index]) {
            //将把 arr[index] 向后移动
            arr[index + 1] = arr[index];
            //让 index 向前移动
            index--;
        }
        //把插入的数放入合适位置
        arr[index + 1] = insertVal;
    }
}

4、快速排序算法

（1）概念：快速排序是指通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。

（2）快速排序的的过程简图：

选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。

—— 图片来源于网络

（3）代码示例： 

/**
 * 快速排序
 *
 * @param arr   需要排序的数组
 * @param start 数组的最小索引： 0
 * @param end   数组的最大索引： arr.length - 1
 * @return 排序好的数组
 */
public static int[] quickSort(int arr[], int start, int end) {
    int pivot = arr[start];
    int i = start;
    int j = end;
    while (i < j) {
        while ((i < j) && (arr[j] > pivot)) {
            j--;
        }
        while ((i < j) && (arr[i] < pivot)) {
            i++;
        }
        if ((arr[i] == arr[j]) && (i < j)) {
            i++;
        } else {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    if (i - 1 > start) arr = quickSort(arr, start, i - 1);
    if (j + 1 < end) arr = quickSort(arr, j + 1, end);
    return (arr);
}

/**
 * 快速排序（无返回值）
 * @param a 需要排序的数组
 * @param low 数组的最小索引： 0
 * @param high 数组的最大索引： arr.length - 1
 */
public static void quickSort2(int[] a, int low, int high) {
    int start = low;
    int end = high;
    int key = a[low];
    while (end > start) {
        //从后往前比较
        while (end > start && a[end] >= key)
            //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
            end--;
        if (a[end] <= key) {
            int temp = a[end];
            a[end] = a[start];
            a[start] = temp;
        }
        //从前往后比较
        while (end > start && a[start] <= key)
            //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
            start++;
        if (a[start] >= key) {
            int temp = a[start];
            a[start] = a[end];
            a[end] = temp;
        }
        //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
    }
    //递归
    if (start > low) quickSort2(a, low, start - 1);//左边序列。第一个索引位置到关键值索引-1
    if (end < high) quickSort2(a, end + 1, high);//右边序列。从关键值索引+1 到最后一个
}

5、希尔排序算法

（1）基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

（2）代码示例：

/**
 * 希尔排序
 * @param a 
 */
private static void shellSort(int[] a) {
    int dk = a.length / 2;
    while (dk >= 1) {
        //类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了
        for (int i = dk; i < a.length; i++) {
            if (a[i] < a[i - dk]) {
                int j;
                int x = a[i];//x 为待插入元素
                a[i] = a[i - dk];
                for (j = i - dk; j >= 0 && x < a[j]; j = j - dk) {
                    //通过循环，逐个后移一位找到要插入的位置。
                    a[j + dk] = a[j];
                }
                a[j + dk] = x;//插入
            }
        }
        dk = dk / 2;
    }
}

6、归并排序算法

（1）基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

（2）归并排序：是建立在归并操作上的一种有效，稳定的排序算法。

什么是归并操作？

归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
逆序数为14；

（2）代码示例：

/**
 * 归并排序
 * @param nums 待排序数组
 * @param l 开始索引：0
 * @param h 最大索引：nums.length - 1
 * @return 排序好的数组
 */
public static int[] mergeSort(int[] nums, int l, int h) {
    if (l == h)
        return new int[]{nums[l]};

    int mid = l + (h - l) / 2;
    int[] leftArr = mergeSort(nums, l, mid); //左有序数组
    int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
    int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组

    int m = 0, i = 0, j = 0;
    while (i < leftArr.length && j < rightArr.length) {
        newNum[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
    }
    while (i < leftArr.length)
        newNum[m++] = leftArr[i++];
    while (j < rightArr.length)
        newNum[m++] = rightArr[j++];
    return newNum;
}

7、桶排序算法

（1）基本思想：把数组 arr 划分为 n 个大小相同子区间（桶），每个子区间各自排序，最后合并 。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

（2）排序过程：

1. 找出待排序数组中的最大值 max、最小值 min
2. 我们使用 动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1
3. 遍历数组 arr，计算每个元素 arr[i] 放的桶
4. 每个桶各自排序

（3）代码示例：

/**
 * 桶排序
 *
 * @param data 待排序数组
 */
public static void bucketSort(int data[]){
    int n = data.length;
    int bask[][] = new int[10][n];
    int index[] = new int[10];
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        max = max > (Integer.toString(data[i]).length()) ? max : (Integer.toString(data[i]).length());
    }
    String str;
    for (int i = max - 1; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            str = "";
            if (Integer.toString(data[j]).length() < max) {
                for (int k = 0; k < max - Integer.toString(data[j]).length(); k++)
                    str += "0";
            }
            str += Integer.toString(data[j]);
            bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = data[j];
        }
        int pos = 0;
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < index[j]; k++) {
                data[pos++] = bask[j][k];
            }
        }
        for (int x = 0; x < 10; x++) index[x] = 0;
    }
}

8、基数排序算法

（1）基本思想：将整数按位数切割成不同的数字，然后按每个位数分别比较。

（2）排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

（3）代码示例：

/**
 * 基数排序
 * @param number 待排序的数组
 * @param d 表示最大的数有多少位
 */
public static void sort(int[] number, int d) 
{
    int k = 0;
    int n = 1;
    int m = 1; //控制键值排序依据在哪一位
    int[][] temp = new int[10][number.length]; //数组的第一维表示可能的余数0-9
    int[] order = new int[10]; //数组order[i]用来表示该位是i的数的个数
    while (m <= d) {
        for (int i = 0; i < number.length; i++) {
            int lsd = ((number[i] / n) % 10);
            temp[lsd][order[lsd]] = number[i];
            order[lsd]++;
        }
        for (int i = 0; i < 10; i++) {
            if (order[i] != 0)
                for (int j = 0; j < order[i]; j++) {
                    number[k] = temp[i][j];
                    k++;
                }
            order[i] = 0;
        }
        n *= 10;
        k = 0;
        m++;
    }
}

未完待续——-

今天的文章常见十四种的Java算法分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。