几种常用的排序算法（c语言实现）

2024-06-30 15:03| 来源: 网络整理| 查看: 265

概述

最近重新回顾了一下数据结构和算法的一些基本知识，对几种排序算法有了更多的理解，也趁此机会通过博客做一个总结。

1.选择排序-简单选择排序

选择排序是最简单的一种基于O（n2）时间复杂度的排序算法，基本思想是从i=0位置开始到i=n-1每次通过内循环找出i位置到n-1位置的最小（大）值。简单排序算法算法实现：

void selectSort(int arr[], int n) { int i, j , minValue, tmp; for(i = 0; i < n-1; i++) { minValue = i; for(j = i + 1; j < n; j++) { if(arr[minValue] > arr[j]) { minValue = j; } } if(minValue != i) { tmp = arr[i]; arr[i] = arr[minValue]; arr[minValue] = tmp; } } } void printArray(int arr[], int n) { int i; for(i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } void main() { int arr[10] = {2,5,6,4,3,7,9,8,1,0}; printArray(arr, 10); selectSort(arr, 10); printArray(arr, 10); return; }

如实现所示，简单的选择排序复杂度固定为O(n2)，每次内循环找出没有排序数列中的最小值，然后跟当前数据进行交换。由于选择排序通过查找最值的方式排序，循环次数几乎是固定的，一种优化方式是每次循环同时查找最大值和最小值可以是循环次数减少为（n/2），只是在循环中添加了记录最大值的操作，原理一样，本文不再对该方法进行实现。

2.冒泡排序

冒泡排序在一组需要排序的数组中，对两两数据顺序与要求顺序相反时，交换数据，使大的数据往后移，每趟排序将最大的数放在最后的位置上，如下：这里写图片描述算法实现：

void bubbleSort(int arr[], int n) { int i, j, tmp; for(i = 0; i < n - 1; i++) { for(j = 1; j < n; j++) { if(arr[j] < arr[j - 1]) { tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; } } } } void printArray(int arr[], int n) { int i; for(i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } void main() { int arr[10] = {2,5,6,4,3,7,9,8,1,0}; printArray(arr, 10); bubbleSort(arr, 10); printArray(arr, 10); return; }

如上是一种最简单的实现方式，需要注意的可能是i, j的边界问题，这种方式固定循环次数，肯定可以解决各种情况，不过算法的目的是为了提升效率，根据冒泡排序的过程图可以看出这个算法至少可以从两点进行优化： 1)对于外层循环，如果当前序列已经有序，即不再进行交换，应该不再进行接下来的循环直接跳出。 2)对于内层循环后面最大值已经有序的情况下应该不再进行循环。优化代码实现：

void bubbleSort_1(int arr[], int n) { int i, nflag, tmp; do { nflag = 0; for(i = 0; i < n - 1; i++) { if(arr[i] > arr[i + 1]) { tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp; nflag = i + 1; } } n = nflag; }while(nflag); }

如上，当nflag为0时，说明本次循环没有发生交换，序列已经有序不用再循环，如果nflag>0则记录了最后一次发生交换的位置，该位置以后的序列都是有序的，循环不再往后进行。

3.插入排序-简单插入排序

插入排序是将一个记录插入到已经有序的序列中，得到一个新的元素加一的有序序列，实现上即将第一个元素看成一个有序的序列，从第二个元素开始逐个插入得到一个完整的有序序列，插入过程如下：这里写图片描述如图，插入排序第i个元素与相邻前一个元素比较，如果与排序顺序相反则与前一个元素交换位置，循环直到合适的位置。算法实现：

void insertSort(int arr[], int n) { int i, j, tmp; for(i = 1; i < n; i++) { for(j = i; j > 0; j--) { if(arr[j] < arr[j-1]) { tmp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = tmp; } else { break; } } } return; } void printArray(int arr[], int n) { int i; for(i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return; } void main() { int arr[10] = {2,5,6,4,3,7,9,8,1,0}; printArray(arr, 10); insertSort(arr, 10); printArray(arr, 10); return; }

如上，前面提到选择排序不管什么情况下都是固定为O(n2)的算法，插入算法虽然也是O(n2)的算法，不过可以看出，在已经有序的情况下，插入可以直接跳出循环，在极端情况下（完全有序）插入排序可以是O（n）的算法。不过在实际完全乱序的测试用例中，与本文中的选择排序相比，相同序列的情况下发现插入排序运行的时间比选择排序长，这是因为选择排序每次外循环只与选择的最值进行交换，而插入排序则需要不停与相邻元素交换知道合适的位置，交换的三次赋值操作同样影响运行时间，因此下面对这一点进行优化：优化后实现：

void insertSort_1(int arr[], int n) { int i, j, tmp, elem; for(i = 1; i < n; i++) { elem = arr[i]; for(j = i; j > 0; j--) { if(elem < arr[j-1]) { arr[j] = arr[j-1]; } else { break; } } arr[j] = elem; } return; }

优化代码将需要插入的值缓存下来，将插入位置之后的元素向后移一位，将交换的三次赋值改为一次赋值，减少执行时间。

4.插入排序-希尔排序

希尔排序的基本思想是先取一个小于n的整数d1作为第一个增量，把全部元素分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 < d1重复上述的分组和排序，直至所取的增量 =1( < …< d2 < d1)，即所有记录放在同一组中进行直接插入排序为止，希尔排序主要是根据插入排序的一下两种性质对插入排序进行改进： 1)插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。 2)但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位排序过程如下：这里写图片描述算法实现：基于一种简单的增量分组方式｛n/2,n/4,n/8……,1｝

