AI 助理
文档备案控制台
开发者社区 人工智能 文章 正文

数据结构与算法学习十二：希尔排序、快速排序（递归、好理解）、归并排序（递归、难理解）

2024-10-16 736
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。

前言

  • 上节的三个排序算法：冒泡、选择、插入，较为简单，好理解，使用比较、交换的思想。但也都是基础。
  • 这节的三个排序算法：希尔、快速【看注释比较容易理解思路】、归并，难理解，使用递归的思想。
  • 这三个是难点，但也是重点。加油

一、希尔排序

1.1 简单插入排序存在的问题

我们看简单的插入排序可能存在的问题.
数组 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}

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

1.2 基本介绍

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

1.3 思路分析

1.3.1希尔排序法基本思想

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

1.3.2希尔排序法示意图

在这里插入图片描述
在这里插入图片描述

1.4 代码实现

有一群小牛, 考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用

  1. 希尔排序时， 对有序序列在插入时采用 交换法 , 并测试排序速度,相对较慢（容易理解）
  2. 希尔排序时， 对有序序列在插入时采用 移动法 , 并测试排序速度,相对较快（不易理解）
package com.feng.ch09_sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 希尔排序：
 *      对插入排序的 进一步优化
 * 使用到了 分组，并且缩小增量的 思想。
 *      第一次分组，gap(分组的次数)=【数组大小】/2,
 *      第二次分组，gap = （第一次分组次数）/2,
 *      第三次分组，gap = （上一次分组次数）/2,
 *
 * 有两种方式：
 * 第一种：交换式
 *      里面使用了冒泡排序的 交换思想
 *      效率低，容易理解  80000数据排序使用 14-19 S
 *
 * 第二种：移位式
 *      里面使用了 简单插入排序的 插入移位思想
 *      效率高，不易理解  8万数据： 1S ， 80万数据：  1S， 800万数据：4S
 * */
public class S4_ShellSort {
    public static void main(String[] args) {
        int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("初始数组：");
        System.out.println(Arrays.toString(array));

        System.out.println();
        System.out.println("排序后");
//        deductionShellSortBychange(array);
        int[] ints = shellSortByChange(array); // 交换式
        System.out.println(Arrays.toString(ints));

        // 测试 80000 个数据排序 所用的时间
        System.out.println();
        System.out.println("测试 80000 个数据 采用希尔排序（交换式） 所用的时间:");
        testTime();   // 交互式：19S, 移位式：1S
    }

    /*
     * 测试一下 希尔排序的速度O(n^2), 给 80000 个数据，测试一下
     * */
    public static void testTime() {
        // 创建一个 80000个的随机的数组
        int array2[] = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
        }
//        System.out.println(Arrays.toString(array2)); // 不在打印，耗费时间太长

        long start = System.currentTimeMillis();  //返回以毫秒为单位的当前时间
        System.out.println("long start:" + start);
        Date date = new Date(start); // 上面的也可以不要，但是我想测试
        System.out.println("date:" + date);
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
        System.out.println("排序前的时间是=" + format.format(date));

        shellSortByChange(array2); // 交互式
//        shellSortByMove(array2);   // 移位式

