十大经典排序算法

这篇具有很好参考价值的文章主要介绍了十大经典排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

十大经典排序算法

1、 冒泡排序(Bubble Sort):相邻元素比较,逐步将最大元素“冒泡”到序列最后。时间复杂度O(n^2)。

2、选择排序(Selection Sort):从序列中选择最小的元素,放到序列的起始位置,再从剩余元素中选择最小的元素放到已排序序列的末尾。时间复杂度O(n^2)。

3、插入排序(Insertion Sort):将序列分为已排序和未排序两部分,从未排序的部分选择元素插入到已排序的部分中,直到所有元素都被插入到已排序的部分。时间复杂度O(n^2)。

4、希尔排序(Shell Sort):插入排序的改进版,通过设置增量序列分组进行排序,每组用插入排序。时间复杂度与增量序列的选取有关,平均时间复杂度为O(n^1.3)。

5、归并排序(Merge Sort):将序列分成两个子序列,对每个子序列进行递归排序,然后合并两个有序子序列,直到合并成整个序列。时间复杂度O(nlogn)。

6、快速排序(Quick Sort):选择枢轴将序列分成两部分,将小于枢轴的元素放在左边,大于枢轴的元素放在右边,然后递归地对左右两部分进行快速排序。时间复杂度O(nlogn)。

7、堆排序(Heap Sort):使用堆的数据结构来维护序列,每次从堆顶选择最大(或最小)的元素,然后重新调整堆。时间复杂度O(nlogn)。

8、计数排序(Counting Sort):统计每个元素出现的次数,然后根据元素出现的顺序将它们排好。时间复杂度O(n+k),k是元素范围。

9、桶排序(Bucket Sort):将元素分配到桶中,对每个桶中的元素进行排序,然后按照桶的顺序依次输出所有元素。时间复杂度O(n+k)。

10、基数排序(Radix Sort):按照每个元素的位数进行排序,从低位到高位依次进行排序。时间复杂度O(dn),d是最大数字的位数。

冒泡排序

冒泡排序是一种简单的排序算法,它通过不断地交换相邻的元素来将序列排序。具体步骤如下:

1、从序列的第一个元素开始,依次比较相邻的两个元素,如果前一个元素大于后一个元素,就交换它们的位置。

2、继续向后遍历序列,重复步骤1,直到遍历到最后一个元素。

3、重复执行步骤1和2,直到序列中的所有元素都排好序。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换相邻的两个元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

这段代码使用了两层循环来实现冒泡排序。外层循环控制排序的趟数,内层循环控制每一趟的比较和交换。时间复杂度为O(n^2),空间复杂度为O(1)。

选择排序

通过不断选择未排序部分的最小元素,将它们逐渐移到数组的开头。具体实现中,每一轮都从未排序部分的第一个元素开始,扫描整个未排序部分,找到其中的最小元素,然后将它和未排序部分的第一个元素交换位置。重复这个过程直到整个数组有序。

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

在该实现中,变量minIndex表示未排序部分的最小元素的下标。每次从未排序部分的第一个元素开始,扫描整个未排序部分,找到其中的最小元素,然后将它和未排序部分的第一个元素交换位置,以此将最小元素移到已排序部分的末尾。重复这个过程直到整个数组有序。

插入排序

通过不断将未排序部分中的元素插入到已排序部分中的适当位置,最终完成排序。

