1. Toy模板网首页
  2. > Toy博客

七大排序算法一文通（易懂图解+优化代码）

10月前 作者：小白的白白 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了七大排序算法一文通（易懂图解+优化代码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

1.直接插入排序

2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序

6.快速排序

6.1 递归实现——Hoare版

6.2 递归实现——挖坑法

6.3 非递归实现

6.4 优化

7.归并排序

7.1 归并排序——递归实现

7.2 归并排序——非递归实现

8.复杂度以及稳定性

1.直接插入排序

😄基本思路

  1. 从待排序数组的第 i (初始情况下i = 2)个元素开始，依次拿该元素与其前面的 i-1 个元素进行比较。
  2. 在这 i-1 个元素中，如果存在比第i个元素大的元素，则将这个元素向后移动一位；否则将当前元素 i 放在比它小的第一个元素的后边.
  3. 比较完一趟后将 i 向后调整，重复上述 1， 2操作。总共进行 arr.length - 1轮即可完成排序.

七大排序算法一文通（易懂图解+优化代码）

🙂直接插入排序代码

//直接插入排序
public void insertSortDirectly(int[] array) {
if(array == null || array.length == 0) {
        return;
    }
    for(int i=1;i<array.length;i++) {
        int temp = array[i];
        int j = i-1;
        for(;j >= 0;j--) {
            if(array[j] > temp) {
                array[j+1] = array[j];
            } else {
                break;
            }
        }
        //将当前元素放在j + 1 的位置上
        array[j+1] = temp;
    }
}

七大排序算法一文通（易懂图解+优化代码）

2.希尔排序

希尔排序实质上还是一种插入排序，不同的是采用了分组插入排序的思想，每次对每组进行的插入排序都会整组数据的插入排序效率更高，所以希尔排序的平均效率相对于普通的插入排序要高。

😄基本思路：

  1. 首先确定一个组数值：gap。通常情况下我们取 整组元素个数/2 作为gap的初始值。
  2. 根据gap将整组数据分成gap组（具体的分组方式见下方图解），对每一组进行一次普通插入排序。
  3. 将gap值缩小为原来的二分之一，再次将整组数据分成gap组，对魅族数据进行插入排序。
  4. 重复 3 步骤，直至gap值变为0，我们就可以得到一个有序序列。

七大排序算法一文通（易懂图解+优化代码）

😄希尔排序代码

public void shellSort(int[] array) {
    if (array == null || array.length == 0) {
        return;
    }
    int gap = array.length;
    while (gap > 1) {
        gap /= 2;
        shell(array, gap);
    }
}

private void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int temp = array[i];
        int j = i - gap;
        for (; j >= 0; j -= gap) {
            if (temp < array[j]) {
                array[j + gap] = array[j];
            } else {
                break;
            }
        }
        array[j + gap] = temp;
    }
}

3.选择排序

😄基本思路

  1. 从第i（初始情况下i=1）元素开始，从其后边的元素中挑选出一个比该元素小的最小的元素，然后与该元素进行交换。
  2. i 向后移动，重复步骤1
  3. 当 i 的值指向为这组数据的倒数第一个元素时，就完成了排序。

七大排序算法一文通（易懂图解+优化代码）

😄选择排序代码

public static void selectSort(int[] array) {
    if (array == null || array.length == 0) {
        return;
    }
    for (int i = 0; i < array.length - 1; i++) {
        int minPos = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minPos]) {
                minPos = j;
            }
        }
        if (minPos != i) {
            int temp = array[i];
            array[i] = array[minPos];
            array[minPos] = temp;
        }
    }
}

4.堆排序

😄基本思路

  1. 升序排列建大堆，降序排列建小堆
  2. 将堆顶元素与堆的最后一个没有被交换过的元素进行交换
  3. 进行一次堆的向下调整，调整范围为堆的大小-调整轮数
  4. 重复2、3操作，进行堆的大小size-1轮操作即可得到有序序列

七大排序算法一文通（易懂图解+优化代码）

😄堆排序代码

public static void heapSort(int[] array) {
    if (array == null || array.length == 0) {
        return;
    }
    //此处我们以升序排列为例，所以建大根堆
    createBigHeap(array);

    //进行排序操作
    int end = array.length - 1;
    while (end > 0) {
        int temp = array[0];
        array[0] = array[end];
        array[end] = temp;
        siftDown(array, 0, end);
        end--;
    }
}

private static void createBigHeap(int[] array) {
    for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
        siftDown(array, i, array.length);  //从下标为i的位置向下调整
    }
}