        System.out.println();
        long end = System.currentTimeMillis();
        Date date2 = new Date(end); // 上面的也可以不要，但是我想测试
        System.out.println("排序后的时间是=" + format.format(date2));
        System.out.println("共耗时" + (end - start) + "毫秒");
        System.out.println("毫秒转成秒为：" + ((end - start) / 1000) + "秒");
    }

    /*
     * 对交换式的希尔排序进行优化 -》》移位法
     * */
    public static int[] shellSortByMove(int[] array) {
        // 增量gap, 并逐步的缩小增量
        for (int gap = array.length / 2; gap > 0; gap /= 2) { // 共分 3 组
            // 从第 gap 个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < array.length; i++) {
                // 这里使用了 前面学习的 直接插入排序
                int j = i;
                int temp = array[j];
                if (array[j] < array[j - gap]) {
                    while ((j - gap) >= 0 && temp < array[j - gap]) {
                        //移动
                        array[j] = array[j - gap];
                        j -= gap;
                    }
                    //当退出while后，就给temp找到插入的位置
                    array[j] = temp;
                }
            }
        }
        return array;
    }

    /*
     * 交换式排序 整合
     * */
    public static int[] shellSortByChange(int[] array) {
        int temporary = 0;
        int count = 0;
        for (int gap = array.length / 2; gap > 0; gap /= 2) {  // 三次分组。
            for (int i = gap; i < array.length; i++) {    // 有几组，循环遍历几次，也就比较几次。
                // 遍历各组中所有的元素（共 gap 组，每组有  个元素），步长为 gap
                // 这里使用了交换：也就是前面学习的 冒泡排序的思想
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (array[j] > array[j + gap]) {
                        temporary = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temporary;
                    }
                }
            }
//            System.out.println("希尔排序第" + (++count) + "轮=" + Arrays.toString(array));
        }
        return array;
    }

    /*
     * 希尔排序：采用交换式
     * 使用逐步推导的方式
     * */
    public static int[] deductionShellSortBychange(int[] array) {
        // 临时变量，存放交换的数据
        int temporary = 0;

        /*
         * 希尔排序的第 1 轮排序
         * */
        System.out.println("第 1 轮排序");
        // 因为第 1 轮排序，是将 10 个数据分成了5组 ，所以要比较 5 次， i 从 5 开始
        for (int i = 5; i < array.length; i++) { // 共遍历 5 次，即 比较 5 次
            // 遍历各组中所有的元素（共 5 组，每组有2个元素），步长为 5
            for (int j = i - 5; j >= 0; j -= 5) {  // 仅比较一次，走一次逻辑，就知道啦
                if (array[j] > array[j + 5]) {
                    temporary = array[j];
                    array[j] = array[j + 5];
                    array[j + 5] = temporary;
                }
            }
        }
        System.out.println(Arrays.toString(array));

        /*
         * 希尔排序的第 2 轮排序
         * */
        System.out.println("第 2 轮排序");
        // 因为第 1 轮排序，是将 10 个数据分成了  5/2 = 2组
        for (int i = 2; i < array.length; i++) {
            // 遍历各组中所有的元素（共 5 组，每组有2个元素），步长为 5
            for (int j = i - 2; j >= 0; j -= 2) {
                if (array[j] > array[j + 2]) {
                    temporary = array[j];
                    array[j] = array[j + 2];
                    array[j + 2] = temporary;
                }
            }
        }
        System.out.println(Arrays.toString(array));

        /*
         * 希尔排序的第 3 轮排序
         * */
        System.out.println("第 3 轮排序");
        // 因为第 3 轮排序，是将 10 个数据分成了  2/2 = 1组
        for (int i = 1; i < array.length; i++) {
            // 遍历各组中所有的元素（共 5 组，每组有2个元素），步长为 5
            for (int j = i - 1; j >= 0; j -= 1) {
                if (array[j] > array[j + 1]) {
                    temporary = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temporary;
                }
            }
        }
        System.out.println(Arrays.toString(array));

        return array;
    }
}

1.5 测试结果

在这里插入图片描述

二、快速排序

2.1 基本介绍

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

2.2 思路分析

  1. 先把数组中的一个数当做基准数，一般会把数组中最左边的数当做基准数。
  2. 然后从两边进行检索，先从右边往左检索比基准数小的，再从左边往右检索比基准数大的。
  3. 如果检索到了，就停下，交换这两个元素。然后继续检索。
  4. 如果这两个索引指针相遇了，就退出循环。
  5. 将基准数与这两个索引遇到的数字进行对换。
  6. 基准数在这里就归位了，左边的数字都比基准数小，右边的数字都比基准数大。
  7. 然后使用递归进行排序。

2.3 代码实现

package com.feng.ch09_sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 快速排序：
 *       对冒泡排序的优化
 *
 * 时间复杂度：O(nlog2n)
 * 速度测试 ： 8万数据： 1S不到， 80万数据： 1S 不到， 800万数据：1S不到 ，速度超级快
 * */
public class S5_QuickSort {