public static void insertionSort(int[] arr) {
    int len = arr.length;
    for (int i = 1; i < len; i++) {
        int j = i;
        int temp = arr[j];
        while (j > 0 && arr[j - 1] > temp) {
            //如果前一个元素比当前元素大,则将前一个元素向后移动一位。
            //将 j 的值减1,继续比较前一个元素。
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
}

希尔排序

希尔排序是插入排序的一种改进版本,也称为“缩小增量排序”。其思想是将原序列分成若干子序列,对每个子序列进行插入排序,然后缩小增量,继续进行排序,直到增量为1时完成排序。希尔排序的关键在于选择合适的增量序列。

  1. 选择一个增量序列,通常选择初始增量为数组长度的一半,每次将增量缩小一半,直到增量为1。
  2. 对于每个增量,将数组分成若干个子序列,分别对每个子序列进行插入排序。
  3. 对于较大的增量,子序列中相距较远的元素可以快速排序,减小增量后子序列中相距较近的元素已经接近有序,插入排序的效率高。
  4. 最后增量为1时,整个序列已经基本有序,插入排序的效率最高。
public static void shellSort(int[] arr) {
    int len = arr.length;
    int gap = len / 2; // 初始增量
    while (gap > 0) {
        // 对每个子序列进行插入排序
        for (int i = gap; i < len; i++) {
            int j = i;
            int temp = arr[j];
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap /= 2; // 缩小增量
    }
}

在该实现中,变量gap表示增量,每次循环将gap除以2以缩小增量,直到gap为1时完成排序。在每次循环中,对于每个子序列(序列下标为i,步长为gap),使用插入排序的方法将子序列排序。

归并排序

归并排序是一种基于分治思想的排序算法。它的基本思想是将待排序数组分成若干个子数组,对每个子数组进行排序,然后将排好序的子数组合并成一个有序的数组。

具体步骤如下:

  1. 将待排序数组从中间分成两个子数组,递归地对左右两个子数组进行归并排序。
  2. 当子数组长度为1时,递归结束,返回结果。
  3. 合并左右两个排好序的子数组,得到新的有序数组。

下面是归并排序的Java代码实现:

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2; // 将数组分成左右两部分
            mergeSort(arr, left, mid); // 对左半部分进行归并排序
            mergeSort(arr, mid + 1, right); // 对右半部分进行归并排序
            merge(arr, left, mid, right); // 将排好序的左右两部分合并
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 创建临时数组
        int i = left; // 左半部分的指针
        int j = mid + 1; // 右半部分的指针
        int k = 0; // 临时数组的指针
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 将临时数组中的元素复制回原数组
        for (k = 0; k < temp.length; k++) {
            arr[left + k] = temp[k];
        }
    }

    public static void main(String[] args) {
        int[] arr = { 5, 3, 8, 6, 2, 7, 1, 4 };
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

在代码中,mergeSort方法是递归调用的归并排序方法,merge方法用于将排好序的左右两部分数组合并。归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。

快速排序

快速排序是一种高效的排序算法,它基于分治的思想,通过不断地将序列分成更小的子序列,然后对子序列进行排序来达到整体排序的目的。具体步骤如下:

  1. 从序列中选择一个元素作为基准,称为枢轴(pivot)。
  2. 将序列中所有小于枢轴的元素移到枢轴左边,所有大于枢轴的元素移到枢轴右边,相同的元素可以放在任意一边。
  3. 对枢轴左右两边的子序列分别重复步骤1和步骤2,直到子序列的长度为1或0。
public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        // 将数组分区,并返回分区点的位置
        int p = partition(arr, left, right);
        // 对分区点左右两边的子数组进行快速排序
        quickSort(arr, left, p - 1);
        quickSort(arr, p + 1, right);
    }
}

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];  // 选择第一个元素为枢轴
    int i = left, j = right;
    while (i < j) {
        // 从右往左找到第一个小于枢轴的元素
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        // 从左往右找到第一个大于枢轴的元素
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        // 交换这两个元素
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将枢轴放到最终位置
    arr[left] = arr[i];
    arr[i] = pivot;
    return i;
}

这段代码使用了递归来实现快速排序。在每一次排序中,我们选择第一个元素作为枢轴,将序列分为两部分,并返回枢轴的位置。然后,对枢轴的左右两部分分别进行递归排序。时间复杂度为O(nlogn),最坏情况下为O(n^2),空间复杂度为O(logn)。

堆排序

堆排序是一种基于二叉堆的排序算法。它的基本思想是先将待排序数组构建成一个二叉堆,然后将堆顶元素取出,再将剩余元素重新构建成一个新的堆,如此反复,直到取出所有元素。

具体步骤如下:

  1. 将待排序数组构建成一个二叉堆,即从最后一个非叶子节点开始,依次执行下沉操作,直到根节点。
  2. 取出堆顶元素,将堆的最后一个元素放到堆顶,再从堆顶开始执行下沉操作,使得堆重新满足堆的性质。
  3. 重复步骤2,直到堆为空,即所有元素都已取出。
import java.util.Arrays;

