首页 > 其他分享 >【408考点之数据结构】排序的基本概念

【408考点之数据结构】排序的基本概念

时间:2024-07-01 10:59:05浏览次数:16  
标签:arr 排序 int 算法 high ++ 考点 数据结构 408

排序的基本概念

排序是计算机科学中的一个基本操作,目的是将一组无序的数据元素按照特定的顺序排列起来。排序在数据管理、检索和分析中有着广泛的应用,能够提高数据处理的效率和准确性。

1. 排序的定义

排序(Sorting)是指将一组记录按某个关键字或多个关键字的大小关系进行排列的过程。常见的排序顺序包括升序(从小到大)和降序(从大到小)。

2. 排序算法的分类

排序算法根据其基本原理和实现方式,可以分为多种类型。主要包括以下几类:

  1. 内部排序:指所有排序操作在内存中完成的排序。

    • 交换排序:通过交换元素的位置来实现排序。常见的有冒泡排序和快速排序。
    • 选择排序:每次从待排序数据中选择最小(或最大)的元素放到已排序序列的末尾。常见的有简单选择排序和堆排序。
    • 插入排序:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。常见的有直接插入排序、希尔排序。
    • 归并排序:将序列分成若干子序列,对每个子序列分别排序,然后合并已排序的子序列,最终得到排序结果。
    • 分配排序:根据元素的某个特征(如位、关键字)进行分配和排序。常见的有桶排序和基数排序。
  2. 外部排序:当数据量大到无法全部装入内存时,需要用到外部存储设备进行排序。典型的外部排序算法是多路归并排序。

3. 排序算法的性能分析

评价一个排序算法的好坏,通常从以下几个方面进行:

  1. 时间复杂度:表示算法执行所需时间的量级,通常用“大O”符号表示。常见的时间复杂度有 O(n^2)、O(n log n) 等。
  2. 空间复杂度:表示算法执行过程中所需额外空间的量级。
  3. 稳定性:如果排序后相等关键字的记录相对顺序保持不变,则称该排序算法是稳定的。稳定的排序算法在某些场景中非常重要,如按多个关键字排序时。
  4. 复杂性:指算法的实现难度和代码复杂度。
4. 常见排序算法

冒泡排序:通过重复遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就交换它们的位置,直到整个数列有序。

void bubbleSort(int arr[], int n) {
    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;
            }
        }
    }
}

快速排序:通过选择一个基准元素,将待排序序列分成两部分,一部分比基准元素小,另一部分比基准元素大,然后递归地对两部分进行排序。

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

归并排序:采用分治法,将序列分成若干子序列,对每个子序列进行排序,然后合并有序子序列得到排序结果。

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}
5. 排序算法的选择

在实际应用中,选择合适的排序算法需要综合考虑时间复杂度、空间复杂度、稳定性等因素。

  1. 数据量小:可以选择时间复杂度为 O(n^2) 的排序算法,如冒泡排序、选择排序、插入排序。
  2. 数据量大:一般选择时间复杂度为 O(n log n) 的排序算法,如快速排序、归并排序、堆排序。
  3. 要求稳定性:可以选择稳定的排序算法,如归并排序、冒泡排序、插入排序。
  4. 空间受限:可以选择原地排序算法,如快速排序、堆排序。

标签:arr,排序,int,算法,high,++,考点,数据结构,408
From: https://blog.csdn.net/gygkhd/article/details/140081353

相关文章

  • 【408考点之数据结构】顺序查找和折半查找
    顺序查找和折半查找在数据处理中,查找操作是非常重要的一部分。顺序查找和折半查找是两种常见的查找方法,它们各有优缺点和适用场景。以下是对这两种查找方法的详细介绍。1.顺序查找定义:顺序查找(SequentialSearch),也称线性查找,是一种最简单、最直接的查找方法。它从数据集......
  • [JLU] 数据结构与算法上机题解思路分享-第一次上机
    前言首先,请务必自己尽全力尝试实现题目,直接看成品代码,思维就被拘束了,也很容易被查重。这里只是思路解析的博客,代码仓库是JLU_Data_Structures_Record希望你能在这里找到你想要的:)正文A调皮的哈利分数30作者朱允刚单位吉林大学贝蒂是个打字高手,打字时有不看屏幕的习......
  • Mysql--B+树--数据结构
    基本概念-B+树/B树B树(B-tree)和B+树(B+tree)是常见的自平衡搜索树数据结构,用于在存储和检索大量数据时提供高效的操作。它们具有一些共同的基本概念:节点(Node):B树和B+树的数据存储在节点中。节点可以包含多个关键字和对应的指针。在B树中,叶子节点和内部节点的结构相同,都存储数据......
  • 【数据结构与算法】拓扑排序,关键活动,关键路径 详解
    拓扑排序算法booltopologicalSort(){ stack<int>stk; intid[N]; intcnt=0; for(inti=1;i<=n;i++){ if(!inDeg[i]){ stk.push(i); } id[i]=inDeg[i]; } while(stk.size()){ intt=stk.top(); stk.pop(); cout<<t<......
  • 【数据结构与算法】最小生成树,Prim算法,Kruskal算法 详解
    最小生成树的实际应用背景。最节省经费的前提下,在n个城市之间建立通信联络网。Kruskal算法(基于并查集)voidinit(){for(inti=1;i<=n;i++){pre[i]=i;}}llroot(lla){lli=a;while(pre[i]!=i){i=pre[i];......
  • 数据结构十天期末计划day0
    复习知识点大纲刷一套期末试题(了解题型分布和知识点)//下面这套年份有点早近几年的试卷老师都不发0.0,新的没有判断题重在后期编译题理论部分定义逻辑结构时可不考虑物理结构。(F) 绪论部分知识线性表采用顺序存储,必须占用一片连续的存储单元。(T)了解线......
  • 数据结构/排序/堆排序 --- 逻辑讲解、代码实现、图形展示
    一、总体逻辑:    1.写一个交换的函数swap备用    2.写一个维护堆的性质的函数heapify备用    3.数组-> 堆(不明白的别急,后面会详细解释)    4.维护整个堆(看不懂别急别急别急)    5.堆顶和堆底的最后一个元素互换(不明......
  • 深入理解栈:计算机科学中的基础数据结构
    1.栈的概念及结构栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(LastInFirstOut)的原则。压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。出栈:栈的删除操作叫做......
  • nginx架构&&基本数据结构&&配置&&模块&&请求详解
    初探nginx架构众所周知,nginx性能高,而nginx的高性能与其架构是分不开的。那么nginx究竟是怎么样的呢?这一节我们先来初识一下nginx框架吧。nginx在启动后,在unix系统中会以daemon的方式在后台运行,后台进程包含一个master进程和多个worker进程。我们也可以手动地关掉后台模式,让ng......
  • 数据结构(C语言版)-第一章绪论
    1.1什么是数据结构数据结构是计算机科学中一个核心概念,它涉及到如何在计算机中有效地存储、组织和管理数据。数据结构的选择和设计直接影响到算法的效率和程序的性能。其基本要素包括数据元素(也称为节点或记录)、数据元素之间的关系,以及在此基础上定义的各种操作。具体来......