    public static void main(String[] args) {
        int[] array = {-9, 78, 0, 23, -567, 70, -1, 900, 4561};
        System.out.println("初始数组：");
        System.out.println(Arrays.toString(array));

        System.out.println();
        System.out.println("排序后：");
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));

        // 测试 80000 个数据排序 所用的时间
        System.out.println();
        System.out.println("测试 80000 个数据 采用快速排序（交换式） 所用的时间:");
        testTime();   // 8万数据： 1S不到， 80万数据： 1S 不到， 800万数据：2-3
    }

    /*
     * 测试一下 快速排序的速度, 给 80000 个数据，测试一下
     * */
    public static void testTime() {
        // 创建一个 80000个的随机的数组
        int array2[] = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
        }
//        System.out.println(Arrays.toString(array2)); // 不在打印，耗费时间太长

        long start = System.currentTimeMillis();  //返回以毫秒为单位的当前时间
        System.out.println("long start:" + start);
        Date date = new Date(start); // 上面的也可以不要，但是我想测试
        System.out.println("date:" + date);
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
        System.out.println("排序前的时间是=" + format.format(date));

        quickSort(array2, 0, array2.length - 1);   // 移位式

        System.out.println();
        long end = System.currentTimeMillis();
        Date date2 = new Date(end); // 上面的也可以不要，但是我想测试
        System.out.println("排序后的时间是=" + format.format(date2));
        System.out.println("共耗时" + (end - start) + "毫秒");
        System.out.println("毫秒转成秒为：" + ((end - start) / 1000) + "秒");
    }

    /*
     * 快速排序方法：通俗异同，直接看注释即可
     *
     * @param array 需要排序的数组
     * @param left  最左边的下标，也是索引
     * @param right 最右边的下标，也是索引
     * */
    public static void quickSort(int[] array, int left, int right) {
        // 进行判断，如果左边索引比右边索引要大，是不合法的，直接使用return 结束这个方法
        if (right < left) {
            return;
        }

        // 定义变量保存基准数，这里的基准数用最左边的数来代替。
        int base = array[left];
        // 定义变量 i ，指向最左边
        int i = left;
        // 定义变量 j, 指向最右边
        int j = right;

        // 当 i 和 j 不相遇的时候，就在循环中进行检索。
        while (i != j) {
            // 先 由j 从右往左检索比基准数小的，如果检索到比基准数小的就停下
            // 如果检索比基准数大的或者相等的，就继续检索
            while (array[j] >= base && i<j) {
                j--; // j 从右往左移动
            }
            // i 从左往右检索。找比基准数 大的，
            while (array[i] <= base && i<j) {
                i++;// i 从左往右移动
            }

            // 如果代码走到这儿，i 和 j 都停下了，。然后交换 i 和 j 位置的元素
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        /*
        * 如果上面的 while 循环条件不成立了，会跳出这个循环，往下执行。
        * 如果这个条件不成立 说明 i 和 j 相遇了，也就是相等
        * 如果 i 和 j 相遇了，就交换基准数这个元素 和相遇位置的元素。
        * 把 相遇位置的元素 赋值 给基准数这个位置的元素
        * */
        array[left] = array[i];
        // 把基准数赋值给相遇位置的元素
        array[i] = base;

        // 基准数在这里就归位了，左边的数字都比基准数小，右边的数字都比基准数大。
        // 对基准数的 左边进行排序
        quickSort(array, left, i-1);

        // 排右边
        quickSort(array, j+1, right);
    }
}

2.4 测试结果

在这里插入图片描述

三、归并排序

3.1 基本介绍

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

3.2 思路分析

说明:
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。

在这里插入图片描述

3.3 代码实现

package com.feng.ch09_sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 归并排序
 *
 * 速度测试： 8万数据： 117Ms， 80万数据： 395Ms， 800万数据：2-3S
 * */
public class S6_MergetSort {

    public static void main(String[] args) {
        int[] array = {8, 4, 5, 7, 1, 3, 6, 2};  // 8-> merge 7次， 80000-> merge 80000-1=7999次

        int[] temp = new int[array.length];
        System.out.println("原始数组：");
        System.out.println(Arrays.toString(array));

        System.out.println();
        System.out.println("排序后：");
        mergetSort(array,0, array.length-1, temp);
        System.out.println(Arrays.toString(array));

        // 测试 80000 个数据排序 所用的时间
        System.out.println();
        System.out.println("测试 80000 个数据 采用归并排序（交换式） 所用的时间:");
        testTime();   // 8万数据： 1S不到， 80万数据： 1S 不到， 800万数据：2-3
    }