public class HeapSort {
    // 堆排序方法
    public static void heapSort(int[] arr) {
        // 构建堆,从最后一个非叶子节点开始,依次执行下沉操作,直到根节点
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            percolateDown(arr, i, arr.length);
        }
        // 取出堆顶元素,将其放到有序区间的末尾,重构堆
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 重新构建堆
            percolateDown(arr, 0, i);
        }
    }

    // 下沉操作,用于维护堆的性质
    private static void percolateDown(int[] arr, int i, int n) {
        int parent = i;
        int child = 2 * i + 1;
        while (child < n) {
            // 找出左右子节点中较大的那个
            if (child + 1 < n && arr[child] < arr[child + 1]) {
                child++;
            }
            // 如果子节点比父节点大,就交换它们的位置
            if (arr[parent] < arr[child]) {
                int temp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = temp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                // 如果父节点比子节点大,说明已经满足堆的性质,跳出循环
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 5, 3, 8, 6, 2, 7, 1, 4 };
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

在代码中,heapSort方法用于执行堆排序,percolateDown方法用于下沉操作,即用于维护堆的性质。

计数排序

计数排序是一种非比较排序算法,它的基本思想是统计每个元素在序列中出现的次数,然后依次输出。

public static void countingSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }

    int max = arr[0];
    int min = arr[0];
    int n = arr.length;

    // 找出待排序数组中的最大值和最小值
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        } else if (arr[i] < min) {
            min = arr[i];
        }
    }

    int range = max - min + 1;

    // 计数数组,存储每个元素出现的次数
    int[] count = new int[range];

    // 统计待排序数组中每个元素出现的次数
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }

    // 累加计数数组中的元素
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // 临时数组,存储排序后的结果
    int[] tmp = new int[n];

    // 从后往前遍历待排序数组,按照计数数组中的位置将元素放入临时数组中
    for (int i = n - 1; i >= 0; i--) {
        int index = count[arr[i] - min] - 1;
        tmp[index] = arr[i];
        count[arr[i] - min]--;
    }

    // 将临时数组中的元素拷贝回原数组
    System.arraycopy(tmp, 0, arr, 0, n);
}

桶排序

桶排序(Bucket Sort)是一种线性排序算法,它利用了函数的映射关系,将要排序的数据分到有限数量的桶中,再对每个桶里的数据进行单独排序。

实现桶排序的一般步骤如下:

  1. 确定待排序数组中最大值和最小值;
  2. 创建若干个桶,根据待排序数据的范围将数据放入相应的桶中;
  3. 对每个非空的桶中的数据进行排序,可以使用插入排序等算法;
  4. 将所有桶中的数据按顺序合并起来即可。
public static void bucketSort(int[] arr) {
    int n = arr.length;
    int maxVal = arr[0];
    int minVal = arr[0];
    for (int i = 1; i < n; i++) {
        maxVal = Math.max(maxVal, arr[i]);
        minVal = Math.min(minVal, arr[i]);
    }

    // 计算桶的个数,并创建桶
    int bucketCount = (maxVal - minVal) / n + 1;
    List<List<Integer>> buckets = new ArrayList<>(bucketCount);
    for (int i = 0; i < bucketCount; i++) {
        buckets.add(new ArrayList<>());
    }

    // 将数据分到各个桶中
    for (int i = 0; i < n; i++) {
        int bucketIdx = (arr[i] - minVal) / n;
        buckets.get(bucketIdx).add(arr[i]);
    }

    // 对每个桶中的数据进行排序
    for (int i = 0; i < bucketCount; i++) {
        Collections.sort(buckets.get(i));
    }

    // 将所有桶中的数据按顺序合并起来
    int idx = 0;
    for (int i = 0; i < bucketCount; i++) {
        List<Integer> bucket = buckets.get(i);
        for (int j = 0; j < bucket.size(); j++) {
            arr[idx++] = bucket.get(j);
        }
    }
}

在这个实现中,我们首先找出待排序数组中的最大值和最小值,然后根据数据的范围确定桶的数量。接着,我们将待排序数据放入对应的桶中,对每个桶中的数据进行排序,最后将所有桶中的数据按顺序合并起来,得到排序后的数组。

基数排序

基数排序(Radix Sort)是一种非比较排序算法,它将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序属于稳定排序,时间复杂度为O(d(n+r)),其中n是排序元素个数,d是数字位数,r是基数。它的主要思想是:将待排序的整数拆分成多个数字位上的值,然后从最低位到最高位依次对每个数字位上的值进行排序。

public static void radixSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    
    // 找出数组中的最大值,以便确定数字的位数
    int maxVal = arr[0];
    for (int i = 1; i < arr.length; i++) {
        maxVal = Math.max(maxVal, arr[i]);
    }
    
    // 根据数字的位数依次进行排序
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        // 初始化桶,用于存储每个数字位上的值
        int[] bucket = new int[10];
        // 统计每个桶中的元素个数
        for (int i = 0; i < arr.length; i++) {
            int digit = (arr[i] / exp) % 10;
            bucket[digit]++;
        }
        // 统计桶中的前缀和
        for (int i = 1; i < bucket.length; i++) {
            bucket[i] += bucket[i - 1];
        }
        // 将数组中的元素按照当前数字位上的值依次存放到新数组中
        int[] sortedArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            sortedArr[--bucket[digit]] = arr[i];
        }
        // 将排序后的数组复制回原数组
        System.arraycopy(sortedArr, 0, arr, 0, arr.length);
    }
}

