c语言排序功能，c语言中排序的各种方法解析

引言如果说各种编程语言是程序员的技能，那么数据结构和算法就是程序员的内在技能。

想要写出简洁又好的代码，不经过不断的锤炼是很难做到的。

八种排序算法排序算法是数据结构的重要组成部分，必须系统学习。

1.排序的概念排序是计算机中常用的操作，其目的是将一组“无序”记录序列排列成“有序”记录序列。

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

如果整个排序过程无需访问外部存储器就能完成，则这种排序问题称为内部排序。

相反，如果参与排序的记录数量太大，以至于整个序列的排序过程无法在内存中完成，则此类排序问题称为外部排序。

2.排序的分类八种主要排序算法都属于内部排序。按策略分类，大致可分为交换排序、插入排序、选择排序、归并排序和基数排序。如下所示：

三、算法分析1、插入排序/直接插入排序

*希尔排序

2. 选择排序

*简单选择排序

*堆排序

3. 交易所排序

*冒泡排序

*快速排序

4. 归并排序

5.基数排序

不稳定排序：简单选择排序、快速排序、希尔排序、堆排序

稳定排序：冒泡排序、直接插入排序、归并排序、奇数排序

1.插入排序

对第一个和第二个元素进行排序，然后将第三个元素插入已排序的元素中，依此类推（插入排序的最佳情况是当数组已经排序时）。

2. 希尔排序

插入排序效率较低，因为它们一次只能对一个元素执行。对于元素个数N，取奇数k=N/2，将下标相差k的数分成组（组内元素个数由元素总数决定），将排序顺序写为如下： 形式。取一组中的一个序列，然后取k=k/2，将下标相差k的数字分组，形成有序序列，直到k=1，然后直接插入进行排序。

3.简单选择排序

选择最小的数字与第一个数字交换，然后选择剩余的最小数字与第二个数字交换。

4.堆排序

例如，升序排序利用根堆较小（堆顶元素最小）的特性，继续输出最小的元素，直到堆中不再有元素为止。

1. 构建一个小的根堆

2.输出堆的第一个元素。

3、从堆底往顶放置元素，重建成一个小根堆，然后从堆顶输出元素，以此类推。

5. 冒泡排序

改进1：如果在某个冒泡中没有数据交换，则说明排序完成，可以直接退出排序。

改进2：从头到尾鞭打，让较大的沉到底部，每次将较小的带到表面时，将两侧靠近中心1

6. 快速排序

选择参考元素。将小于参考元素的元素放置在参考元素之前，将大于参考元素的元素放置在参考元素之后。此操作将数组分成两部分。分区保持数字有序，并继续对引用元素之前和之后的部分进行分区，直到分区间隔内只剩下一个元素。因此，元素的序列必须是有序的，完成最终的升序。

7. 归并排序

将无序序列分成两部分，直到序列中只有一个数字。这通过合并仅包含一个数字的两个序列来创建一个有序的数字序列。这一直持续到你最终得到一个大的有序序列。

8. 基数排序

找到最大的数，打开一个比最大数稍大的数组，遍历每个元素。如果某个特定元素是k，那么a[k]++，那么最好遍历数组a，输出a[。 k]等于k。只能处理整数

下面提供了各种分类的具体分类描述。

1.直接插入排序（Insertion Sort）

算法思路：

直接插入排序的核心思想是按顺序将数组中的每个元素与之前放入的元素进行比较，如果所选元素小于已排序的元素，则比较所有元素，直到替换为止。这如果你看一下解释，你会发现直接插入排序可以在两个循环中完成。

第一级循环：遍历所有数组元素进行比较。

第二级循环：比较本轮选中（selected）的元素和排序（ordered）的元素。如果：选择已订购并交换两者。

算法代码：

