C语言常用排序算法

C语言经典算法大全1.冒泡排序算法冒泡排序是一种简单但低效的排序算法，它通过多次遍历列表，比较相邻元素并交换位置，直到整个列表有序。

冒泡排序的时间复杂度为O(n^2)。

```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;}}}```2.选择排序算法选择排序是一种简单但高效的排序算法，它通过多次遍历列表，找到最小元素并将其放置在正确的位置上。

选择排序的时间复杂度也为O(n^2)。

```void selectionSort(int arr[], int n)int minIndex, temp;for (int i = 0; i < n-1; i++)minIndex = i;for (int j = i+1; j < n; j++)if (arr[j] < arr[minIndex])minIndex = j;}}//交换元素temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}```3.插入排序算法插入排序是一种简单但高效的排序算法，它通过将未排序的元素插入到已排序的列表中，逐步构建排序好的列表。

插入排序的时间复杂度为O(n^2)。

```void insertionSort(int arr[], int n)int i, key, j;for (i = 1; i < n; i++)key = arr[i];j=i-1;while (j >= 0 && arr[j] > key)arr[j + 1] = arr[j];j=j-1;}arr[j + 1] = key;}```4.快速排序算法快速排序是一种高效的排序算法，它通过选择一个主元，将列表分割为两个子列表，其中一个子列表的所有元素都小于主元，另一个子列表的所有元素都大于主元。

C语言常用算法概述C语言作为一种通用的高级编程语言，广泛应用于计算机科学领域，特别是在算法和数据结构方面。

C语言提供了许多常用算法，这些算法能够解决各种计算问题，并提供了高效的解决方案。

本文将概述C语言中常用的算法，包括排序算法、查找算法和图算法。

一、排序算法排序算法是将一组元素按照特定的顺序排列的算法。

C语言提供多种排序算法，下面将介绍几种常用的排序算法。

1. 冒泡排序冒泡排序是一种简单的排序算法，它通过多次遍历数组，每次比较相邻的两个元素，将较大的元素向后移动。

通过多次遍历，最大的元素会逐渐“冒泡”到数组的末尾。

2. 插入排序插入排序是一种稳定的排序算法，它通过将数组分为已排序和未排序两部分，将未排序的元素逐个插入已排序的部分，使得整个数组逐渐有序。

3. 快速排序快速排序是一种高效的排序算法，它通过选择一个基准元素，将数组分成两个子数组，其中一个子数组中的元素都小于基准，另一个子数组中的元素都大于基准。

然后递归地对两个子数组进行排序。

4. 归并排序归并排序是一种稳定的排序算法，它通过将数组划分为多个子数组，然后将这些子数组逐个合并，最终得到有序的数组。

归并排序使用了分治的思想，对子数组进行递归排序。

二、查找算法查找算法用于在一个集合中寻找特定元素的算法。

C语言提供了多种查找算法，下面将介绍两种常用的查找算法。

1. 顺序查找顺序查找是一种简单的查找算法，它通过逐个比较集合中的元素，直到找到需要查找的元素或者遍历完整个集合。

2. 二分查找二分查找是一种高效的查找算法，它要求集合必须有序。

它通过将集合分成两半，然后比较需要查找的元素与中间元素的大小关系，从而确定下一步查找的范围。

三、图算法图算法用于解决图结构相关的计算问题。

C语言提供了多种图算法，下面将介绍两种常用的图算法。

1. 深度优先搜索深度优先搜索是一种用于遍历或搜索图的算法，它通过从一个顶点出发，依次访问与该顶点相邻的未访问过的顶点。

当无法再继续访问时，回退到上一个顶点继续搜索。

C语言常用算法总结1、冒泡排序算法：冒泡排序是一种简单的排序算法，它重复地遍历要排序的序列，一次比较两个相邻的元素如果他们的顺序错误就把他们交换过来。

时间复杂度为O(n^2)。

2、快速排序算法：快速排序是一种基于分治的排序算法，通过递归的方式将数组划分为两个子数组，然后对子数组进行排序最后将排好序的子数组合并起来。

时间复杂度为O(nlogn)。

3、插入排序算法：插入排序是一种简单直观的排序算法，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描找到相应位置并插入。

时间复杂度为O(n^2)。