在上面的代码中,我们首先找出了待排序数组中的最大值,以便确定数字的位数,然后依次对每个数字位上的值进行排序。具体来说,我们利用了桶排序的思想,在每次排序时都需要初始化桶,并统计每个桶中的元素个数。接着,我们根据桶中元素的前缀和,计算出每个数字位上的值在排序后的数组中的结束位置,从而将待排序数组中的元素依次存放到新数组中。最后,将排序后的数组复制回原数组,即可得到排好序的结果。文章来源地址https://www.toymoban.com/news/detail-702235.html

到了这里,关于十大经典排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构与算法》之十大基础排序算法

    冒泡排序是一种交换排序,它的思路就是在待排序的数据中,两两比较相邻元素的大小,看是否满足大小顺序的要求,如果满足则不动,如果不满足则让它们互换。 然后继续与下一个相邻元素的比较,一直到一次遍历完成。一次遍历的过程就被成为一次冒泡,一次冒泡的结束

    2024年02月05日
    浏览(95)
  • 数据结构:一篇拿捏十大排序(超详细版)

    排序: 所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性: 假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前, 而

    2024年02月08日
    浏览(50)
  • DSt:数据结构的最强学习路线之数据结构知识讲解与刷题平台、刷题集合、问题为导向的十大类刷题算法(数组和字符串、栈和队列、二叉树、堆实现、图、哈希表、排序和搜索、动态规划/回溯法/递归/贪心/分治)总

    Algorithm:【算法进阶之路】之算法面试刷题集合—数据结构知识和算法刷题及其平台、问题为导向的十大类刷题算法(数组和字符串、链表、栈和队列、二叉树、堆、图、哈希表、排序和搜索、回溯算法、枚举/递归/分治/动态规划/贪心算法)总结 目录 相关文章

    2024年02月08日
    浏览(52)
  • 【数据结构】经典排序法

    欢迎来到Cefler的博客😁 🕌博客主页:那个传说中的man的主页 🏠个人专栏:题目解析 🌎推荐文章:题目大解析2 插入排序是一种简单但有效的排序算法,它的基本思想是将一个元素插入到已排序的序列中,从而得到一个新的有序序列。 就像我们打扑克一样,一张一张的模,

    2024年02月07日
    浏览(37)
  • 【数据结构】经典排序

    什么是排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之

    2024年02月04日
    浏览(35)
  • 十大经典排序算法----堆排序(超详细)

    目录 1. 堆排序的基础知识 1.1 大顶堆小顶堆  1.2 向下调整算法 1.3 物理结构与逻辑结构的关系 2. 堆排序详解 2.1 堆排序整体思路  2.2 思路详解 2.2.1 建堆 2.2.2 大堆or小堆 2.2.3 输出数据 3. 时间复杂度分析 4. 完整代码  5. 彩蛋 堆排序(Heap Sort)就是对直接选择排序的

    2024年02月03日
    浏览(31)
  • 十大经典排序算法

    1、 冒泡排序(Bubble Sort):相邻元素比较,逐步将最大元素“冒泡”到序列最后。时间复杂度O(n^2)。 2、选择排序(Selection Sort):从序列中选择最小的元素,放到序列的起始位置,再从剩余元素中选择最小的元素放到已排序序列的末尾。时间复杂度O(n^2)。 3、插入排序(In

    2024年02月09日
    浏览(39)
  • 十大经典排序算法(上)

    目录 1.1冒泡排序 1. 算法步骤  3.什么时候最快 4. 什么时候最慢 5.代码实现 1.2选择排序 1. 算法步骤  2. 动图演示 3.代码实现  1.3 插入排序 1. 算法步骤 2. 动图演示 3. 算法实现 1.4 希尔排序 1. 算法步骤 2. 动图演示  3.代码实现 1.5 归并排序 1. 算法步骤  2. 动图演示  3.代码实现

    2024年02月02日
    浏览(37)
  • C语言之十大经典排序算法

            嗨喽,大家好,我是程序猿老王,程序猿老王就是我。         今天给大家讲一讲C语言十大经典排序算法原理与实现。 目录 一、排序算法背景 二、十大经典排序算法的由来 三、十大经典排序算法的复杂度 四、十大经典排序算法讲解 1.冒泡排序(Bubble Sort)

    2023年04月09日
    浏览(35)
  • 探索十大经典排序算法之美(基于Python)

    在计算机科学的世界中,排序算法无疑是最为经典和基础的主题之一。排序不仅是解决各种计算问题的基础,而且在日常编程中也是必不可少的一环。Python这一富有表达力的编程语言,提供了许多强大的工具和库,使得实现和理解排序算法变得更加直观和有趣。 本篇博客将带

    2024年02月21日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包