常见排序算法

排序的分类

• 内部排序:

  指将需要处理的所有数据都加载到内部存储器中进行排序。

• 外部排序法：

  数据量过大，无法全部加载到内存中，需要借助外部存储进行
  排序。

  

1、冒泡排序

基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待
排序序列从前向后（从下标较小的元素开始）,依次比较
相邻元素的值，若发现逆序则交换，使值较大
的元素逐渐从前移向后部，就象水底下的气泡一样逐渐
向上冒

排序过程

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

代码示例

public static void bubbleSort(int[] arr) {

    for (int i = 0; i < arr.length - 1; i++) {//确定排序趟数
        //这里length - 1 -i, i表示前面的i次循环已经把大的数移动到后部分了,
        //所以后部分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;
            }
        }
    }
}

简单优化

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较

代码示例

public static void bubbleSort(int[] arr) {

    for (int i = 0; i < arr.length - 1; i++) {
        Boolean flag = false;
        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;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

2、选择排序

基本介绍

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的

选择排序思想

选择排序（select sorting）它的基本思想是：第一次从arr[0]arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列

代码简单示例

    public static void selectSort(int[] arr) {

    for (int i = 0; i < arr.length - 1; i++) {
        int min = arr[i];
        int minIndex = i;
        // 遍历
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) { // 说明min不是真的最小值
                min = arr[j]; // 重置min
                minIndex = j; // 重置minIndex
            }
        }
        // 判断是否需要交换
        if (minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
    }
}

3、插入排序

插入排序的简单介绍

插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表

代码实现

public void insertSort(int[] arr) {
    /* i 为排序的数据的下标 将第一个作为已经有序的列表 故，无序从 1 开始  遍历所有未排序元素*/
    for (int i = 1; i < arr.length; i++) {
        /* j 已经排序的下标 */
        int j = i - 1;

        /* 待排序数据 */
        int insertValue = arr[i];
        /*如果当前数据与排序后的最后一个数据比较，如果当前数据比插入后的数据小，就将插入后的数据后移动 */
        for (; j >= 0 &&  insertValue < arr[j]; j--) {
            /* 将排序后的数据后移一位 */
            arr[j + 1] = arr[j];
        }
        /* 将待插入的数据放到找到的 不满足 （ j >= 0 && arr[j] > arr[i] ） 条件的前一个位置*/
        arr[j + 1] = insertValue;
    }
}

4、希尔排序

概述

简单插入排序存在的问题:
我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.

希尔排序法介绍

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

基本思想:
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

图示：

代码实现

     /**
     * 实现代码： 首先分组，之后再进行shell排序即可
     * @param arr
     */
      public void shellSort(int[] arr) {

        /* 分组 ，gap 是 分组后的步长 */
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            /* 进行shell排序 */

            /* i 为排序的数据的下标  遍历所有未排序元素*/
            for (int i = gap; i < arr.length; i ++) {
                /* j 已经排序的下标 */
                int j = i - gap;

                /* 待排序数据 */
                int insertValue = arr[i];
                /*如果当前数据与排序后的最后一个数据比较，如果当前数据比插入后的数据小，就将插入后的数据后移动 */
                for (; j >= 0 && insertValue < arr[j]; j -= gap) {
                    /* 将排序后的数据后移一位 */
                    arr[j + gap] = arr[j];
                }
                /* 将待插入的数据放到找到的 不满足 （ j >= 0 && arr[j] > arr[i] ） 条件的前一个位置*/
                arr[j + gap] = insertValue;
            }

        }
    }

5、快速排序

概述

快速排序（Quicksort）是对冒泡排序的一种改进。

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

分析

基本思想:
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此对快速排序作了进一步的说明：挖坑填数+分治法

挖坑填数+分治法 分析

1. 以一个数组作为示例，取区间第一个数为基准数。

   0	1	2	3	4	5	6	7	8	9
   72	6	57	88	60	42	83	73	48	85

