7大排序算法详解+java实现

目录

0 概述

1 冒泡排序

2 选择排序

3 插入排序

4 希尔排序

5 快速排序

6 归并排序

7 基数排序

下载地址

7大排序算法详解文档及java代码实现（可直接运行）下载地址：https://download.csdn.net/download/qq_39735940/19005360

0 概述

排序的分类：

1. 内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。
2. 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

常见的排序算法分类：

度量一个程序(算法)执行时间的两种方法：

1. 事后统计的方法。这种方法可行, 但是有两个问题：
   • 一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；
   • 二是所得时间的统计量依赖于计算机的硬件、软件等环境因素；这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。
2. 事前估算的方法。通过分析某个算法的时间复杂度来判断哪个算法更优。

平均时间复杂度和最坏时间复杂度

1. 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
2. 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

平均时间复杂度和最坏时间复杂度是否一致，和算法有关：

最基础的四个算法：冒泡、选择、插入、快排中，快排的时间复杂度最小O(n*log2n)，其他都是O(n2)

相关术语解释：

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
• 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
• 内排序：所有排序操作都在内存中完成；
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
• 时间复杂度： 一个算法执行所耗费的时间。
• 空间复杂度：运行完一个程序所需内存的大小。
• n：数据规模
• k：“桶”的个数
• In-place：不占用额外内存
• Out-place：占用额外内存

1 冒泡排序

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

/**
 * 冒泡排序
 * @param arr
 */
public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                 int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
           

冒泡排序的优化

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

/**
 * 冒泡排序的优化
 * @param arr
 */
public static void bubbleSortOfOptimize(int[] arr) {
    boolean flag = false; // 标识变量，表示是否进行过交换
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if(!flag){
            // 在一趟排序中，一次交换都没有发生过
            break;
        }else {
            flag = false;
        }
    }
}
           

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次，得到一个按排序码从小到大排列的有序序列。

/**
 * 选择排序（从小到大）
 * @param arr
 */
public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int curMinIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[curMinIndex]) {
                curMinIndex = j;
            }
        }
        if (curMinIndex != i) { // 一个小的优化，如果不是当前位置再进行交换
            int temp = arr[i];
            arr[i] = arr[curMinIndex];
            arr[curMinIndex] = temp;
        }
    }
}
           

3 插入排序

插入排序（Insertion Sorting）的基本思想是：

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

/**
 * 插入排序（从小到大）
 * @param arr
 */
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int insertVal = arr[i];
        // insertIndex表示插入的索引位置
        int insertIndex = i;
        for (int j = i; j > 0; j--) {
            // 如果当前要比较的数小于被比较的数，则被比较的数往右移动一位
            if (insertVal < arr[j - 1]) {
                arr[j] = arr[j - 1];
                insertIndex--;
            } else {
                break;
            }
        }
        arr[insertIndex] = insertVal;
    }
}
           

插入排序可能存在的问题：

数组 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}

结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.

4 希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

希尔排序法基本思想：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；

随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

/**
 * 希尔排序（从小到大）---交换法
 * @param arr
 */
public static void shellSort(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            // 遍历各组中所有的元素，共gap组，步长gap
            // 此处类似冒泡排序
            for (int j = i - gap; j >= 0; j -= gap) {
                if (arr[j] > arr[j + gap]) {
                    int temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
    }
}
           

对交换法的改进

希尔排序的移动法（效率有很大提升）

/**
 * 希尔排序（从小到大）---移动法
 * @param arr
 */
public static void shellSort2(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 从第gap个元素，逐个对其所在的组进行直接插入排序
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            if (arr[j] < arr[j - gap]) {
                // 此处类似插入排序
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    // 移动
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                // 当退出while，就给temp找到插入的位置
                arr[j] = temp;
            }
        }
    }
}
           

5 快速排序

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

基本思想是：

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

基准值可以选中间那位数，也可以选第一位或者最后一位。

/**
 * 快速排序，以数组最右侧一位作为基准值
 * @param arr
 * @param left
 * @param right
 */
