比较常见的几种排序算法

server/2025/3/17 5:12:12/

1. 冒泡排序 (Bubble Sort)

void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {  // 遍历次数int swapped = 0;  // 优化:若本轮未交换则提前结束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;swapped = 1;}}if (!swapped) break;  // 无交换则已有序}
}

  • 原理
    通过相邻元素的比较和交换,每一轮将最大的元素“冒泡”到数组末尾。

  • 时间复杂度

    • 最好:O(n)(已有序时优化后)

    • 平均/最坏:O(n²)

  • 稳定性:稳定(相等元素不交换)

  • 优点:简单易懂,无需额外空间。

  • 缺点:效率低,不适用于大规模数据。

  • 适用场景:教学示例或小规模数据。

  • 1. 冒泡排序 (稳定,时间复杂度 O(n²))

    cvoid bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {  // 遍历次数int swapped = 0;  // 优化:若本轮未交换则提前结束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;swapped = 1;}}if (!swapped) break;  // 无交换则已有序}
    }

  • 2. 选择排序 (Selection Sort)

  • 原理
    每一轮从未排序部分选出最小值,与当前未排序部分的第一个元素交换。

  • 时间复杂度

    • 所有情况:O(n²)

  • 稳定性:不稳定(交换可能破坏相等元素的顺序)

  • 优点:简单,原地排序。

  • 缺点:效率低,无论数据是否有序都需要完整遍历。

  • 适用场景:小规模数据或对内存敏感的场景。

  • cvoid selectionSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {int min_idx = i;  // 记录最小元素下标for (int j = i+1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 将最小值交换到当前位置int temp = arr[i];arr[i] = arr[min_idx];arr[min_idx] = temp;}
    }

    3. 插入排序 (Insertion Sort)

  • 原理
    将数组分为已排序和未排序两部分,逐个将未排序元素插入到已排序部分的正确位置。

  • 时间复杂度

    • 最好:O(n)(已有序时)

    • 平均/最坏:O(n²)

  • 稳定性:稳定(插入时保持相等元素的相对顺序)

  • 优点:对小规模或部分有序数据高效。

  • 缺点:大规模乱序数据效率低。

  • 适用场景:小规模数据、数据基本有序或在线排序(数据逐步到达)。

  • void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {  // 从第二个元素开始int key = arr[i];  // 当前待插入元素int j = i - 1;// 将比key大的元素后移while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;  // 插入正确位置}
    }

    4. 快速排序 (Quick Sort)

  • 原理
    采用分治法,选择一个基准元素(pivot),将数组分为小于基准和大于基准的两部分,递归排序子数组。

  • 时间复杂度

    • 平均/最好:O(n log n)

    • 最坏:O(n²)(如数组已有序且选固定基准)

  • 稳定性:不稳定(分区交换可能破坏顺序)

  • 优点:实际应用中速度最快(平均性能好)。

  • 缺点:最坏情况效率低,递归栈可能溢出。

  • 优化手段:随机选基准、三数取中法。

  • 适用场景:大规模数据,对稳定性无要求。

  • // 分区函数
    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 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); // 递归右半区}
    }// 调用示例:quickSort(arr, 0, n-1);

    5. 归并排序 (Merge Sort)

  • 原理
    采用分治法,将数组递归分成两半,分别排序后合并两个有序子数组。

  • 时间复杂度

    • 所有情况:O(n log n)

  • 稳定性:稳定(合并时保留相等元素的顺序)

  • 优点:稳定且时间复杂度稳定。

  • 缺点:需要额外存储空间(O(n))。

  • 适用场景:需要稳定排序、数据规模较大且内存允许。

  • // 合并两个有序子数组
    void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int L[n1], R[n2];  // 临时数组// 复制数据到临时数组for (int i = 0; i < n1; i++) L[i] = arr[left + i];for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];// 合并过程int i = 0, j = 0, k = left;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++];while (j < n2) arr[k++] = R[j++];
    }void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;  // 防止溢出mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
    }// 调用示例:mergeSort(arr, 0, n-1);

    6. 希尔排序 (Shell Sort)

  • 原理
    插入排序的改进版,通过定义递减的间隔序列(如n/2, n/4, ... 1),对间隔分组内的元素进行插入排序。

  • 时间复杂度

    • 取决于间隔序列,一般为O(n^(1.3~2))

  • 稳定性:不稳定(分组可能破坏相等元素的顺序)

  • void shellSort(int arr[], int n) {// 初始间隔设为n/2,逐步缩小for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];  // 当前待插入元素int j;// 对间隔gap的元素进行插入排序for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
    }

    二去重复化算法:主要通过将存储单元中的数据元素通过循环遍历的方式进行删除相同数据元素,返回新定不相同的元素到新的存储空间中

    1对于同一数组或者指针:

    #include <stdio.h>
    #define N 80
    int fun(int a[], int n)
    {   int i,j=1; //设置初始组数下标for(i=1;i<n;i++) //遍历数组元素{if(a[i]!=a[j-1]) //判断相邻元素是否一致a[j++]=a[i];   //复制新的元素}return j; //返回数组元素个数}int main()
    {  int  a[N]={2,2,2,3,4,4,5,6,6,6,6,7,7,8,9,9,10,10,10,10},i,n=20;void NONO ();printf("The original data :\n");for(i=0; i<n; i++)printf("%3d",a[i]);n=fun(a,n);printf("\n\nThe data after deleted :\n");for(i=0;i<n;i++)printf("%3d",a[i]); printf("\n\n");NONO();
    }
    void NONO ()
    {/* 请在此函数内打开文件,输入测试数据,调用 fun 函数,输出数据,关闭文件。 */FILE *rf, *wf; int a[N], n, i, j ;rf = fopen("in.dat","r") ;wf = fopen("out.dat","w") ;for(i = 0 ; i < 5 ; i++) {fscanf(rf, "%d", &n) ;for(j = 0 ; j < n ; j++) fscanf(rf, "%d", &a[j]) ;n = fun(a, n) ;for(j = 0 ; j < n ; j++) fprintf(wf, "%4d", a[j]) ;fprintf(wf, "\n") ;}fclose(rf) ; fclose(wf) ;
    }
    

    2对于对个数组或者指针的去重复化:

  • #include <stdio.h>// 去重函数
    int removeDuplicates(int arr[], int n, int result[]) {int i, j, k = 0;for (i = 0; i < n; i++) {  //循环原数组int isDuplicate = 0;       //初始化标志位for (j = 0; j < i; j++) {    //标志前面的数组元素if (arr[i] == arr[j]) {isDuplicate = 1; //判断是否有相同元素的标志位break;}}if (!isDuplicate) {result[k++] = arr[i];  将不同值放在新数组中}}return k;
    }int main() {int arr[] = {1, 2, 3, 2, 4, 3};int n = sizeof(arr) / sizeof(arr[0]);int result[100];  // 假设结果数组足够大int newSize = removeDuplicates(arr, n, result);// 输出去重后的数组for (int i = 0; i < newSize; i++) {printf("%d ", result[i]);}printf("\n");return 0;
    }
    }
    

总结对比

算法时间复杂度(平均)稳定性空间复杂度适用场景
冒泡排序O(n²)稳定O(1)教学、小数据
选择排序O(n²)不稳定O(1)小数据、内存敏感
插入排序O(n²)稳定O(1)小数据、部分有序
快速排序O(n log n)不稳定O(log n)大规模数据、通用排序
归并排序O(n log n)稳定O(n)大规模数据、需稳定性
希尔排序O(n^(1.3~2))不稳定O(1)中等规模数据、内存敏感

http://www.ppmy.cn/server/175622.html

相关文章

Emacs 折腾日记(十七)——文本属性

我们在上一篇中介绍了如何对文件中的文本进行操作&#xff0c;本篇主要来介绍关于文本的属性。 是的&#xff0c;文本也有属性。这里的文本属性有点类似于Word中的文字属性&#xff0c;文本中对应的字符只是文本属性的一种&#xff0c;它还包括文本大小、字体、颜色等等内容。…

基于python+django+vue.js开发的医院门诊管理系统/医疗管理系统源码+运行

功能介绍 平台采用B/S结构&#xff0c;后端采用主流的Python语言进行开发&#xff0c;前端采用主流的Vue.js进行开发。源码 功能包括&#xff1a;医生管理、科室管理、护士管理、住院管理、药品管理、用户管理、日志管理、系统信息模块。 源码地址 https://github.com/geee…

【leetcode100】全排列Ⅱ

1、题目描述 给定一个可包含重复数字的序列 nums &#xff0c;按任意顺序 返回所有不重复的全排列。 示例 1&#xff1a; 输入&#xff1a;nums [1,1,2] 输出&#xff1a; [[1,1,2],[1,2,1],[2,1,1]] 2、初始思路 2.1 思路 避免重复子集&#xff0c;可以使用used保存同层…

【训练细节解读】文本智能混合分块(Mixtures of Text Chunking,MoC)引领RAG进入多粒度感知智能分块阶段

喜欢本文可以在主页订阅专栏哟 核心创新&#xff1a;双重评估指标与混合分块架构&#xff1a; 第一章&#xff1a;检索增强生成&#xff08;RAG&#xff09;技术演进与分块挑战 1.1 RAG架构的核心演变 检索增强生成&#xff08;Retrieval-Augmented Generation&#xff09…

Linux 快捷键 | 终端快捷键 / 键盘快捷键

注&#xff1a;本文为 “Linux 快捷键” 相关文章合辑。 英文引文&#xff0c;机翻未校。 未整理去重。 Linux 终端常用快捷键 组合键 ~~~~~~~ 功能描述Ctrl a光标移动到行首&#xff08;Ahead of line&#xff09;&#xff0c;相当于通常的 Home 键Ctrl b光标往回 (Back…

Alembic 实战指南:快速入门到FastAPI 集成

一、快速开始 1.1 简介 Alembic 是一个基于 SQLAlchemy 的数据库迁移工具&#xff0c;主要用于管理数据库模式&#xff08;Schema&#xff09;的变更&#xff0c;例如新增表、修改字段、删除索引等&#xff0c;确保数据库结构与应用程序的 ORM 模型保持一致。 Alembic 通过版…

【开源代码解读】AI检索系统R1-Searcher通过强化学习RL激励大模型LLM的搜索能力

关于R1-Searcher的报告&#xff1a; 第一章&#xff1a;引言 - AI检索系统的技术演进与R1-Searcher的创新定位 1.1 信息检索技术的范式转移 在数字化时代爆发式增长的数据洪流中&#xff0c;信息检索系统正经历从传统关键词匹配到语义理解驱动的根本性变革。根据IDC的统计…

我的创作纪念日 打造高效 Python 日记本应用:从基础搭建到功能优化全解析

不知不觉&#xff0c;在 CSDN 写博客已经有 5 年的时间了。这 5 年&#xff0c;就像一场充满惊喜与挑战的奇妙旅程&#xff0c;在我的成长之路上留下了深深浅浅的印记。到现在我的博客数据&#xff1a; 展现量92万阅读量31万粉丝数2万文章数200 这样的数据是我在写第一篇博客…