• 初始时，i = 0; j = 9; X = a[i] = 72

• 由于已经将 a[0] 中的数保存到 X 中，可以理解成在数组 a[0] 上挖了个坑，可以将其它数据填充到这来。

2. 从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j–;

   数组变为：

   0	1	2	3	4	5	6	7	8	9
   48	6	57	88	60	42	83	73	88	85

• i = 3; j = 7; X=72

3. 再重复上面的步骤，先从后向前找，再从前向后找。

• 从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

• 从i开始向后找，当i=5时，由于i==j退出。

• 此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

  数组变为：

  0	1	2	3	4	5	6	7	8	9
  48	6	57	42	60	72	83	73	88	85

4. 可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结

• 1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
• 2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
• 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
• 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

实现挖坑填数的代码

    //快速排序
    void quickSort(int s[], int l, int r)
    {
        if (l < r)
        {
            //将中间的这个数和第一个数交换 
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                while (i < j && s[j] >= x) {
                    // 从右向左找第一个小于x的数
                    j--;
                }
                if (i < j) {
                    s[i++] = s[j];
                }

                while (i < j && s[i] < x) {
                    // 从左向右找第一个大于等于x的数
                    i++;
                }
                if (i < j) {
                    s[j--] = s[i];
                }
            }

            s[i] = x;
            // 递归调用
            quick_sort(s, l, i - 1);
            quick_sort(s, i + 1, r);
        }
    }

6、归并排序

简介

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

归并排序思想示意图1-基本思想

归并排序思想示意图2-合并相邻有序子序列:

代码实现

    //归并排序
public static void mergeSort(int[] arr,int low,int high) {
    int middle=(high+low)/2;
    if(low<high) {
        //处理左边
        mergeSort(arr, low, middle);
        //处理右边
        mergeSort(arr, middle+1, high);
        //归并
        merge(arr,low,middle,high);
    }
}

/**
    * 合并数组前后两部分
    *
    * @param arr  数组
    * @param low  开始位置
    * @param middle  中间分割位置
    * @param high 结束位置
    */
public static void merge(int[] arr,int low,int middle, int high) {
    //用于存储归并后的临时数组
    int[] temp = new int[high-low+1];
    //记录第一个数组中需要遍历的下标
    int i=low;
    //记录第二个数组中需要遍历的下标
    int j=middle+1;
    //用于记录在临时数组中存放的下标
    int index=0;
    //遍历两个数组取出小的数字，放入临时数组中
    while(i<=middle&&j<=high) {
        //第一个数组的数据更小
        if(arr[i]<=arr[j]) {
            //把小的数据放入临时数组中
            temp[index]=arr[i];
            //让下标向后移一位；
            i++;
        }else {
            temp[index]=arr[j];
            j++;
        }
        index++;
    }
    //处理多余的数据
    while(j<=high) {
        temp[index]=arr[j];
        j++;
        index++;
    }
    while(i<=middle) {
        temp[index]=arr[i];
        i++;
        index++;
    }
    //把临时数组中的数据重新存入原数组
    for(int k=0;k<temp.length;k++) {
        arr[k+low]=temp[k];
    }
}

7、归并排序

基数排序(桶排序)介绍

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用

基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
基数排序(Radix Sort)是桶排序的扩展

基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序基本思想

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

基数排序图文说明:

将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序:

第1轮排序 [按照个位排序]:
说明： 事先准备10个数组(10个桶)， 0-9 分别对应 位数的 0-9
(1) 将 各个数，按照个位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出

第1轮排序后：{542, 53 ,3 ,14 ,214 ,748}

第2轮排序 [按照十位排序]

(1) 将 各个数，按照十位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出

第2轮排序后： {3 ,14 ,214 ,542 ,748 ,53}

第3轮排序 [按照百位排序]
(1) 将 各个数，按照百位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出

第3轮排序后：{3 ,14 ,53 ,214 ,542 ,748} 【ok】

