开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> JAVA数据结构与算法-八大排序算法 -> 正文阅读

[数据结构与算法]JAVA数据结构与算法-八大排序算法

一.八大排序简介

1.冒泡排序

（1）算法思想

从前向后遍历，依次比较相邻元素的值，若为逆序则交换，使较大的元素逐渐从前部移向后部，每次遍历结束后最大的元素移至末尾，下一次无需遍历该元素。

优化：若某次遍历中未交换元素，则表明数组有序，排序结束。

（2）特点

1）算法简单，程序简便，但交换次数多，较费时
2）对n个元素的数组需遍历n-1次，每次遍历将最大的元素放在最后，下次无需遍历该元素。

（3）图解

在这里插入图片描述

（4）代码

public static void BubbleSort(int[] arr) {  // 冒泡排序
    boolean flag = false;
    int temp;
    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;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (!flag) break;
        flag = false;
    }
}

2.选择排序

（1）算法思想

依次从数组中选出最小（最大）的元素与数组第一个元素交换，每次遍历只交换一次。
第一次从arr[0] ~ arr[n-1]中选出最小元素，与arr[0]交换；
第二次从arr[1] ~ arr[n-1]中选出最小元素，与arr[1]交换；
第三次从arr[2] ~ arr[n-1]中选出最小元素，与arr[2]交换；
…
第n-1次arr[n-2] ~ arr[n-1]中选出最小元素，与arr[n-2]交换。
共交换n-1次。

（2）特点

交换次数比冒泡排序少。

（3）图解

在这里插入图片描述

（4）代码

public static void SelectSort(int[] arr) {  // 选择排序
    int arr_min;
    int index;
    for (int i = 0; i < arr.length - 1; i++) {  // n个元素共n-1次交换
        arr_min = arr[i];
        index = i;
        for (int j = i + 1; j < arr.length; j++) {  // 遍历寻找最小值
            if (arr[j] < arr_min) {
                index = j;
                arr_min = arr[j];
            }
        }
        if (index != i) {  // 若最小值为第一个值则不需交换，否则交换
            arr[index] = arr[i];
            arr[i] = arr_min;
        }
    }
}

3.插入排序

（1）算法思想

将数组看为以第一个元素为基准的有序数组和包含其他元素的无序数组，将无序数组中的元素依次插入有序数组（与数组中的每个值比较，找到位置）。
在代码中未额外开辟空间，而是采用从右向左比较，若有序数组中比较的元素比该元素大则右移，否则插入的方法。

（2）特点

适合数组本身比较有序的情况，若数组本身逆序程度较大（有序表很长，需插入的数较小）则在插入数据时需多次右移，增加算法时间。

（3）图解

在这里插入图片描述

（4）代码

public static void InsertSort(int[] arr) {  // 插入排序
         // 将下标为1的数到最后一个数插入
        for (int i = 1; i < arr.length; i++) { 
            int insertVal = arr[i];  // 取出要插入的数并保存
            int insertIndex = i - 1;  // 从它的前一个数开始判断
            
            // 前一个条件表示还没判断完，后一个表示放在该数前面
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {  
                // 该数后移一位，给前面留地方
                arr[insertIndex + 1] = arr[insertIndex];  
                insertIndex--;  // 从右向左判断
            }
            // 第一个条件不满足则表示要插入的数为最小数
            //第二个条件不满足则表示要插入的数比arr[insertIndex]大，放在该数后面
            if (insertIndex + 1 != i) arr[insertIndex + 1] = insertVal;
        }
    }

4.希尔排序

（1）算法思想

把数组按一定增量分组，对每组使用直接插入排序，之后将增量/2，再次排序，直到增量为1，进行最后一次排序。

设数组长度为n。
第1次增量为n/2，共分n/2组（即索引为j的元素与索引为j-n/2，j+n/2，j+n…的元素在同一组），进行n/2次直接插入排序。
第2次增量为n/4，共分n/4组，进行n/4次直接插入排序。
…
第log₂n次增量为1，共分1组，进行1次插入排序，排序后的结果即为有序数组。

（2）特点

经调整后，对索引值较大、数值较小的元素在前几次排序中已经插入到前面，最后一次元素较有序，算法时间减少。

（3）图解

在这里插入图片描述

（4）代码

