首页 > 编程语言 >各排序算法及其时间复杂度比较

各排序算法及其时间复杂度比较

时间:2024-09-08 17:02:25浏览次数:12  
标签:arr int 复杂度 ++ 算法 printf 排序

排序算法及其时间复杂度比较

在C语言中,排序算法是常见的算法之一,用于将一组数据按照一定顺序排列。下面我将简要介绍几种常见排序算法的时间复杂度,并给出每种排序算法的C语言代码示例。

1. 插入排序(Insertion Sort)

时间复杂度

  • 平均和最坏情况:O(n^2)
  • 最好情况:O(n)(当输入数组已经排序时)

代码示例

#include <stdio.h>  
 
void printArray(int arr[], int size) {  
    int i;  
    for (i = 0; i < size; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
}  

void insertionSort(int arr[], int n) {  
    int i, key, j;  
    for (i = 1; i < n; i++) {  
        key = arr[i];  
        j = i - 1;  
  
        /* 将arr[i]插入到已排序的序列arr[0..i-1]中的正确位置 */  
        while (j >= 0 && arr[j] > key) {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
        printArray(arr, n);
    }  
}  

// 测试代码  
int main() {  
    int arr[] = {12, 11, 13, 5, 6};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    insertionSort(arr, n);  
    printf("Sorted array: \n");  
    for (int i = 0; i < n; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
    return 0;  
}

2. 选择排序(Selection Sort)

时间复杂度

  • 平均、最好、最坏情况:O(n^2)

代码示例

#include <stdio.h>  
 

void printArray(int arr[], int size) {  
    int i;  
    for (i = 0; i < size; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
}  

void selectionSort(int arr[], int n) {  
    int i, j, min_idx, temp;  
  
    for (i = 0; i < n-1; i++) {  
        // 寻找[i, n-1]区间的最小值的索引下标  
        min_idx = i;  
        for (j = i+1; j < n; j++)  
          if (arr[j] < arr[min_idx])  
            min_idx = j;  
  
        // 交换找到的最小元素与第i个元素  
        temp = arr[min_idx];  
        arr[min_idx] = arr[i];  
        arr[i] = temp;
         printArray(arr, n);
    }  
}  
  
// 测试代码  
int main() {  
    int arr[] = {12, 11, 13, 5, 6,7,8};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    selectionSort(arr, n);  
    printf("Sorted array: \n");  
    for (int i = 0; i < n; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
    return 0;  
}

3. 冒泡排序(Bubble Sort)

时间复杂度

  • 平均和最坏情况:O(n^2)
  • 最好情况:O(n)(当输入数组已经排序时)

代码示例

#include <stdio.h>  
 
void printArray(int arr[], int size) {  
    int i;  
    for (i = 0; i < size; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
}  

void bubbleSort(int arr[], int n) {  
    int i, j, temp;  
    for (i = 0; i < n-1; i++) {  
        for (j = 0; j < n-i-1; j++) {  
            if (arr[j] > arr[j+1]) {  
                temp = arr[j];  
                arr[j] = arr[j+1];  
                arr[j+1] = temp;  
            }  
        }
         printArray(arr, n);
    }
    
}  
  
// 测试代码  
int main() {  
    int arr[] = {10, 14, 11, 5, 6,7,8};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    bubbleSort(arr, n);  
    printf("Sorted array: \n");  
    for (int i = 0; i < n; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
    return 0;  
}

4. 希尔排序(Shell Sort)

时间复杂度

  • 平均:取决于增量序列,O(nlogn)到O(n^2)
  • 最坏情况:O(n^s),其中s是所选用的增量序列中最大的增量

代码示例(使用简单的增量序列):

#include <stdio.h>  


void printArray(int arr[], int size) {  
    int i;  
    for (i = 0; i < size; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
}  

void shellSort(int arr[], int n) {  
    for (int gap = n/2; gap > 0; gap /= 2) {  
        for (int i = gap; i < n; i += 1) {  
            int temp = arr[i];  
            int j;  
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {  
                arr[j] = arr[j - gap];  
            }  
            arr[j] = temp;  
        }  
         printArray(arr, n);
    }  
}  
  

// 测试代码  
int main() {  
    int arr[] = {11, 13, 12, 1, 3,9,8};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    shellSort(arr, n);  
    printf("Sorted array: \n");  
    for (int i = 0; i < n; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
    return 0;  
}

5. 快速排序(Quick Sort)

时间复杂度

  • 平均:O(n log n)
  • 最好情况:O(n log n)
  • 最坏情况:O(n^2)(当输入数组已经排序时)

代码示例(使用递归):

#include <stdio.h>  
  
void swap(int *xp, int *yp) {  
    int temp = *xp;  
    *xp = *yp;  
    *yp = temp;  
}  
  
int partition(int arr[], int low, int high) {  
    int pivot = arr[high];    // 选择最后一个元素作为基准  
    int i = (low - 1);        // 较小元素的索引  
    for (int j = low; j <= high - 1; j++) {  
        // 如果当前元素小于或等于基准  
        if (arr[j] <= pivot) {  
            i++;    // 增加较小元素的索引  
            swap(&arr[i], &arr[j]);  
        }  
    }  
    swap(&arr[i + 1], &arr[high]);  
    return (i + 1);  
}  
  
void quickSort(int arr[], int low, int high) {  
    if (low < high) {  
        /* pi 是分区后基准的正确位置 */  
        int pi = partition(arr, low, high);  
  
        // 递归地对基准前后的子数组进行排序  
        quickSort(arr, low, pi - 1);  
        quickSort(arr, pi + 1, high);  
    }  
}  
  
// 实用函数,用于打印数组  
void printArray(int arr[], int size) {  
    int i;  
    for (i = 0; i < size; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
}  
  
// 测试快速排序  
int main() {  
    int arr[] = {10, 7, 8, 9, 1, 5};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    quickSort(arr, 0, n - 1);  
    printf("Sorted array: \n");  
    printArray(arr, n);  
    return 0;  
}

6. 归并排序(Merge Sort)

时间复杂度

  • 平均、最好、最坏情况:O(n log n)

代码示例(使用递归):

#include <stdio.h>  
#include <stdlib.h>  
  
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];  
  
    // 合并临时数组回到原数组arr[l..r]  
    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++;  
    }  
  
    // 拷贝L[]的剩余元素  
    while (i < n1) {  
        arr[k] = L[i];  
        i++;  
        k++;  
    }  
  
    // 拷贝R[]的剩余元素  
    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);  
    }  
}  
  
// 实用函数,用于打印数组  
void printArray(int arr[], int size) {  
    int i;  
    for (i = 0; i < size; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
}  
  
// 测试归并排序  
int main() {  
    int arr[] = {12, 11, 13, 5, 6, 7};  
    int arr_size = sizeof(arr) / sizeof(arr[0]);  
  
    printf("Given array is \n");  
    printArray(arr, arr_size);  
  
    mergeSort(arr, 0, arr_size - 1);  
  
    printf("\nSorted array is \n");  
    printArray(arr, arr_size);  
    return 0;  
}

在上述的几种排序算法中,各排序算法在各种情况中,运行时间的快慢都不一样,而在其中相较于一般情况,归并列算法相当于有不错的表现,而对于各时间复杂度下的快慢,本人列了一张表格,由快到慢(表格由上至下)如图表所示,所以在不同的数据处理场景中可以相对数据以及各硬件速度选择不同的排序算法,以达到程序的最优解。

理解和分析算法的时间复杂度是算法设计、优化和选择中的重要环节。通过比较不同算法的时间复杂度,我们可以评估它们在处理大规模数据时的效率和可行性。

名称 时间复杂度
常数时间 O(1)
对数时间 O( log n)
线性时间 O(n )
线性对数时间 O(n log n)
二次时间 O(n^2)
三次时间 O(n^3)
指数时间 O(2^n)

标签:arr,int,复杂度,++,算法,printf,排序
From: https://www.cnblogs.com/zkbklink/p/18403133

相关文章

  • Java 面试题:Java的垃圾收集算法 --xunznux
    文章目录标记算法可达性分析算法标记算法的基本流程:标记算法的特点:标记算法的局限性:标记算法的优化:结论:1.标记-清除算法(Mark-Sweep)基本原理:优点:缺点:2.复制算法(Copying)核心思想基本原理:优点:缺点:3.标记-整理算法(Mark-Compact)基本原理:优点:缺点:4.分代收集算法(Genera......
  • 算法-动态规划-其他
    1.打家劫舍(LeetCode)你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警......
  • 代码随想录算法训练营第九天 | Javascript | 力扣Leetcode | 手撕KMP的一天 | 28. 找
    目录前言简介题目链接:28.找出字符串中第一个匹配项的下标题目链接:459.重复的子字符串前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,算法基础只有力扣几十道题,非常薄弱。......
  • 一种基于YOLOv8的高精度PCB缺陷检测算法(原创自研)
      ......
  • 算法专题一: 双指针
    目录前言1.移动零(easy)2.复写零(easy)3.快乐数(medium)4.盛水最多的容器(medium)5.有效三角形的个数(medium)6.和为s的两个数字(easy)7.三数之和(medium)8.四数之和(medium)前言常见的双指针有两种形式,一种是对撞指针,一种是左右指针。1.对撞指针:⼀般用于顺序结构中,也......
  • 信息学奥赛初赛天天练-86-NOIP2014普及组-基础题5-球盒问题、枚举算法、单源最短路、D
    1NOIP2014普及组基础题521把M个同样的球放到N个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放置方法?(用K表示)()例如,M=7,N=3时,K=8;在这里认为(5,1,1)和(1,5,1)是同一种放置方法。问:M=8,N=5时,K=()22如图所示,图中每条边上的数字表示该边的长度,则从......
  • 信息学奥赛初赛天天练-86-NOIP2014普及组-基础题5-球盒问题、枚举算法、单源最短路、D
    信息学奥赛初赛天天练-86-NOIP2014普及组-基础题5-球盒问题、枚举算法、单源最短路、Dijkstra算法、Bellman-Ford算法PDF文档公众号回复关键字:202409081NOIP2014普及组基础题521把M个同样的球放到N个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放置方法?(......
  • 算法入门-深度优先搜索2
    第六部分:深度优先搜索104.二叉树的最大深度(简单)题目:给定一个二叉树root,返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例1:输入:root=[3,9,20,null,null,15,7]输出:3示例2:输入:root=[1,null,2]输出:2第一种思路:感觉递......
  • 马老师浑元十三刀本质是DDD程序=算法+数据结构:浑元形意太极的本质是领域驱动设计(02)
    浑元形意太极的本质是领域驱动设计(01)在软件开发的旅程中,领域驱动设计就是我们的指路明灯。它照亮了我们前进的道路,驱散了迷茫的阴霾。有了领域驱动设计的指引,我们不再畏惧未知,不再害怕挑战。我们知道,无论前方有多么艰难的障碍,都有领域驱动设计为我们指明方向。领域驱动设计就......
  • Java中的五种排序
    五种排序常见的排序算法有十种:三大基础排序:选择、冒泡、插入(时间复杂度:O(n^2),空间复杂度(O(1))比较低)使用的是最基本的两层嵌套结构快速、归并、堆、希尔、桶、计数、基数排序:1)升序:从小到大2)降序:从大到小1、冒泡排序法冒泡排序是一种简单排序算法,它通过以此比较交换两......