void print(int a[], int n ,int i){ cout for(int j=0; j8; j++){ cout } cout} void InsertSort(int a[], int n){ for(int i=1 ; i if(a[i] a[i-1]){ //如果第i个元素大于i-1元素，则直接插入； int x ordered; 移动列表后。 ]; //作为哨兵复制，即存储要重新排序的元素a[i]=a[i-1] //按顺序移动一个元素while(x a[j]){ //在有序列表中搜索。插入位置a[j+1]=a[j] //向后移动元素} a[j+1]=x; //插入到正确的位置} print(a,n,i) //输出各结果排序}}int main{ int a[8]={3,1,5,7,2,4,9;6 }; 打印(a,8, 8);} 2.贝壳分选

算法思维：

希尔排序，也称为降序增量排序算法，是插入排序的更高效的改进版本。然而，希尔排序是一种不稳定的排序算法。

希尔排序的基本思想是，首先将整个待排序记录序列分割成若干个子序列进行直接插入排序，一旦整个序列中的记录处于“基本正确的顺序”，则进行直接插入排序在所有记录上。

算法步骤：

1. 选择增量序列t1、t2、tk。这里，titj,tk=1。

2、根据增量序列k的个数对序列进行k次排序。

3、在每次排序过程中，将待排序的列按照对应的增量ti分成若干个长度为m的子序列，对每个子表进行直接插入排序。只有当增量因子为1时，整个序列才被视为一个表，表的长度就是整个序列的长度。

算法代码：

void print(int a[], int n ,int i){ cout for(int j=0; j8; j++){ cout } cout}/** * 直接插入排序的一般形式* * @param int dk For shrin直接插入排序，增加数量。 dk=1 * */void ShellInsertSort(int a[], int n, int dk){ for(int i=dk; i if(a[i] a[i- dk]) { //第i个元素是如果大于i-1个元素，则直接插入；如果较小，则在移动有序列表后插入int j=i-dk; //将其重新排序，以便在a[i]中使用=a[i-dk] //向后移动一个元素while(x a[j]){ //查找有序列表中的插入位置a[j+dk]=a[j] ; //恢复元素} a[j+dk]=x; //插入到正确的位置n, i); //第一个增量d (n/2, n 是要排序的数字数量，执行希尔排序) void shellSort(int a[], int n){ int dk=n/2; while( dk=1 ){ ShellInsertSort(a, n, dk); int a[8]={3, 1,5,7,2,4,9,6; }; //ShellInsertSort(a,8,1); //直接插入排序shellSort (a,8); 3. 简单选择排序（Selection Sort）

算法思路：

简单选择排序实现思路：比较+交换

从要排序的序列中查找关键字最小的元素。

如果最小元素不是正在排序的序列的第一个元素，则将其替换为第一个元素。

从剩余的N-1个元素中，找到关键字最小的元素，重复步骤（1）和（2），直到排序完成。所以我们可以看到，简单的选择排序也是通过两级循环实现的。第一级循环：依次遍历序列中的每个元素。 第二级循环：将遍历中的当前元素与序列中的剩余元素进行比较。

算法代码：

void print(int a[], int n ,int i){ cout\\\’th\\\’ for(int j=0; j8; j++){ cout } cout}/** * 数组最小值* * @return int数组键值*/int SelectMinKey(int a[], int n, int i){ int k=i; for(int j=i+1;j n; ++j) { if(a[k] a[ j ]) k=j; } return k;}/** * 选择排序* */void selectSort(int a[], int n){ int key, tmp; +i ) { key=SelectMinKey(a, n, i ); //选择最小元素if(key !=i){ tmp=a[i]=a[key]; //将最小元素与第i 个元素交换} print(a , n, i) }}int a[8]={3,1,5,7,2,4, 9,6} ; cout\\\’初始值：\\\’; for(int j=0; j8; j++ ){ cout } cout selectSort(a,8,8);} 4. 堆排序

算法思路：

堆概念

堆：本质上是一个数组对象。一个特别重要的属性：每个叶节点都小于（或大于）其所有父节点。就此而言，它们分为大顶桩和小顶桩。

大顶堆要求节点的元素大于其子元素。

小顶堆要求节点元素小于其左子元素和右子元素。

两者都没有对孩子的体型提出要求。

堆排序是一种基于大顶堆或小顶堆的排序方法。然后通过一个大的顶堆来实现。

基本思想：堆排序可以通过以下步骤完成：

1、首先，序列的构建称为大顶堆（满足大顶堆的特性，即根节点处的元素必须是当前序列的最大值）。

2. 取出当前bigtop堆的根节点，并将其替换为序列的最后一个元素（其中序列的最后一个元素是排序后的最大值；当前位于根节点的堆元素不一定不满足特性一大堆顶部）

3、调整交换后的n-1个序列元素，以满足大顶堆的特性。

4. 重复步骤2.3，直到堆中只剩下一个元素。

下面是基于bigtop堆的堆排序算法的代码。

void print(int a[], int n){ for(int j=0; j cout } cout}/** * 除H[s] 之外的所有H[s.m] 满足以下定义已知heap* 将H [s] 调整为一个大的顶部堆* * @param H 是要调整的堆数组。 param s 是要调整的下一个数组元素* @param length 是数组的长度*/void HeapAdjust(int H[],int s, int length){ int tmp=H[s]; int child=2 *s+1; //左子节点的位置，i+1为右子节点的位置当前调整节点) while (child length) { if(child+1 ++child; } if (H[s] H[s]=H[child]; //则将较大的子节点向上移动并替换其父节点s=child //下一个要调整的节点的位置Reset s such that child=2*s+1 } else { //如果当前要调整的节点大于其左右子节点，则无需调整调整并退出break } H[s]=tmp; //当前要调整的节点放置在较大子节点的位置} print(H,length);}/** * 调整初始堆* H[ 0.length-1 ] 在堆上* 调整后是第一个元素序列中最小的元素*/void BuildingHeap(int H[], int length){ //最后一个有孩子的节点的位置i=( length -1)/2 for (int i=(length -1)/2; i=0; –i) HeapAdjust(H ,i,length);}/** * 堆排序算法*/void HeapSort(int H[],int length) { //初始堆BuildingHeap(H, length); //调整从最后一个元素开始的顺序for (int i=length – 1; i 0; –i) { //堆的第一个element H[0] 并交换堆中的最后一个元素int temp=H[i]=H[0]=temp; //每次将堆中的第一个元素与堆中的最后一个元素交换需要调整堆。 HeapAdjust(H,0,i); }} int main{ int H[10]={3,1,5,7,2,4,9,6,10,8}; //selectSort(a , 8); 5.冒泡排序（冒泡排序）

算法思路：

气泡遍历所有数据，每次都比较相邻元素。如果顺序与给定的顺序不匹配，则交换位置，将最大或最小的数据移动到顶部，重复相同的操作，直到所有数据都匹配。为了。该算法的名称来源于这样一个事实：较大的元素通过交换慢慢“浮动”到数组的开头。

算法代码：

void bubbleSort(int a[], int n){ for(int i=0; i n-1; ++i) { for(int j=0; j n-i-1; ++j) { if(a[ j] a[j+1]) { int tmp=a[j] ; a[j]=a[j+1] } }} 6. 快速排序

算法思路：

快速排序是托尼·霍尔（Tony Hall）开发的一种排序算法。平均而言，对n 个项目进行排序需要O(n logn) 次比较。在最坏的情况下，需要进行O(n2) 次比较，但这种情况并不常见。事实上，快速排序通常比其他(n log n) 算法快得多，因为内部循环可以在大多数架构上高效实现。

快速排序使用分而治之的策略将列表分成两个子列表。

算法步骤：

从序列中删除元素称为“枢轴”。

重新排序数组，以便所有小于基值的元素都放置在基值之前，所有大于基值的元素都放置在基值之后（两侧放置相同的数字即可）。在此分区的末尾，碱基位于序列的中间。这称为分区操作。

对小于基值的元素子数组和大于基值的元素子数组进行递归排序。

递归的最低情况是数组大小为0 或1 时，即数组始终已排序时。它继续递归，但在每次迭代时至少有一个元素移动到其最终位置，因此算法总是终止。

算法代码：

void print(int a[], int n){ for(int j=0; j cout } cout}void swap(int *a, int *b){ int tmp=*a; *a=*b; *b=tmp;}int Partition(int a[], int low, int high){ int privotKey=a[low]; //基本元素while(low high){ //从表两端向中心交替扫描while ( low high a[high]=privotKey) –high; //从high指定的位置向前搜索到low+1的位置，将小于基数的元素交换到低端swap(a[low ], a [high]); ++low(a[low], a[high]); } void 快速排序(int a [], int low, int high){ if(low high){ int privotLoc=Partition(a , low , high) //将表分成两个QuickSort(a, low, privotLoc -1); /Recursion 对下层子表递归排序QuickSort(a, privotLoc + 1, high) //对上层子表递归排序}}int main{ int a[10]={3,1,5,7,2,4,9 , 6,10,8}; cout\\\’初始值：\\\’;

算法思路：

归并排序是一种基于归并操作的有效排序算法。该算法是分而治之的一个非常典型的应用。

算法步骤：

应用空格，使大小为两个排序序列的总和。该空间用于存储合并序列。

设置两个指针。初始位置是两个排序序列的起始位置。

比较两个指针指向的元素，选择较小的元素，将其放入合并空间，并将指针移动到下一个位置。

重复步骤3，直到指针到达序列末尾。

将其他序列中的所有剩余元素直接复制到合并序列的末尾。

算法代码：

void print(int a[], int n){ for(int j=0; j cout } cout}//r[i…m] 和r[m +1…n] 合并到辅助数组rf[i…] 中n]void Merge(ElemType *r,ElemType *rf, int i, int m, int n){ int j,k; for(j=m+1,k=i; i=m j=n; ++k ) { if(r[j] r[i]) rf[k]=r[j++]; else rf[k]=r[i++] } while(i=m) rf[k++]=r[i++]; while(j=n) rf[k++]=r[j++]; print(rf,n+1);}void MergeSort(ElemType *r, ElemType *rf, int lenght){ int lenType * q=r ; len length) { int s=len=2 * s ; int i=1 ) ; //连接两个长度相同的子表i=i+ len; } if(i + s length){ Merge(q, rf, i, i+ s -1, length -1); 合并两个长度不等的子表} tmp=q; q=rf; //Next 即使在合并中也确保q 合并到rf 中。 }}int main{ int a[10 ]={ 3,1,5,7,2,4,9,6,10,8}; int b[10]; cout\\\’结果：\\\’ ;10);} 8.基数排序(Radix sort)

算法思路：

基数排序：排序是通过根据序列中每个元素的值对N 个已排序元素执行多次“分布”和“聚集”来实现的。

分配：取出L[i]中的元素，先找到其编号，然后根据该编号将其分配到具有相同序号的桶中。

集合：将序列中的所有元素分配到相应的桶中后，将桶中的元素集合起来形成新的已排序序列L。

它重复对新形成的序列L的数十个和数百个元素的分配和收集，直到分配了序列中的最高有效位，之后终止排序。

算法代码：

d RadixSort(Node L[],length,maxradix){ int m,n,k,lsp; k=1;m=1; //清除临时值。空间while(k { for(int i=0;i { if(L[i] Temp[0][n]=L[i]); else Lsp=(L[i]/m)%10; //OK 关键字Temp[lsp][n]=L[i]; } CollectElement(L,Temp); //m=m*10;

使用Python实现1.冒泡排序

冒泡排序算法的工作原理如下。

比较相邻元素。如果第一个大于第二个，则更换两个。

对每对相邻元素执行相同的操作，从第一对开始，到最后一对结束。一旦这一步完成，最后一个元素将是最大的数字。

对除最后一个元素之外的所有元素重复上述步骤。

重复上述步骤，减少元素数量，直到不再有可比较的数字对。

以上摘自维基百科

代码：

def bubble_sort(numberlist): length=len(numberlist) for i in range(length): for j in range(1, length – i): ifnumberlist[j – 1]numberlist[j]:numberlist[j],numberlist [j – 1]=数字列表[j – 1],数字列表[j] 返回数字列表2.排序选择范围

选择排序是一种简单直观的排序算法。它的工作原理如下：首先，找到未排序序列中最小（最大）的元素并将其存储在已排序序列的开头。然后从剩余的未排序元素中找到最小（最大）的元素，并将其放在已排序序列的末尾。已排序的序列。继续下去，直到所有元素都排序完毕。

以上摘自维基百科

代码：

def findSmallest(arr): # 用于查找数组中的最小元素并返回最小元素的索引。最小=arr[0] 最小索引=0 for i in range(1, len(arr)): 如果最小arr[i]: 最小=arr[i] 最小索引=i 返回最小索引def selectSort(arr): newArr=while arr: 最小=findSmallest(arr) newArr.append(arr.pop(smallest)) return newArr 3.插入排序

步骤如下：

从第一个元素开始，可以认为元素已排序。

取出下一个元素，从后向前扫描已排序的元素序列。

如果（已排序的）元素大于新元素，则将该元素移动到下一个位置。

重复步骤3，直到找到重新排序的元素小于或等于新元素的位置。

在该位置插入新元素后

重复步骤2-5

以上摘自维基百科

代码实现：

def insert_sort(data): for k in range(1, len(data)): cur=data[k] j=k while j 0 and data[j – 1] cur: data[j]=data[j – 1] j -=1 data[j]=cur 返回数据4. 希尔排序

爬坡道

排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
以上节选自维基百科
代码实现：
def shell_sort(numberlist): length = len(numberlist) gap = length // 2 while gap > 0: for i in range(gap, length): temp = numberlist[i] j = i while j >= gap and numberlist[j – gap] > temp: numberlist[j] = numberlist[j – gap] j -= gap numberlist[j] = temp gap = gap // 2 return numberlist五、归并排序
原理如下（假设序列共有{displaystyle n}个元素）：
● 将序列每相邻两个数字进行归并操作，形成{displaystyle ceil(n/2)}个序列，排序后每个序列包含两/一个元素
● 若此时序列数不是1个则将上述序列再次归并，形成{displaystyle ceil(n/4)}个序列，每个序列包含四/三个元素
● 重复步骤2，直到所有元素排序完毕，即序列数为1
以上节选自维基百科
代码如下：
def merge(left, right): result = while left and right: if left[0] < right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)) if left: result += left if right: result += right return resultdef merge_sort(numberlist): if len(numberlist) <= 1: return numberlist mid = len(numberlist) // 2 left = numberlist[:mid] right = numberlist[mid:] left = merge_sort(left) right = merge_sort(right) return merge(left, right)六、快速排序从数列中挑出一个元素，称为“基准”（pivot），
● 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
● 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
● 递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
以上节选自维基百科
代码如下：
def quick_sort(array): if len(array) < 2: return array else: pivot = array[0] less = [i for i in array[1:] if i <= pivot] greater = [i for i in array[1:] if i > pivot] return quick_sort(less) + [pivot] + quick_sort(greater)七、堆排序
若以升序排序说明，把数组转换成最大堆积(Max-Heap Heap)，这是一种满足最大堆积性质(Max-Heap Property)的二叉树：对于除了根之外的每个节点i, A[parent(i)] ≥ A[i]。
重复从最大堆积取出数值最大的结点(把根结点和最后一个结点交换，把交换后的最后一个结点移出堆)，并让残余的堆积维持最大堆积性质。
def heap_sort(numberlist): length = len(numberlist) def sift_down(start, end): root = start while True: child = 2 * root + 1 if child > end: break if child + 1 <= end and numberlist[child] < numberlist[child + 1]: child += 1 if numberlist[root] < numberlist[child]: numberlist[root], numberlist[child] = numberlist[child], numberlist[root] root = child else: break# 创建最大堆 for start in range((length – 2) // 2, -1, -1): sift_down(start, length – 1)# 堆排序 for end in range(length – 1, 0, -1): numberlist[0], numberlist[end] = numberlist[end], numberlist[0] sift_down(0, end – 1) return numberlist八、计数排序以上节选自维基百科
代码如下：
def counting_sort(numberlist, maxnumber): # maxnumber为数组中的最大值 length = len(numberlist) # 待排序数组长度 b = [0 for i in range(length)] # 设置输出序列，初始化为0 c = [0 for i in range(maxnumber+ 1)] # 设置技术序列，初始化为0 for j in numberlist: c[j] = c[j] + 1 for i in range(1, len(c)): c[i] = c[i] + c[i – 1] for j in numberlist: b[c[j] – 1] = j c[j] = c[j] – 1 return b总结
各种排序的稳定性，时间复杂度和空间复杂度总结：
我们比较时间复杂度函数的情况：
时间复杂度函数O(n)的增长情况
所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。
时间复杂度来说：
(1)平方阶(O(n2))排序
各类简单排序:直接插入、直接选择和冒泡排序；
(2)线性对数阶(O(nlog2n))排序
快速排序、堆排序和归并排序；
(3)O(n1+§))排序,§是介于0和1之间的常数。
希尔排序
(4)线性阶(O(n))排序
基数排序，此外还有桶、箱排序。说明：
当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
稳定性：
排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。
稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序
选择排序算法准则：
每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。
选择排序算法的依据
影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：
1．待排序的记录数目n的大小；
2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
3．关键字的结构及其分布情况；
4．对排序稳定性的要求。
设待排序元素的个数为n.
1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序 ： 如果内存空间允许且要求稳定性的，
归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
2） 当n较大，内存空间允许，且要求稳定性 =》归并排序
3）当n较小，可采用直接插入或直接选择排序。
直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序
4）一般不使用或不直接使用传统的冒泡排序。
5）基数排序
它是一种稳定的排序算法，但有一定的局限性：
1、关键字可分解。
2、记录的关键字位数较少，如果密集更好
3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
总结
以上所述是小编给大家介绍的必须知道的C语言 八大排序算法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对脚本之家网站的支持！
☞2023女性开发者报告：3成16岁就会编程、JS/Python成女性掌握最多语言
☞为了让自己快乐，我在36岁辞职了