private static void siftDown(int[] array, int parent, int size) {
    int childLeft = parent * 2 + 1;
    while (childLeft < size) {
        if (childLeft + 1 < size && array[childLeft] < array[childLeft + 1]) {
            childLeft = childLeft + 1;
        }
        if (array[parent] < array[childLeft]) {
            int temp = array[parent];
            array[parent] = array[childLeft];
            array[childLeft] = temp;
        }
        parent = childLeft;
        childLeft = parent * 2 + 1;
    }
}

5.冒泡排序

😄基本思路

  1. 依次比较待比较组中的相邻元素，满足排序序列比较条件则进行值的交换。假设待排序序列的长度为length，经过这样的一轮比较后，最大或最小的元素就位于了序列中的最前/最后（或最后/最前）的位置上。
  2. 再重复 1步骤 length-1 次，即可完成排序。
  3. 及其详细的实现步骤可以查看之前发布的这篇文章
    冒泡排序详解

七大排序算法一文通（易懂图解+优化代码）

😄冒泡排序代码

public static void bubbleSort(int[] array) {
    if (array == null || array.length == 0) {
        return;
    }
    for (int i = 0; i < array.length - 1; i++) {
        boolean flag = false;    //标志变量。如果进行了一轮比较而没有进行交换操作，说明已经有序了
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                flag = true;
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        if(!flag) {
            break;
        }
    }
}

6.快速排序

😄基本思路

  1. 快速排序本质上也是一种基于交换排序来实现的。在进行排序之前，我们需要先在排序序列中指定一个基准值；
  2. 然后定义两个指针从序列的最左侧和最右侧分别寻找一个比基准值大和小的元素，进行交换；重复进行上述操作，直至左右指针相遇。然后将基准值与左右指针相遇的位置上的值进行交换。
  3. 以基准值分割左右序列，在其左右序列中重复上述 1 ，2 步骤直至序列有序

6.1 递归实现——Hoare版

😄快速排序递归实现图解

七大排序算法一文通（易懂图解+优化代码）

😄快速排序递归实现代码——Hoare

public static void quickSort(int[] array) {
    if (array == null || array.length == 0) {
        return;
    }
    quickSort(array, 0, array.length - 1);
}

private static void quickSort(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    int pivot = getPivot(array, start, end);
    quickSort(array, start, pivot - 1);
    quickSort(array, pivot + 1, end);
}

private static int getPivot(int[] array, int left, int right) {
    int startPos = left;
    int temp = array[left];
    while (left < right) {
        while (left < right && array[right] >= temp) {
            right--;
        }
        while (left < right && array[left] <= temp) {
            left++;
        }
        int cur = array[left];
        array[left] = array[right];
        array[right] = cur;
    }
    array[startPos] = array[left];
    array[left] = temp;
    return left;
}

6.2 递归实现——挖坑法

😄基本思路

这种方法与Hoare版本的快排区别在于根据基准调整左右序列的做法。挖坑法是直接将基准位置空出，从右侧开始找到一个比基准小的数就将该数放在基准的位置上，从左侧开始找到一个比基准大的数就放在右侧空出的位置上，左右交替进行；当左右指针相遇时，就将基准值放在相遇位置上，并更新基准值下标。剩余的做法和Hoare一致，即在其左右子序列中重复上述操作。

七大排序算法一文通（易懂图解+优化代码）

 😄快速排序递归实现代码——挖坑法