    /*
     * 测试一下 归并排序的速度, 给 80000 个数据，测试一下
     * */
    public static void testTime() {
        // 创建一个 80000个的随机的数组
        int array2[] = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
        }
//        System.out.println(Arrays.toString(array2)); // 不在打印，耗费时间太长

        long start = System.currentTimeMillis();  //返回以毫秒为单位的当前时间
        System.out.println("long start:" + start);
        Date date = new Date(start); // 上面的也可以不要，但是我想测试
        System.out.println("date:" + date);
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
        System.out.println("排序前的时间是=" + format.format(date));

        int[] temp = new int[array2.length];
        mergetSort(array2,0, array2.length-1, temp);   // 移位式

        System.out.println();
        long end = System.currentTimeMillis();
        Date date2 = new Date(end); // 上面的也可以不要，但是我想测试
        System.out.println("排序后的时间是=" + format.format(date2));
        System.out.println("共耗时" + (end - start) + "毫秒");
        System.out.println("毫秒转成秒为：" + ((end - start) / 1000) + "秒");
    }

    /*
     * 分 + 合的方法
     * */
    public static void mergetSort(int[] array, int left, int right, int[] temp) {
        if (left < right) {// 数据校验
            int mid = (left + right) / 2; // 中间索引
            // 向左递归 分解
            mergetSort(array, left, mid, temp);
            // 向右递归 分解
            mergetSort(array, mid + 1, right, temp);
            // 以上为分解
            // 以下这一句为合并
            merge(array, left, mid, right, temp);

        }
    }

    /*
     * 合并的方法
     *
     * @param array 排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     * */
    public static void merge(int[] array, int left, int mid, int right, int[] temp) {
//        System.out.println("XXXX");
        int i = left; // 初始化 i, 左边有序序列的初始索引
        int j = mid + 1; // 初始化j, 右边有序序列的初始索引
        int t = 0; // 指向 temp 数组的 当前索引。

        // (一)
        // 先把左右两边（有序）的数据按照规则填充到 temp数组
        // 直到 左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {
            /*
             * 如果 左边的有序序列 的当前元素，小于等于右边有序序列的 当前元素
             * 既然左边的当前元素，填充到 temp 数组
             * 然后 t++, i++
             * */
            if (array[i] <= array[j]) {
                temp[t] = array[i];
                t += 1;
                i += 1;
            } else {
                // 如果 右边的有序序列的当前元素 小于 左边有序序列的当前元素，则将右边的当前元素填充到 temp数组，然后 t++, j++
                temp[t] = array[j];
                t += 1;
                j += 1;
            }
        }

        /*
         * (二)
         * 当代码走到这里，说明 左边 或者 右边 ，已经有一方 有剩余的。
         * 把有 剩余数据 的一边的数据 依次全部填充到 temp
         * */
        // 左边 有序序列还有剩余的元素，就全部填充到 temp
        while (i <= mid) {
            temp[t] = array[i];
            t++;
            i++;
        }
        // 右边 有序序列还有剩余的元素，就全部填充到 temp
        while (j <= right) {
            temp[t] = array[j];
            t++;
            j++;
        }

        /*
         * (三)
         * 将 temp 数组的元素拷贝到 array
         * 注意，并不是每次都拷贝所有
         * */
        t = 0;
        int tempLeft = left;//
        // 第一次 合并： tempLeft = 0, right = 1, // tempLeft = 2, right = 3 // tempLeft = 0, right = 3
        // 最后一次，tempLeft = 0  right = 7
//        System.out.println("tempLeft=" + tempLeft + ",right=" + right);
        while (tempLeft <= right) {
            array[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }

    }

}

3.4 测试结果

在这里插入图片描述