public static void quickSort(int[] arr, int left, int right) {
    if (right > left) {
        int pivotVal = arr[right];
        // 保存最开始的左右值
        int oriLeft = left, oriRight = right;
        while (right > left) {
            // ***以右侧为基准值，则先遍历左侧***
            // 从左侧开始寻找，直到找到一个比基准值pivotVal大的值为止
            while (right > left && arr[left] <= pivotVal) {
                left++;
            }
            if (right > left) {
                // 将这个比基准值pivotVal大的值arr[left]，放到右侧
                arr[right] = arr[left];
                right--;  // 这个-1操作也可以不要，但是加上的话可以使得下面while循环少判断一次
            }
            while (right > left && arr[right] >= pivotVal) {
                right--;
            }
            if (right > left) {
                arr[left] = arr[right];
                left++;
            }
        }
        // 当left == right 时，把基准值放回right；
        // 由于left == right，所以下方的left 和 right表示的值都是一样的
        arr[right] = pivotVal;
        quickSort(arr, oriLeft, right - 1);
        quickSort(arr, left + 1, oriRight);
    }
}
           

6 归并排序

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

治阶段，需要将两个已经有序的子序列合并成一个有序序列。

比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，

来看下实现步骤：

/**
 * 归并排序
 *
 * @param arr   待排序的数组
 * @param left
 * @param right
 * @param temp  临时数组
 */
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2;   // 中间索引
        mergeSort(arr, left, mid, temp);    //向左递归进行分解
        mergeSort(arr, mid + 1, right, temp);   //向右递归进行分解
        merge(arr, left, mid, right, temp); // 合并
    }
}

/**
 * 将两段有序的序列合并成一段有序的序列
 *
 * @param arr   待排序的数组
 * @param left  左边有序序列的初始索引
 * @param mid   中间索引
 * @param right 右边索引
 * @param temp  临时数组
 */
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    //（1） 第一步，先将左右两块内容已经有序的序列进行逐个对比，合并成一个有序的序列
    int i = left;   // 左边有序序列的初始索引
    int j = mid + 1;    // 右边有序序列的初始索引
    int t = 0;  // 指向temp数组的当前索引
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            temp[t] = arr[i];
            t++;
            i++;
        } else {
            temp[t] = arr[j];
            t++;
            j++;
        }
    }
    //（2）第二步，将左右两边剩余的部分放入临时数组
    while (i <= mid) {
        temp[t] = arr[i];
        t++;
        i++;
    }
    while (j <= right) {
        temp[t] = arr[j];
        t++;
        j++;
    }
    //（3）第三步，将临时数组temp的元素拷贝到数组arr
    t = 0;
    int tempLeft = left;
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t];
        tempLeft++;
        t++;
    }
}
           

7 基数排序

1. 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
2. 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3. 基数排序(Radix Sort)是桶排序的扩展
4. 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序基本思想：

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

图文解释：

基数排序的说明：

1. 基数排序是对传统桶排序的扩展，速度很快；
2. 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError；
3. 基数排序时稳定的；
4. 有负数的数组，一般不用基数排序来进行排序；
5. 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

/**
 * 基数排序
 *
 * @param arr
 */
public static void radixSort(int[] arr) {
    //（1）找到数组中最大的数的位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max)
            max = arr[i];
    }
    // 得到最大数是几位数
    int maxLength = (max + "").length();
    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        // 定义一个二维数组，表示10个桶，每个桶就是一个一位数组
        // 为了防止在放入数的时候，数据溢出，则每个一位数组（桶），大小定义为arr.length
        int[][] bucket = new int[10][arr.length];
        // 定义一个数组，用于存储每个桶中的元素数量
        int[] bucketElementCount = new int[10];
        for (int j = 0; j < arr.length; j++) {
            // 取每个元素对应位数的值
            int digitOfElement = arr[j] / n % 10;
            bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
            bucketElementCount[digitOfElement]++;
        }
        // 遍历每个桶内的数据，将数据都取出放入到arr数组
        int index= 0;
        for (int j=0;j<bucket.length;j++){
            for(int k=0;k<bucketElementCount[j];k++){
                arr[index] = bucket[j][k];
                index ++;
            }
            // 每轮处理后，需要将每个桶中的元素数量置为0
            bucketElementCount[j] = 0;
        }
    }
}
           

下载地址

7大排序算法详解文档及java代码实现（可直接运行）下载地址：https://download.csdn.net/download/qq_39735940/19005360