4、选择排序算法：选择排序是一种简单的排序算法，每次循环选择未排序部分的最小元素，并放置在已排序部分的末尾。

时间复杂度为O(n^2)。

5、归并排序算法：归并排序是一种稳定的排序算法，基于分治思想，将数组递归地分为两个子数组，将子数组排序后再进行合并最终得到有序的数组。

时间复杂度为O(nlogn)。

6、堆排序算法：堆排序是一种基于完全二叉堆的排序算法，通过构建最大堆或最小堆，然后依次将堆顶元素与末尾元素交换再调整堆，得到有序的数组。

时间复杂度为O(nlogn)。

7、二分查找算法：二分查找是一种在有序数组中查找目标元素的算法，每次将待查找范围缩小一半，直到找到目标元素或范围为空。

时间复杂度为O(logn)。

8、KMP算法：KMP算法是一种字符串匹配算法，通过利用模式字符串的自重复性，避免不必要的比较提高匹配效率。

时间复杂度为O(m+n)，其中m为文本串长度，n为模式串长度。

9、动态规划算法：动态规划是一种通过将问题分解为子问题，并通过组合子问题的解来求解原问题的方法。

动态规划算法通常使用内存空间来存储中间结果，从而避免重复计算。

时间复杂度取决于问题规模。

10、贪心算法：贪心算法是一种通过选择局部最优解来构建全局最优解的算法并以此构建最终解。

时间复杂度取决于问题规模。

11、最短路径算法：最短路径算法用于求解图中两个节点之间的最短路径，常见的算法包括Dijkstra算法和Floyd-Warshall算法。

使⽤C语⾔实现12种排序⽅法⽬录1.冒泡排序2.插⼊排序3.折半插⼊排序4.希尔排序5.选择排序6.鸡尾酒排序7.堆排序8.快速排序9.归并排序10.计数排序11.桶排序12.基数排序1.冒泡排序思路：⽐较相邻的两个数字，如果前⼀个数字⼤，那么就交换两个数字，直到有序。

时间复杂度O(n^2)，稳定性：这是⼀种稳定的算法。