public static void quickSortNonRecursive(int[] array) {
    if (array == null || array.length == 0) {
        return;
    }
    Stack<Integer> stack = new Stack<>();
    int start = 0;
    int end = array.length - 1;
    int pivot = getPivot(array, start, end);
    if (pivot > start + 1) {
        stack.push(start);
        stack.push(pivot - 1);
    }
    if (pivot < end - 1) {
        stack.push(pivot + 1);
        stack.push(end);
    }
    while (!stack.isEmpty()) {
        end = stack.pop();
        start = stack.pop();
        pivot = getPivot(array, start, end);
        if (pivot > start + 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if (pivot < end - 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }
    }
}

6.3 非递归实现

😄非递归实现图解

七大排序算法一文通（易懂图解+优化代码）

 😄非递归实现代码

public static void quickSortNonRecursive(int[] array) {
    if (array == null || array.length == 0) {
        return;
    }
    Stack<Integer> stack = new Stack<>();
    int start = 0;
    int end = array.length-1;
    int pivot = getPivot(array, start, end);
    if (pivot > start + 1) {
        stack.push(start);
        stack.push(pivot - 1);
    }
    if (pivot < end - 1) {
        stack.push(pivot + 1);
        stack.push(end);
    }
    while (!stack.isEmpty()) {
        end = stack.pop();
        start = stack.pop();
        pivot = getPivot(array, start, end);
        if (pivot > start + 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if (pivot < end - 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }
    }
}

6.4 优化

三数取中法

要解决的问题：

  • 当使用递归法快速排序时，如果序列已经趋于有序。那么每次的pivot值可能会取在序列的最左边或者最右边，这样就可能会出现下边的单项递归，大大增加了递归的层数，很有可能会导致栈溢出错误。我们使用“三数取中”这种优化就是为了提升递归快排的健壮性。
    七大排序算法一文通（易懂图解+优化代码）

做法：

  • private static int threeNum(int[] array, int left, int right) {
    int mid = (left + right) / 2;
    if (array[left] < array[right]) {
        if (array[mid] < array[left]) {
            return left;
        } else if (array[mid] > array[right]) {
            return right;
        } else {
            return mid;
        }
    } else {
        if (array[mid] < array[right]) {
            return right;
        } else if (array[mid] > array[left]) {
            return left;
        } else {
            return mid;
        }
    }
}

7.归并排序

归并排序采用归并思想，将已经分割好的子序列进行合并，并且在合并的过程中对归并的子序列进行比较排序，这样，当归并结束总序列也就有序了。

😄基本思路

  1. 定义待排序数组的初始位置指针和结束位置指针 start和end，计算中间值 mid = (left +right)/2
  2. 以mid值为左右序列界限进行分割，对左序列和又序列重复1过程，当递归下去发现开始位置和结束位置相等了，就说明元素序列已经不可再分了。
  3. 对分割后的序列之间进行二路归并，并且在归并的过程中对数组进行排序，这样当子序列合并结束数组也就有序了

7.1 归并排序——递归实现

😄归并排序递归实现图解

七大排序算法一文通（易懂图解+优化代码）

😄归并排序递归实现代码

/**
 * 归并排序
 * @param array 待排序数组
 */
public static void mergeSort(int[] array) {
    mergeSort(array, 0, array.length - 1);
}

private static void mergeSort(int[] array, int start, int end) {
    //归
    if (start >= end) {
        return;
    }
    int mid = (start + end) / 2;
    mergeSort(array, start, mid);
    mergeSort(array, mid + 1, end);

    //并
    merge(array, start, mid, end);
}

private static void merge(int[] array, int start, int mid, int end) {
    int s1 = start;
    int s2 = mid + 1;
    int[] temp = new int[end - start + 1];
    int pos = 0;
    while (s1 <= mid && s2 <= end) {
        if(array[s1] <= array[s2]) {
            temp[pos++] = array[s1++];
        } else {
            temp[pos++] = array[s2++];
        }
    }
    while(s1 <= mid) {
        temp[pos++] = array[s1++];
    }
    while(s2 <= end) {
        temp[pos++] = array[s2++];
    }
    //将这个归并好的数组拷贝到排序数组中
    for (int i = start; i <= end; i++) {
        array[i] = temp[i-start];
    }
}

7.2 归并排序——非递归实现

😄归并排序非递归实现图解

七大排序算法一文通（易懂图解+优化代码）

 😄归并排序非递归实现代码文章来源地址https://www.toymoban.com/news/detail-466795.html

public static void mergeSortNonRecursive(int[] array) {
    if (array == null || array.length == 0) {
        return;
    }
    int gap = 1;
    while (gap < array.length) {
        for (int i = 0; i < array.length; i += gap * 2) {
            int left = i;
            int mid = left + gap - 1;
            int right = mid + gap;
            //right和mid有可能会越界，对其进行修正
            if (mid >= array.length) {
                mid = array.length - 1;
            }
            if (right >= array.length) {
                right = array.length - 1;
            }
            merge(array, left, mid, right);
        }
        gap *= 2;
    }
}

private static void merge(int[] array, int start, int mid, int end) {
    int s1 = start;
    int s2 = mid + 1;
    int[] temp = new int[end - start + 1];
    int pos = 0;
    while (s1 <= mid && s2 <= end) {
        if (array[s1] <= array[s2]) {
            temp[pos++] = array[s1++];
        } else {
            temp[pos++] = array[s2++];
        }
    }
    while (s1 <= mid) {
        temp[pos++] = array[s1++];
    }
    while (s2 <= end) {
        temp[pos++] = array[s2++];
    }
    //将这个归并好的数组拷贝到排序数组中
    for (int i = start; i <= end; i++) {
        array[i] = temp[i - start];
    }
}

8.复杂度以及稳定性

排序算法 时间复杂度 空间复杂度 稳定性
直接插入排序 O(n²) O(1) 稳定
希尔排序 O(七大排序算法一文通（易懂图解+优化代码）) O(1) 不稳定
选择排序 O(n²) O(1) 不稳定
堆排序 O(n*log2n) O(1) 不稳定
冒泡排序 O(n²) O(1) 稳定
快速排序 O(n*logn) O(logn) 不稳定
归并排序 O(n*logn) O(n) 稳定

到了这里，关于七大排序算法一文通（易懂图解+优化代码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【JAVA】七大排序算法(图解)

    【JAVA】七大排序算法(图解)

    稳定性： 待排序的序列中若存在值相同的元素，经过排序之后，相等元素的先后顺序不发生改变，称为排序的稳定性。 思维导图： （排序名称后面蓝色字体为 时间复杂度和稳定性 ） 核心思路 每次从无序区间中选择第一个元素，插入到有序区间的合适位置，直到整个数组有

    2024年02月12日
    浏览(36)
  • 排序算法大全：冒泡排序【含优化】，选择排序【含优化】，直接插入排序，希尔排序，堆排序，快速排序【含3种实现版本及非递归实现】，归并排序【含非递归实现】。详细图解，文字解释，代码实现，性能分析。

    排序算法大全：冒泡排序【含优化】，选择排序【含优化】，直接插入排序，希尔排序，堆排序，快速排序【含3种实现版本及非递归实现】，归并排序【含非递归实现】。详细图解，文字解释，代码实现，性能分析。

    目录  一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析   三、直接插入排序 1、直接插入排序思想 2、直接插入排序算法的性能分析 四、希尔排序 1、希尔排序思想 2、希尔排序算法的性能分析 五、堆排

    2024年02月20日
    浏览(58)
  • 数据结构：手撕图解七大排序(含动图演示)

    数据结构：手撕图解七大排序(含动图演示)

    插入排序分为直接插入排序和希尔排序，其中希尔排序是很值得学习的算法 希尔排序的基础是直接插入排序，先学习直接插入排序 直接插入排序类似于打扑克牌前的整牌的过程，假设我们现在有2 4 5 3四张牌，那么应该怎么整牌？ 方法很简单，把3插到2和4中间，这样就完成了

    2024年02月15日
    浏览(51)
  • KMP算法——通俗易懂讲好KMP算法：实例图解分析+详细代码注解 --》你的所有疑惑在本文都能得到解答

    KMP算法——通俗易懂讲好KMP算法：实例图解分析+详细代码注解 --》你的所有疑惑在本文都能得到解答

    KMP 是一个 解决模式串在文本串是否出现过 ，如果出现过，最早出现的位置的经典算法。 Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于 在一个文本串 S 内查找一个模式串 P 的出现位置 ，这个算法由 Donald Knuth 、 Vaughan Pratt 、 James H. Morris 三人于 1977 年联合发表

    2024年02月07日
    浏览(49)
  • Java 七大排序之快速排序（三种方法包含优化方法）

    Java 七大排序之快速排序（三种方法包含优化方法）

    任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 1)  挖坑法 划分完之后，再左右递归。

    2024年02月09日
    浏览(40)
  • 【算法与数据结构】归并排序的代码实现（详细图解）以及master公式的讲解

    【算法与数据结构】归并排序的代码实现（详细图解）以及master公式的讲解

    目录 1、归并排序  1.1、算法描述  1.2、图解说明 2、代码实现  3、master公式 3.1、公式以及结论 3.2、适用于某些特殊的递归 3.3、计算归并排序的时间复杂度 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用 递归 或者说是 分治法 （Divide and Conquer）的一个非

    2024年02月08日
    浏览(61)
  • 七大排序算法和计数排序

    七大排序算法和计数排序

    以下排序以从小到大排序为例 时间复杂度： 最好情况：完全有序的情况 1 2 3 4 5 O(N) 最坏情况：完全逆序的情况 5 4 3 2 1 O(N^2)（相当于等差数列求和） 空间复杂度：O(1) 稳定性：稳定 当所给的数据越有序，直接插入排序越快 有一组基本有序的数据时，用直接插入排序较好 希

    2024年02月16日
    浏览(47)

  • 一文速学数模-最优化算法(二)梯度下降算法一文详解+Python代码

    目录 前言 一、梯度下降法简述 二、梯度下降算法原理理解 1.梯度 2.梯度定义

    2023年04月24日
    浏览(46)
  • 七大经典比较排序算法

    七大经典比较排序算法

    🌟 思想： 直接插入排序是一种简单的插入排序法， 思想是是把待排序的数据按照下标从小到大，依次插入到一个已经排好的序列中，直至全部插入，得到一个新的有序序列 。 例如：我们玩扑克牌的时候，每次摸进一张的新的牌我们会将其插入到合适的位置。 思路： 我们

    2024年02月15日
    浏览(47)
  • 七大排序算法详解

    七大排序算法详解

    常见的稳定的排序有三种：直接插入排序，冒泡排序，归并排序 对于一组数据元素排列，使用某种排序算法对它进行排序，若 相同数据之间的前后位置 排序后和未排序之前是相同的，我们就成这种排序算法具有稳定性 单看单个属性的稳定性并无意义，稳定性主要体现在对具

    2024年02月11日
    浏览(21)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包