代码实现

public static void  radixSort(int[] arr) {
    //存最数组中最大的数字
    int max=Integer.MIN_VALUE;
    for(int i=0;i<arr.length;i++) {
        if(arr[i]>max) {
            max=arr[i];
        }
    }
    //计算最大数字是几位数
    int maxLength = (max+"").length();
    //用于临时存储数据的数组
    int[][] temp = new int[10][arr.length];
    //用于记录在temp中相应的数组中存放的数字的数量
    int[] counts = new int[10];
    //根据最大长度的数决定比较的次数
    for(int i=0,n=1;i<maxLength;i++,n*=10) {
        //把每一个数字分别计算余数
        for(int j=0;j<arr.length;j++) {
            //计算余数
            int ys = arr[j]/n%10;
            //把当前遍历的数据放入指定的数组中
            temp[ys][counts[ys]] = arr[j];
            //记录数量
            counts[ys]++;
        }
        //记录取的元素需要放的位置
        int index=0;
        //把数字取出来
        for(int k=0;k<counts.length;k++) {
            //记录数量的数组中当前余数记录的数量不为0
            if(counts[k]!=0) {
                //循环取出元素
                for(int l=0;l<counts[k];l++) {
                    //取出元素
                    arr[index] = temp[k][l];
                    //记录下一个位置
                    index++;
                }
                //把数量置为0
                counts[k]=0;
            }
        }
    }
}

常用排序算法总结和对比

常用排序算法对比

相关术语解释

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度： 一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
n: 数据规模
k: “桶”的个数
In-place: 不占用额外内存
Out-place: 占用额外内存

常见查找算法

在java中，常用的查找有四种:

1. 顺序(线性)查找
2. 二分查找/折半查找
3. 插值查找
4. 斐波那契查找

1、顺序(线性)查找（比较简单）

查找算法中顺序查找算是最简单的了，无论是有序的还是无序的都可以，只需要一个个对比即可，但其实效率很低

代码实现

public static int search(int[] arr, int key) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == key)
            return i;
    }
    return -1;
}

2、二分查找算法

分析

采用二分法查找时，数据需是有序不重复的 。

基本思想：

假设数据是按升序排序的，对于给定值 x，从序列的中间位置开始比 较，如果当前位置值等于 x，则查找成功；若 x 小于当前位置值，则在数列的前半段中查找；若 x 大于当前位置值则在数列的后半段中继续查找，直到找到为止。

代码实现

    /**
     * 二分法查找
     * @param arr 查找数组
     * @param low 左边索引
     * @param high 右边索引
     * @param key 查找目标值
     * @return 目标值索引
     */
    public int binarySearch(int[] arr, int low, int high, int key) {

        if (arr.length <= 0 || low > high) {
            return -1;
        }

        int mid = (low + high) / 2;

        if (key == arr[mid]) {
            return mid;
        } else if (key < arr[mid]) {
            return binarySearch(arr, low, mid - 1, key);
        } else{
            return binarySearch(arr, mid + 1, high, key);
        }
    }

3、插值查找算法

概述

插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找

代码实现

        /**
     * 插值查找
     *
     * @param arr  查找数组
     * @param low  左边索引
     * @param high 右边索引
     * @param key  查找目标值
     * @return 目标值索引
     */
    public int insertValueSearch(int[] arr, int low, int high, int key) {

        if (arr.length <= 0 || low > high) {
            return -1;
        }

        int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);

        if (key == arr[mid]) {
            return mid;
        } else if (key < arr[mid]) {
            return insertValueSearch(arr, low, mid - 1, key);
        } else {
            return insertValueSearch(arr, mid + 1, high, key);
        }
    }

从时间复杂度来说，其最坏时间复杂度也是 O(longn)，但对于表长较大，而关键字分布又比较均匀的查找表来说，其平均性能要比二分查找好的多。

反之，若查找表中关键字分布非常不均匀，那么插值查找未必是很合适的选择。