public static void ShellSort(int[] arr) {  // 希尔排序
    // gap为增量，将arr分为gap组分别进行插入排序，每组的元素相隔gap
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {  
        // 下标为0到gap-1的元素表示每组的第一个元素，将之后的每个元素都进行插入
        for (int i = gap; i < arr.length; i++) {  
            int j = i;  // 待插入元素下标
            int temp = arr[j];  // 待插入元素
            // 对待插入元素使用组内插入排序确定位置，此时下标为i元素之前的每组元素都已按照顺序排列
            while (j - gap >= 0 && temp < arr[j - gap]) {  
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

5.快速排序

（1）算法思想

基于数组中的一个基准元素（代码中为索引在中间的数）将数组分成两部分，左部分的所有元素都小于等于基准元素，右部分的所有元素都大于等于基准元素，再将左右两部分分别递归进行相同操作，直到只剩一个或两个元素。

（2）特点

速度快，最常使用的排序算法，使用递归以空间换时间。

（3）图解

以最左端元素作为基准元素
在这里插入图片描述
以最右端元素作为基准元素

（4）代码

public static void QuickSort(int[] arr, int left, int right) {  // 快速排序 由于用到递归，传入的参数除了数组还有最左元素下标和最右元素下标
    int l = left;  // 此次递归最左元素的下标，作为指针使用
    int r = right;  // 此次递归最有元素的下标，作为指针使用
    int pivot = arr[(l + r) / 2];  // 中轴值，位置处于l和r中间的数
    int temp;
    while (l < r) {
        while (arr[l] < pivot) l++;  // 没找到则指针继续右移
        while (arr[r] > pivot) r--;  // 没找到则指针继续左移
        
        // 两个while循环均停止，说明找到不符合顺序的值，或者已经遍历到pivot，此时分三种情况:
        // 1.两侧均找到需交换的值，此时l、r为该值的下标
        // 2.一侧找到需交换的值，另一侧全部遍历，未找到，即（l为该值下标，r = pivot）或（l = pivot，r为该值下标）
        // 3.两侧均未找到，此时l = r = pivot
        
        // 若l >= r，说明pivot左右两边已经全部按照顺序排好，l>r为防止越界
        if (l >= r) break;
        
        // 此时将不符合条件的值进行交换：两个值进行交换，或者一个值和pivot交换
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        
        // 针对存在与pivot相等的值，此时若arr[l]或arr[r]扫描到该值，会误认为扫描完成，此时l != r，会陷入死循环
        // 在交换完成后再进行一次扫描，若两侧都未找到需交换的值，即l == r，则l < r，在下一次循环时break跳出循环
        // 否则跳过与pivot相等的值
        if (arr[l] == pivot) r--;
        if (arr[r] == pivot) l++;
    }
    // while循环推出，本次分组结束，在下一次递归中当l==r，pivot会同时进行左递归和右递归，出现栈溢出
    if (l == r) {
        l++;
        r--;
    }
    if (left < r) QuickSort(arr, left, r);
    if (right > l) QuickSort(arr, l, right);
}

6.归并排序

（1）算法思想.

采用分治算法，先将数组分为左右两个子数组，递归将子数组二分化，直到每个子数组只有一个元素；之后使用合并有序数组的方法（双指针）逐个将子数组合并，直到最终生成有序数组。

（2）特点

与快速排序的区别：快速排序在分的时候按照基准元素将大的分在一边，小的分在一边，分完即有序，只需依次合并；归并排序在分的时候直接按照索引值分，在合并的时候才考虑顺序，采取从下到上的方式，用两个有序子数组并成一个有序数组。

（3）图解

在这里插入图片描述

（4）代码

public static void merge(int[] arr, int left, int mid, int right, int[] temp) {  // 将两个有序数组合并
   int i = left;  // 左数组指针，将下标为i的数与右数组的数作比较
    int j = mid + 1;  // 右数组指针，将下标为j的数与左数组的数作比较
    int t = 0;  // 合并后临时数组temp的指针，每次比较后将较小的数放在下标为t的地方
    while (i <= mid && j <= right) {  // 当两侧数组都有数据时继续比较
        if (arr[i] <= arr[j]) {  // 若左数组的数较小，则将其添加到temp数组下标为t的地方，同时指针移位
            temp[t] = arr[i];
            i++;
            t++;
        } else temp[t++] = arr[j++];
    }
    // 否则表明至少有一边数组中的数已经全部放入temp，将两边的数分别判断，按原次序放入temp
    while (i <= mid) temp[t++] = arr[i++];
    while (j <= right) temp[t++] = arr[j++];
    // 将temp中下标从left到right的数拷贝到原数组arr中
    t = 0;
    int tempLeft = left;
    while (tempLeft <= right) arr[tempLeft++] = temp[t++];
}

    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);
    }
}

7.基数排序

（1）算法思想

与桶排序相似，按照数组元素各位的大小将其装入不同的桶从而进行排序。
并不考虑正负的情况下，共有10个桶，分别代表某元素的某位为0-9，当比较某位时，将数组中的每个元素按照该位的数字（位数不足的补0）放入对应的桶中，全放入后按桶中的顺序拷贝到数组中，更新数组，之后接着比较上一位的数字，直到最高位，之后更新的数组就是有序数组。

设数组中最大数有i位。
第一次比较个位，将数组中的每个元素按照个位放到对应的桶中，之后将个位为0的第一个数到个位为9的最后一个数依次放入数组，个位越小越靠前。
第二次比较十位，更新数组后十位越小越靠前，十位相同的元素中个位越小越靠前（在前一次排序中将其排到个位较大元素的前面）。
…
第i次比较第i位，其他第i位为0的元素均在最前，第i位不为0的元素在其之后按照该位大小排序，更新数组之后即为有序数组。

（2）特点

目前的代码不适用于存在负数的情况，对于只有一个元素特别大的情况会耗费大量时间。

（3）图解

在这里插入图片描述

（4）代码

public static void RadixSort(int[] arr) {  // 基数排序（桶排序的扩展）
   int[][] bucket = new int[10][arr.length];  // 二维数组，10个桶分别放置某一位为0-9的数
    int[] counts = new int[10];  // 下标为i的数据表示某位为i的桶中数据的个数
    int max_num = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max_num) max_num = arr[i];
    }
    int max_len = (max_num + "").length();
    for (int l = 0; l < max_len; l++) {
        for (int num : arr) {
            int digit = num / (int)(Math.pow(10, l)) % 10;  // 提取某一位
            bucket[digit][counts[digit]] = num;  // 在该位为digit的桶中添加该元素，counts[digit]表示该桶中元素个数，如为2，则表示该桶中有2个元素，新元素的下标为2
            counts[digit]++;  //该桶添加新元素后元素数量+1
        }
        // 按照桶中的顺序依次将数据放入原数组，进行下一次排序
        int index = 0;  // 用于计数放置的数据
        for (int j = 0; j < counts.length; j++) {  // 第j个桶
            if (counts[j] != 0) {
                for (int k = 0; k < counts[j]; k++) {  // 第j个桶里面第k个元素
                    arr[index] = bucket[j][k];
                    index++;
                }
            }
            counts[j] = 0;
        }
    }
}