文章标签：
算法
搜索推荐
索引
Shell
java冯坚持
目录
相关文章
哈基米编译器
|
算法 搜索推荐
快速排序-数据结构与算法
快速排序（Quick Sort）是一种基于分治法的高效排序算法。其核心思想是通过选择基准（pivot），将数组划分为左右两部分，使得左侧元素均小于基准，右侧元素均大于基准，然后递归地对左右两部分进行排序。时间复杂度平均为 O(n log n)，最坏情况下为 O(n²)（如数组已有序）。空间复杂度为 O(1)，属于原地排序，但稳定性不佳。 实现步骤包括编写 `partition` 核心逻辑、递归调用的 `quickSort` 和辅助函数 `swap`。优化方法有随机化基准和三数取中法，以减少最坏情况的发生。
哈基米编译器
844 13
羑悻的小杀马特
|
搜索推荐 C语言
数据结构（C语言）之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法，通过递归将数组不断分割为子数组，直到每个子数组仅剩一个元素，再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中，每次分割区间为[left, mid]和[mid+1, right]，确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值（初始为1），先对单个元素排序，再逐步扩大到更大的区间进行合并，直至整个数组有序。归并排序的时间复杂度为O(n*logn)，空间复杂度为O(n)，且具有稳定性，适用于普通排序及大文件排序场景。
羑悻的小杀马特
351 13
RossyYan
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序（头歌实践教学平台习题）【合集】
本关任务是实现二路归并算法，即将两个有序数组合并为一个有序数组。主要内容包括： - **任务描述**：实现二路归并算法。 - **相关知识**： - 二路归并算法的基本概念。 - 算法步骤：通过比较两个有序数组的元素，依次将较小的元素放入新数组中。 - 代码示例（以 C++ 为例）。 - 时间复杂度为 O(m+n)，空间复杂度为 O(m+n)。 - **测试说明**：平台会对你编写的代码进行测试，提供输入和输出示例。 - **通关代码**：提供了完整的 C++ 实现代码。 - **测试结果**：展示代码运行后的排序结果。 开始你的任务吧，祝你成功！
RossyYan
577 10
RossyYan
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序（头歌实践教学平台习题）【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括： - **任务描述**：实现希尔排序算法。 - **相关知识**： - 排序算法基础概念，如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列（增量序列）的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧，如循环嵌套和索引计算。 - **测试说明**：提供了测试输入和输出示例，帮助验证代码正确性。 - **我的通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了代码运行的测试结果。 通过这些内容，读者可以全面了解希尔排序的原理和实现方法。
RossyYan
427 10
RossyYan
|
搜索推荐 C++
【C++数据结构——内排序】快速排序（头歌实践教学平台习题）【合集】
快速排序是一种高效的排序算法，基于分治策略。它的主要思想是通过选择一个基准元素（pivot），将数组划分成两部分。一部分的元素都小于等于基准元素，另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序，最终使整个数组有序。(第一行是元素个数，第二行是待排序的原始关键字数据。本关任务：实现快速排序算法。开始你的任务吧，祝你成功！
RossyYan
503 7
ephemerals__
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
1393 10
那年春天
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
492 59
RossyYan
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
1258 77
hahaha无
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
336 0
栈区的非法访问导致的死循环(x64)
游客beejssedmb2sq
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
325 0

热门文章

最新文章

  • 1
    【数据结构入门】-堆的实现以及堆排序（2）
  • 2
    [数据结构] 数组与链表的优缺点和区别
  • 3
    使用metasploit进行栈溢出攻击-5
  • 4
    堆区和栈区的区别【转】
  • 5
    【数据结构】大根堆和小根堆
  • 6
    数据结构拾遗(2) --红黑树的设计与实现(中)
  • 7
    activty栈管理
  • 8
    基于OHCI的USB主机 —— UFI数据结构1
  • 9
    数据结构思维 第八章 索引器
  • 10
    【算法与数据结构】最大子序列和问题
  • 1
    软考中级软件设计师专项-数据结构与算法上篇
    1022
  • 2
    快速排序-数据结构与算法
    844
  • 3
    为什么要学习数据结构与算法
    442
  • 4
    局域网屏幕监控系统中的Python数据结构与算法实现
    613
  • 5
    2024重生之回溯数据结构与算法系列学习之串（12）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丟脸好嘛？】
    485
  • 6
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
    549
  • 7
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
    394
  • 8
    2024重生之回溯数据结构与算法系列学习（8）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
    347
  • 9
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二（5）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
    360
  • 10
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
    387

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    一条命令迁移，帮你实现 OpenClaw 与 Hermes Agent 记忆互通！