void shellSort(int arr[], int n) { int i, j, elem; int k = n/2; while(k>=1) { for(i = k; i < n; i ++) { elem = arr[i]; for(j = i; j >= k; j-=k) { if(elem < arr[j-k]) { arr[j] = arr[j-k]; } else { break; } } arr[j] = elem; } k = k/2; } } void printArray(int arr[], int n) { int i; for(i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return; } void main() { int arr[10] = {2,5,6,4,3,7,9,8,1,0}; printArray(arr, 10); shellSort(arr, 10); printArray(arr, 10); return; } 5.归并排序

归并排序是基于归并操作的一种排序算法，归并操作的原理就是将一组有序的子序列合并成一个完整的有序序列，即首先需要把一个序列分成多个有序的子序列，通过分解到每个子序列只有一个元素时，每个子序列都是有序的，在通过归并各个子序列得到一个完整的序列。这里写图片描述合并过程：把序列中每个单独元素看作一个有序序列，每两个单独序列归并为一个具有两个元素的有序序列，每两个有两个元素的序列归并为一个四个元素的序列依次类推。两个序列归并为一个序列的方式：因为两个子序列都是有序的（假设由小到大），所有每个子序列最左边都是序列中最小的值，整个序列最小值只需要比较两个序列最左边的值，所以归并的过程不停取子序列最左边值中的最小值放到新的序列中，两个子序列值取完后就得到一个有序的完整序列。归并的算法实现：

void merge(int arr[], int l, int mid, int r) { int len,i, pl, pr; int *tmp = NULL; len = r - l + 1; tmp = (int*)malloc(len * sizeof(int)); //申请存放完整序列内存 memset(tmp, 0x0, len * sizeof(int)); pl = l; pr = mid + 1; i = 0; while(pl 1,5,9,8,7,6,3,4,0,2}; printArray(arr, 10); quickSort(arr, 10); printArray(arr, 10); }

因为有变量i从左到右依次遍历序列元素，所有这种方式叫单路快排，不过细心的同学可以发现我们忽略了考虑e等于v的情况，这种快排方式一大缺点就是对于高重复率的序列即大量e等于v的情况会退化为O（n2）算法，原因在大量e等于v的情况划分情况会如下图两种情况：这里写图片描述解决这种问题的一另种方法：快速排序-两路快排：两路快排通过i和j同时向中间遍历元素，e==v的元素分布在左右两个部分，不至于在多重复元素时划分严重失衡。依旧去第一个元素arr[l]为参考量，始终保持arr[l+1….i) =arr[l]原则. 代码实现：

//arr[l+1....i) =arr[l] static int partition2(int arr[], int l, int r) { int i, j; i = l + 1 ; j = r; while(i arr[l] 不是arr[j] >= arr[l]*/ { j--; } while(i v的状态。代码实现：

#include void printArray(int arr[], int n) { int i; for(i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return; } void swap(int *a, int *b) { int tmp; tmp = *a; *a = *b; *b = tmp; return; } static void _quickSort3(int arr [ ],int l,int r) { int i, lt, gt; if(l >= r) { return; } i = l + 1; lt = l; gt = r ; while(i arr[l]) { swap(&arr[i], &arr[gt]); gt--; } else { i++; } } swap(&arr[l], &arr[gt]); _quickSort3(arr, l, lt); _quickSort3(arr, gt + 1, r); return; } void quickSort(int arr[], int n) { _quickSort3(arr, 0, n - 1); return; } void main() { int arr[10] = {1,5,9,8,7,6,3,4,0,2}; printArray(arr, 10); quickSort(arr, 10); printArray(arr, 10); }

三路快排在重复率比较高的情况下比前两种有较大优势，但就完全随机情况略差于两路快排，可以根据具体情况进行合理选择，另外本文在选取参考值时为了方便一直选择第一个元素为参考值，这种方式对于近乎有序的序列算法会退化到O（n2），因此一般选取参考值可以随机选择参考值或者其他选择参考值的方法然后再与arr[l]交换，依旧可以使用相同的算法。

7.堆排序

堆其实一种树形结构，以二叉堆为例，是一颗完全二叉树（即除最后一层外每个节点都有两个子节点，且非满的二叉树叶节点都在最后一层的左边位置），二叉树满足每个节点都大于等于他的子节点(大顶堆)或者每个节点都小于等于他的子节点（小顶堆），根据堆的定义可以得到堆满足顶点一定是整个序列的最大值（大顶堆）或者最小值（小顶堆）。如下图：

这里写图片描述堆排序就是一种基于堆得选择排序，先将需要排序的序列构建成堆，在每次选取堆顶点的最大值和最小值知道完成整个堆的遍历。用数组表示堆：二叉堆作为树的一种，通常用结构体表示，为了排序的方便，我们通常使用数组来表示堆，如下图：这里写图片描述将一个堆按图中的方式按层编号可以得到如下结论： 1）节点的父节点编号满足parent(i) = i/2 2）节点的左孩子编号满足 left child (i) = 2*i 3）节点右孩子满足 right child (i) = 2*i + 1 由于数组编号是从0开始对上面结论修改得到： parent(i) = (i-1)/2 left child (i) = 2*i + 1 right child (i) = 2*i + 2 堆的两种操作方式：根据堆的主要性质（父节点大于两个子节点或者小于两个子节点），可以得到堆的两种主要操作方式，以大顶堆为例： a）如果子节点大于父节点将子节点上移（shift up） b）如果父节点小于两个子节点中的最大值则父节点下移（shift down） shift up: 如果往已经建好的堆中添加一个元素，如下图，此时不再满足堆的性质，堆遭到破坏，就需要执行shift up 操作将添加的元素上移调整直到满足堆的性质。这里写图片描述调整堆的方法： 1）7号位新增元素48与其父节点[i/2]=3比较大于父节点的32不满足堆性质，将其与父节点交换。 2）此时新增元素在3号位，再与3号位父节点[i/2]=1比较，小于1号位的62满足堆性质，不再交换，如果此步骤依旧不满足堆性质则重复1步骤直到满足堆的性质或者到根节点。 3）堆调整完成。代码实现：代码中基于数组实现，数组下表从0开始，父子节点关系如用数组表示堆

/*parent(i) = (i-1)/2 left child (i) = 2*i + 1 right child (i) = 2*i + 2 */ void swap(int *a, int *b) { int tmp; tmp = *a; *a = *b; *b = tmp; return; } void shiftUp(int arr[], int n, int k) { while((k - 1)/2 >= 0 && arr[k] > arr[(k - 1)/2]) { swap(&arr[k], &arr[(k-1)/2]); k = (k - 1)/2; } return; }

shift down: 与shift up相反，如果从一个建好的堆中删除一个元素，此时不再满足堆的性质，此时应该怎样来调整堆呢？这里写图片描述如上图，将堆中根节点元素62删除调整堆的步骤为： 1）将最后一个元素移到删除节点的位置 2）与删除节点两个子节点中较大的子节点比较，如果节点小于较大的子节点，与子节点交换，否则满足堆性质，完成调整。 3）重复步骤2，直到满足堆性质或者已经为叶节点。 4）完成堆调整代码实现：

void shiftDown(int arr[], int n, int k) { int j = 0 ; while(2*k + 1 < n) { j = 2 *k + 1; //标记两个子节点较大的节点，初始为左节点 if (j + 1 < n && arr[j] < arr[j+1]) { j ++; } if(arr[k] < arr[j]) { swap(&arr[k], &arr[j]); k = j; } else { break; } } return; }

知道了上面两种堆的操作后，堆排序的过程就非常简单了 1）首先将待排序序列建成堆，由于最后一层即叶节点没有子节点所以可以看成满足堆性质的节点，第一个可能出现不满足堆性质的节点在第一个父节点的位置，假设最后一个叶子节点为（n - 1）则第一个父节点位置为(n-1-1)/2,只需要依次对第一个父节点之前的节点执行shift down操作到根节点后建堆完成。 2）建堆完成后（以大顶堆为例）第一个元素arr[0]必定为序列中最大值，将最大值提取出来（与数组最后一个元素交换），此时堆不再满足堆性质，再对根节点进行shift down操作，依次循环直到根节点，排序完成。代码实现：

#include /*parent(i) = (i-1)/2 left child (i) = 2*i + 1 right child (i) = 2*i + 2 */ void swap(int *a, int *b) { int tmp; tmp = *a; *a = *b; *b = tmp; return; } void shiftUp(int arr[], int n, int k) { while((k - 1)/2 >= 0 && arr[k] > arr[(k - 1)/2]) { swap(&arr[k], &arr[(k-1)/2]); k = (k - 1)/2; } return; } void shiftDown(int arr[], int n, int k) { int j = 0 ; while(2*k + 1 < n) { j = 2 *k + 1; if (j + 1 < n && arr[j] < arr[j+1]) { j ++; } if(arr[k] < arr[j]) { swap(&arr[k], &arr[j]); k = j; } else { break; } } return; } void heapSort(int arr[], int n) { int i = 0; for(i = (n - 1 -1)/2; i >=0; i--) { shiftDown(arr, n, i); } for(i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); shiftDown(arr, i, 0); } return; } void printArray(int arr[], int n) { int i; for(i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return; } void main() { int arr[10] = {1,5,9,8,7,6,3,4,0,2}; printArray(arr, 10); heapSort(arr, 10); printArray(arr, 10); } 总结

待续……..

【本文地址】

公司简介

联系我们