代码实现：void bubble_sort(int arr[],size_t len){size_t i,j;for(i=0;i<len;i++){bool hasSwap = false; //优化，判断数组是否已经有序，如果有序可以提前退出循环for(j=1;j<len-i;j++){ //这⾥j<len-i是因为最后⾯的肯定都是最⼤的，不需要多进⾏⽐较if(arr[j-1]>arr[j]){ //如果前⼀个⽐后⼀个⼤swap(&arr[j-1],&arr[j]); //交换两个数据hasSwap = true;}}if(!hasSwap){break;}}}2.插⼊排序思路：把⼀个数字插⼊⼀个有序的序列中，使之仍然保持有序，如对于需要我们进⾏排序的数组，我们可以使它的前i个数字有序，然后再插⼊i+1个数字，插⼊到合适的位置使之仍然保持有序，直到所有的数字有序。

时间复杂度：O(n^2) 稳定性：稳定的算法代码实现：void insert_sort(int arr[],int len){int i,j;for(i=1;i<len;i++){int key = arr[i]; //记录当前需要插⼊的数据for(j= i-1;i>=0&&arr[j]>key;j--){ //找到插⼊的位置arr[j+1] = arr[j]; //把需要插⼊的元素后⾯的元素往后移}arr[j+1] = key; //插⼊该元素}}3.折半插⼊排序思路：本质上是插⼊排序，但是通过半分查找法找到插⼊的位置，让效率稍微快⼀点。

C语⾔⼋⼤排序算法C语⾔⼋⼤排序算法，附动图和详细代码解释！来源：C语⾔与程序设计、⽵⾬听闲等⼀前⾔如果说各种编程语⾔是程序员的招式，那么数据结构和算法就相当于程序员的内功。

想写出精炼、优秀的代码，不通过不断的锤炼，是很难做到的。

⼆⼋⼤排序算法排序算法作为数据结构的重要部分，系统地学习⼀下是很有必要的。

1、排序的概念排序是计算机内经常进⾏的⼀种操作，其⽬的是将⼀组“⽆序”的记录序列调整为“有序”的记录序列。

排序分为内部排序和外部排序。

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

反之，若参加排序的记录数量很⼤，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

2、排序分类⼋⼤排序算法均属于内部排序。

如果按照策略来分类，⼤致可分为：交换排序、插⼊排序、选择排序、归并排序和基数排序。

如下图所⽰：3、算法分析1.插⼊排序*直接插⼊排序*希尔排序2.选择排序*简单选择排序*堆排序3.交换排序*冒泡排序*快速排序4.归并排序5.基数排序不稳定排序：简单选择排序，快速排序，希尔排序，堆排序稳定排序：冒泡排序，直接插⼊排序，归并排序，奇数排序1、插⼊排序将第⼀个和第⼆个元素排好序，然后将第3个元素插⼊到已经排好序的元素中，依次类推（插⼊排序最好的情况就是数组已经有序了）因为插⼊排序每次只能操作⼀个元素，效率低。

元素个数N，取奇数k=N/2，将下标差值为k的数分为⼀组（⼀组元素个数看总元素个数决定），在组内构成有序序列，再取k=k/2，将下标差值为k的数分为⼀组，构成有序序列，直到k=1，然后再进⾏直接插⼊排序。

3、简单选择排序选出最⼩的数和第⼀个数交换，再在剩余的数中⼜选择最⼩的和第⼆个数交换，依次类推4、堆排序以升序排序为例，利⽤⼩根堆的性质（堆顶元素最⼩）不断输出最⼩元素，直到堆中没有元素1.构建⼩根堆2.输出堆顶元素3.将堆低元素放⼀个到堆顶，再重新构造成⼩根堆，再输出堆顶元素，以此类推5、冒泡排序改进1：如果某次冒泡不存在数据交换，则说明已经排序好了，可以直接退出排序改进2：头尾进⾏冒泡，每次把最⼤的沉底，最⼩的浮上去，两边往中间靠16、快速排序选择⼀个基准元素，⽐基准元素⼩的放基准元素的前⾯，⽐基准元素⼤的放基准元素的后⾯，这种动作叫分区，每次分区都把⼀个数列分成了两部分，每次分区都使得⼀个数字有序，然后将基准元素前⾯部分和后⾯部分继续分区，⼀直分区直到分区的区间中只有⼀个元素的时候，⼀个元素的序列肯定是有序的嘛，所以最后⼀个升序的序列就完成啦。

C语言常用排序算法/************************************************************************************** ******平方阶(O(n2))排序一般称为简单排序，例如直接插入、直接选择和冒泡排序*************************************************************************************** *****//*插入排序*/extern int InsertSort(int source[], int array_size){int index = 1; //插入排序int i, j;for (i = 1; i < array_size; i++){index = source[i];j = i;while ((j > 0) && (source[j - 1] > index)){source[j] = source[j - 1];j--;}source[j] = index;}return 1;}/*冒泡排序*/extern int BubbleSort(int source[], int array_size){int i, j;int temp;for (i = 0; i < array_size; i++){for (j = 0; j < array_size - i - 1; j++)if (source[j] > source[j + 1]){temp = source[j];source[j] = source[j + 1];source[j + 1] = temp;}}return 1;}/*选择排序*/extern int SelectSort(int source[], int array_size){int temp, min;int i, j;for (i = 0; i < array_size; i++){min = i;//先假设最小下标为ifor (j = i + 1; j < array_size; j++)if (source[j] < source[min])min = j;//把i之后的最小值附给minif (min != i){temp = source[i];source[i] = source[min];source[min] = temp;}//判断min与i是否相等,若相等则说明原假设正确,反之:交换数值}return 1;}/************************************************************************************** *******线性对数阶(O(nlgn))排序如快速、堆和归并排序*************************************************************************************** *****//*快速排序接口*/static int Partition(int source[], int left, int right)int x = source[left];while (left < right){while (left < right && x <= source[right])right--;source[left] = source[right];while (left < right && x >= source[left])left++;source[right] = source[left];}source[left] = x;return left;}extern int QuickSort(int source[], int left, int right){int iPos;if (left >= right)return 1;iPos = Partition(source, left, right);QuickSort(source, left, iPos - 1); // 左边划分QuickSort(source, iPos + 1, right); // 右边划分return 1;}/*堆排序*/static void HeapAdjust(int source[], int root, int node)/*root根节点, node节点总数*/ {//已知source[root..node]中除source[root]之外均满足堆的定义,本函数调整source[root] //使source[root..node]成为一个大顶堆int j, rc;rc = source[root];for (j = 2 * root; j <= node; j *= 2) //沿关键字叫大的结点向下筛选{if (j < node && source[j] < source[j + 1])++j; //j为关键字较大的记录的下标if (rc >= source[j])break; //rc应插入在位置root上source[root] = source[j];root = j;}source[root] = rc; //插入extern int HeapSort(int source[], int array_size){int i, t;for (i = array_size / 2; i > 0; --i)//把a[1..L.length]建成大顶堆HeapAdjust(source, i, array_size);for (i = array_size; i > 1; --i){t = source[1]; //将堆顶记录和当前未经排序子序列a[1..i]source[1] = source[i]; //中的最后一个记录相互交换source[i] = t;HeapAdjust(source, 1, i - 1); //将r[1..i-1]重新调整为大顶堆}return 1;}/************************************************************************************** ********O(n1+￡)阶排序￡是介于0和1之间的常数，即0<￡<1，如希尔排序*************************************************************************************** *****//*希儿排序*/extern int ShellSort(int source[], int array_size){int increament;int e, i, j;/*初始步长设为n/2*/for (increament = array_size / 2; increament > 0; increament = increament / 2) for (j = increament; j < array_size; j++){if (source[j] < source[j - increament]){e = source[j];for (i = j - increament; i >= 0 && source[i] > e; i = i - increament) source[i + increament] = source[i];source[i + increament] = e;}}return 1;。

C语言常用算法大全1.排序算法-冒泡排序：依次比较相邻的两个元素，如果顺序不对则交换，每轮找出一个最大或最小的元素-选择排序：从未排序的元素中选择最小或最大的放到已排序的最后，以此类推-插入排序：将未排序的元素插入到已排序的合适位置，从后向前进行比较和交换-快速排序：选择一个基准元素，将小于基准元素的放在左边，大于基准元素的放在右边，然后对左右两边递归地进行快速排序-归并排序：将待排序的序列不断划分为左右两部分，分别排序后再将排序好的左右两部分按顺序合并-堆排序：构建大顶堆，将堆顶元素与末尾元素交换，然后重新调整堆，重复这个过程直到排序完成2.查找算法-顺序查找：从给定的元素序列中逐个比较，直到找到目标元素或遍历完整个序列-二分查找：对于有序序列，在序列的中间位置比较目标元素和中间元素的大小关系，通过每次缩小一半的范围来查找目标元素-插值查找：根据目标元素与有序序列的最小值和最大值的比例推测目标元素所在的位置，然后递归地进行查找-斐波那契查找：根据斐波那契数列的性质来确定目标元素所在的位置，然后递归地进行查找3.图算法-深度优先（DFS）：从图的一些顶点出发，依次访问其未被访问过的邻接顶点，直到所有顶点都被访问过为止-广度优先（BFS）：从图的一些顶点出发，逐层遍历图的顶点，直到所有顶点都被访问过为止- 最小生成树算法：Prim算法和Kruskal算法，用于找到连接图中所有顶点的最小权值边，构成一棵包含所有顶点的生成树- 最短路径算法：Dijkstra算法和Floyd-Warshall算法，用于找到图中两个顶点之间的最短路径-拓扑排序：用于有向无环图（DAG）中的顶点排序，确保排序后的顶点满足所有依赖关系-关键路径算法：找出网络中的关键路径，即使整个工程完成的最短时间4.字符串算法- KMP算法：通过预处理模式串构建next数组，利用next数组在匹配过程中跳过一部分不可能匹配的子串- Boyer-Moore算法：从模式串的末尾开始匹配，利用坏字符和好后缀规则进行跳跃匹配- Rabin-Karp算法：利用哈希函数对主串和匹配串的子串进行哈希计算，然后比较哈希值是否相等- 字符串匹配算法：BM算法、Shift-And算法、Sunday算法等，用于寻找模式串在主串中的出现位置5.动态规划算法-最长公共子序列（LCS）：用于寻找两个序列中最长的公共子序列-最长递增子序列（LIS）：用于寻找给定序列中最长的递增子序列-0-1背包问题：将有限的物品放入容量为C的背包中，使得物品的总价值最大-最大子数组和：用于求解给定数组中连续子数组的最大和-最大正方形：在给定的0-1矩阵中，找出只包含1的最大正方形的边长这些算法是在C语言中常用的算法，它们涵盖了排序、查找、图、字符串和动态规划等多个领域。

常用的c语言排序算法主要有三种即冒泡法排序、选择法排序、插入法排序。

一、冒泡排序冒泡排序：是从第一个数开始，依次往后比较，在满足判断条件下进行交换。

代码实现（以降序排序为例）#include<stdio.h>int main(){int array[10] = { 6,9,7,8,5,3,4,0,1,2 };int temp;for (int i = 0; i < 10; i++){//循环次数for (int j = 0; j <10 - i-1; j++){if (array[j] < array[j+1]){//前面一个数比后面的数大时发生交换temp = array[j];array[j] = array[j+1];array[j + 1] = temp;}}} //打印数组for (int i = 0; i < 10; i++) printf("%2d", array[i]); return 0;}}二、选择排序以升序排序为例：就是在指定下标的数组元素往后（指定下标的元素往往是从第一个元素开始，然后依次往后），找出除指定下标元素外的值与指定元素进行对比，满足条件就进行交换。

与冒泡排序的区别可以理解为冒泡排序是相邻的两个值对比，而选择排序是遍历数组，找出数组元素与指定的数组元素进行对比。

（以升序为例）#include<stdio.h>int main(){int array[10] = { 6,9,7,8,5,3,4,0,1,2 };int temp, index;for (int i = 0; i < 9; i++) {index = i;for (int j = i; j < 10; j++){if (array[j] < array[index])index = j;}if(i != index){temp = array[i]; array[i] = array[index]; array[index] = temp; }for(int i=0;i<10:i++) printf("%2d"array[i]）return 0；}三、快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

C语言经典算法大全精选1.排序算法1.1冒泡排序：通过不断交换相邻元素的位置，将最大（最小）值“冒泡”到序列的末尾（开头）。

1.2插入排序：将未排序的元素逐个插入已排序的序列中，保持序列始终有序。

1.3选择排序：每次从未排序的元素中选择最小（最大）的元素，放到已排序序列的末尾（开头）。

1.4快速排序：通过递归地将序列分割为较小和较大的两部分，然后分别对两部分进行排序。

1.5归并排序：将序列递归地分割为两个子序列，分别排序后再将结果合并。

1.6堆排序：构建最大（最小）堆，然后逐步将堆顶元素与最后一个元素交换，并调整堆结构。

2.查找算法2.1顺序查找：逐个比较元素，直到找到目标元素或遍历完整个序列。

2.2二分查找：在有序序列中，通过不断缩小查找范围，找到目标元素。

2.3插值查找：根据目标元素与序列中最大、最小元素的关系，按比例选择查找范围。

2.4哈希查找：利用哈希函数将目标元素映射到一个唯一的位置，从而快速定位目标元素。

3.字符串算法3.1字符串匹配算法：在文本串中查找给定的模式串，并返回匹配位置。

3.2字符串翻转：将一个字符串逆序输出。

3.3字符串压缩：将连续出现多次的字符压缩为一个字符，并输出压缩后的字符串。

3.4字符串拆分：按照指定的分隔符将字符串拆分为多个子串，并返回子串列表。

3.5字符串反转单词：将一个句子中的单词顺序逆序输出。

4.图算法4.1深度优先：从起始顶点出发，递归地访问所有能到达的未访问顶点。

4.2广度优先：从起始顶点出发，逐层地访问与当前层相邻的未访问顶点。

4.3最小生成树：找到连接所有顶点的具有最小权值的无环边集合。

4.4最短路径：找到两个顶点之间最短路径的权值和。

4.5拓扑排序：找到一个顶点的线性序列，满足所有有向边的起点在终点之前。

5.数学算法5.1质数判断：判断一个数是否为质数（只能被1和自身整除）。

5.2求最大公约数：找到两个数的最大公约数。

5.3求最小公倍数：找到两个数的最小公倍数。