漳州网站设计,个人网站开发项目总结,个人注册公司需要什么,肇庆企业网站建设学习了十种常见的排序方法#xff0c;此文章针对所学的排序方法进行整理#xff08;通过C语言完成排序#xff09;。 参考内容#xff1a; https://blog.csdn.net/mwj327720862/article/details/80498455 https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
1. 冒…学习了十种常见的排序方法此文章针对所学的排序方法进行整理通过C语言完成排序。 参考内容 https://blog.csdn.net/mwj327720862/article/details/80498455 https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
1. 冒泡排序Bubble Sort
冒泡排序是一种简单的排序算法属于交换排序的一种。通过重复遍历待排序的列表依次比较相邻的两个元素并根据大小进行交换。 从左到右依次比较相邻的两个元素如果前面的元素大于后面的元素就交换它们的位置。重复此过程将最大或最小的元素移动到当前未排序部分的末尾。对未排序部分重复上述步骤直到所有元素都排好序。 时间复杂度平均 O ( n 2 ) O(n^2) O(n2)
空间复杂度 O ( 1 ) O(1) O(1) 如图中数组排序用了5轮成功排好序但实际运行了8轮不判断数组已经有序的情况下以下是排序实现代码。
#include stdio.hint bubbleSort(int arr[],int size)
{for(int i 0; i size - 1; i){for(int j 0; j size - i - 1;j){if(arr[j] arr[j 1]){int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}
}void printArr(int arr[], int size)
{for(int i 0; i size; i){printf(%-5d,arr[i]);}printf(\n);
}int main(int argc,char *argv[])
{int arr[] {1,3,7,5,4,6,2,9,8};int size sizeof(arr) / sizeof(arr[0]);printArr(arr,size);bubbleSort(arr,size);printArr(arr,size);return 0;
}
2. 选择排序Selection Sort
选择排序是一种简单排序算法它的基本思想是通过多次选择将没排序部分中的最小或最大元素找到将其放在已排序部分的末尾或开头。 从未排序部分中找到最小或最大的元素。将该元素与未排序部分的第一个元素交换完成一轮排序。将剩余未排序部分重复上述步骤直到所有元素都排序完成。 时间复杂度平均 O ( n 2 ) O(n^2) O(n2)
空间复杂度 O ( 1 ) O(1) O(1) #include stdio.hint selectSort(int arr[],int size)
{int i,j,k;for(i 0; i size - 1; i){k i;for(j i 1; j size; j){if(arr[k] arr[j])k j;}int temp arr[k];arr[k] arr[i];arr[i] temp;}
}int printArr(int arr[],int size)
{for(int i 0; i size; i){printf(%-5d,arr[i]);}printf(\n);
}int main(int argc,char *argv[])
{int arr[] {1,3,7,5,4,6,2,9,8};int size sizeof(arr) / sizeof(arr[0]);printArr(arr,size);selectSort(arr,size);printArr(arr,size);return 0;
}
3. 插入排序Insert Sort
插入排序是一种简单的排序算法它的基本思想是将待排序的数组划分为已排序部分和未排序部分每次从未排序部分取出一个元素插入到已排序部分的合适位置直到整个数组变得有序。 从第二个元素开始依次将未排序部分的元素插入到已排序部分的合适位置使已排序部分始终有序。重复上述步骤直到所有元素都排好序。 时间复杂度平均 O ( n 2 ) O(n^2) O(n2)
空间复杂度 O ( 1 ) O(1) O(1)
#include stdio.hint insertSort(int arr[],int size)
{int i,j;for( i 1; i size; i){int temp arr[i];for(j i; j 0 arr[j - 1] temp; j--){arr[j] arr[j - 1]; }arr[j] temp;}
}void printArr(int arr[], int size)
{for(int i 0; i size; i)printf(%-5d,arr[i]);printf(\n);
}int main(int argc,char *argv[])
{int arr[] {1,3,7,5,4,6,2,9,8};int size sizeof(arr) / sizeof(arr[0]);printArr(arr,size);insertSort(arr,size);printArr(arr,size);return 0;
}
4. 希尔排序Shell Sort
希尔排序是一种基于插入排序的高级排序算法它的基本思想是通过逐步减少数据的间隔gap将数据分组并排序从而逐步逼近整体有序它的核心思想是分组插入排序通过对数据进行预排序以减少逆序对从而优化了插入排序的效率。 将数组分成多个间隔为gap的子序列每隔gap个元素视为一个分组。对每个子序列进行插入排序使子序列内局部有序。减小gap值重复步骤 1 和 2直到gap1此时对整个数组进行最后一次插入排序。最终数组完全有序 时间复杂度平均介于 O ( n l o g n ) O(nlog n) O(nlogn)和 O ( n 2 ) O(n^2) O(n2)之间
空间复杂度 O ( 1 ) O(1) O(1) #include stdio.hint shellSort(int arr[],int size)
{int i,j,temp,increment;for(increment size / 2; increment 0; increment / 2){for(i increment; i size; i){temp arr[i];for(j i - increment; j 0 arr[j] temp; j - increment){arr[j increment] arr[j];}arr[j increment] temp;}}
}void printArr(int arr[],int size)
{for(int i 0; i size; i)printf(%-5d,arr[i]);printf(\n);}int main(int argc,char *argv[])
{int arr[] {1,3,7,5,4,6,2,9,8};int size sizeof(arr) / sizeof(arr[0]);printArr(arr,size);shellSort(arr,size);printArr(arr,size);return 0;
}
5. 归并排序Merge Sort
归并排序是一种分治算法它通过将数组不断拆分成更小的子数组进行排序并将排序后的子数组合并成一个有序的数组。它的主要思想是分而治之
分解将数组递归地分成两半直到每个子数组只有一个元素或为空。合并将两个有序的子数组合并成一个更大的有序数组。 将数组从中间拆分成两个子数组。递归地对左右两个子数组进行归并排序。合并两个有序子数组使整个数组有序。 时间复杂度平均 O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度 O ( n ) O(n) O(n)需要额外数组存储合并结果 #include stdio.h
#include stdlib.hvoid merge(int arr[], int left, int mid, int right)
{int n1 mid - left 1;int n2 right - mid;int *L (int *)malloc(n1 * sizeof(int));int *R (int *)malloc(n2 * sizeof(int));for(int i 0; i n1; i)L[i] arr[left i];for(int i 0; i n2; i)R[i] arr[mid i 1];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];i;k;}while(j n2){arr[k] R[j];j;k;}free(L);free(R);
} void mergeSort(int arr[], int left, int right)
{if(left right){int mid left (right - left) / 2;mergeSort(arr,left,mid);mergeSort(arr,mid1,right);merge(arr,left,mid,right);}
}void printArr(int arr[],int size)
{for(int i 0; i size; i){printf(%-5d,arr[i]);}printf(\n);
}int main(int argc,char *argv[])
{int arr[] {1,3,7,5,4,6,2,9,8};int size sizeof(arr) / sizeof(arr[0]);printArr(arr,size);mergeSort(arr,0,size - 1);printArr(arr,size);return 0;
}
6. 快速排序Quick Sort
快速排序是一种基于分治思想的高效排序算法。它通过选择一个基准值将数组划分为两个部分小于基准值的元素和大于基准值的元素然后递归地对这两部分进行排序。 选择基准值从数组中选择一个基准值通常是第一个元素、最后一个元素或者任意元素分区将数组重新排序使所有小于基准值的元素位于基准值左侧大于基准值的元素位于右侧递归排序对基准值两侧的子数组继续递归快速排序重复上述步骤直到有序 时间复杂度平均 O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度 O ( l o g n ) O(logn) O(logn)递归栈空间 #include stdio.hint 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,pi1,high);}
}void printArr(int arr[],int size)
{for(int i 0; i size; i)printf(%-5d,arr[i]);printf(\n);
}int main(int argc,char *argv[])
{int arr[] {1,3,7,5,4,6,2,9,8};int size sizeof(arr) / sizeof(arr[0]);printArr(arr,size);quickSort(arr,0,size-1);printArr(arr,size);return 0;
}
7. 堆排序Heap Sort
堆排序是一种基于堆结构的比较排序算法。堆是一颗完全二叉树并且满足堆性质
大顶堆每个节点的值都大于或等于其左右子节点的值。小顶堆每个节点的值都小于或等于其左右子节点的值。
堆排序利用大顶堆的特性来实现升序排序或小顶堆实现降序排序此处实现升序排序 构建初始堆将数组是为完全二叉树并调整其为大顶堆。交换堆顶和堆尾堆顶元素是最大值与最后一个元素交换将最大值移到最终位置。调整堆交换后重新调整为大顶堆。重复步骤2、3。直到堆中只有一个元素 时间复杂度平均 O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度 O ( 1 ) O(1) O(1) #include stdio.hvoid heapify(int arr[],int n,int i)
{int lastest i;int left 2 * i 1;int right 2 * i 2;if(left n arr[left] arr[lastest]){lastest left;}if(right n arr[right] arr[lastest]){lastest right;}if(lastest ! i){int temp arr[lastest];arr[lastest] arr[i];arr[i] temp;heapify(arr,n,lastest);}
}void heapSort(int arr[],int n)
{for(int i n / 2 - 1; i 0; i--){heapify(arr,n,i);}for(int i n - 1; i 0;){int temp arr[i];arr[i] arr[0];arr[0] temp;i--;heapify(arr,i,0);}
}void printArr(int arr[],int size)
{for(int i 0; i size; i){printf(%-5d,arr[i]);}printf(\n);
}int main(int argc,char *argv[])
{int arr[] {1,3,7,5,4,6,2,9,8};int size sizeof(arr) / sizeof(arr[0]);printArr(arr,size);heapSort(arr,size);printArr(arr,size);return 0;
}
8. 计数排序Counting Sort
计数排序是一种非比较排序算法适用于对整数或范围有限的离散数据进行排序。它通过统计每个元素出现的次数来确定元素在排序后的位置。它的核心思想是
统计每个元素的出现次数利用这些计数信息计算元素的位置索引根据索引将元素放入正确的位置从而完成排序 计算频率 找到数组中最大值和最小值确定数值范围 创建一个计数数组记录每个值在原数组中出现次数 累积计数 将计数数组转换为累积计数数组表示每个值在排序后的位置范围 填充结果 倒叙遍历原数组根据累积计数数组将元素放到结果数组中并更新计数数组 时间复杂度 O ( n k ) O(nk) O(nk)n是数组大小k是数据范围
空间复杂度 O ( n k ) O(nk) O(nk)需要额外计数数组和结果数组 #include stdio.h
#include stdlib.hvoid countSort(int arr[],int size)
{int max arr[0],min arr[0];for(int i 0; i size; i){if(arr[i] max)max arr[i];if(arr[i] min)min arr[i];}int len max - min 1;int *count (int *)calloc(len,sizeof(int));for(int i 0; i size; i){count[arr[i]-min];}for(int i 1; i len; i){count[i] count[i-1];}int *output (int *)calloc(size,sizeof(int));for(int i size - 1; i 0; i--){output[count[arr[i]-min]-1] arr[i];}for(int i 0; i size; i){arr[i] output[i];}free(count);free(output);
}void printArr(int arr[],int size)
{for(int i 0;i size; i)printf(%-5d,arr[i]);printf(\n);
}int main(int argc,char *argv[])
{int arr[] {57, 31, 67, 89, 4, 12, 5, 54, 32, 63};int size sizeof(arr) / sizeof(arr[0]);printArr(arr,size);countSort(arr,size);printArr(arr,size);return 0;
}
9. 桶排序Bucket Sort
桶排序是一种基于分布的排序算法它通过将数据分配到多个桶中然后分别对每个桶中的数据进行排序最后合并所有桶中的数据来完成排序。适用于输入数据分布均匀的情况特别是当数据范围有限且可以被分成多个区间时效率较高。 分桶根据数据范围将数据分配到多个桶中每个桶对应一个区间桶内排序对每个桶中的数据分别进行排序推荐插入排序合并桶依次合并每个桶中的数据 时间复杂度平均 O ( n k n l o g ( n / k ) ) O(nknlog(n/k)) O(nknlog(n/k))
空间复杂度 O ( n k ) O(nk) O(nk) #include stdio.h
#include stdlib.h// 链表节点
typedef struct Node {int data;struct Node* next;
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;newNode-next NULL;return newNode;
}// 在链表中插入节点并保持排序顺序
void sortedInsert(Node** head, int data) {Node* newNode createNode(data);if (*head NULL || (*head)-data data) {newNode-next *head;*head newNode;} else {Node* current *head;while (current-next ! NULL current-next-data data) {current current-next;}newNode-next current-next;current-next newNode;}
}// 桶排序函数
void bucketSort(int arr[], int size) {if (size 0) return;// 找到数组中的最大值和最小值int max arr[0], min arr[0];for (int i 1; i size; i) {if (arr[i] max) max arr[i];if (arr[i] min) min arr[i];}int bucketCount 5; // 假设有5个桶int range (max - min bucketCount) / bucketCount; // 每个桶存储的整数范围Node** buckets (Node**)malloc(bucketCount * sizeof(Node*));for (int i 0; i bucketCount; i) {buckets[i] NULL;}// 将元素分配到对应的桶for (int i 0; i size; i) {int bucketIndex (arr[i] - min) / range;sortedInsert(buckets[bucketIndex], arr[i]);}// 将桶内的元素合并回原数组int index 0;for (int i 0; i bucketCount; i) {Node* current buckets[i];while (current ! NULL) {arr[index] current-data;Node* temp current;current current-next;free(temp); // 释放链表节点}}free(buckets); // 释放桶数组
}void printArr(int arr[], int size) {for (int i 0; i size; i) printf(%-5d, arr[i]);printf(\n);
}int main() {int arr[] {21, 33, 17, 5, 44, 26, 32, 19, 38};int size sizeof(arr) / sizeof(arr[0]);printArr(arr, size);bucketSort(arr, size);printArr(arr, size);return 0;
}
10.基数排序Radix Sort
基数排序是一种非比较排序算法通过按位对数据进行多轮排序来实现。它是一种稳定的排序算法适用于整数或字符串等离散数据的排序。基数排序的核心思想是将数据拆分为多个位按照位的优先级从低位到高位或从高位到低位依次进行排序。 确定最大位数找到数组中元素的最大数决定排序的轮数 按位排序 从最低为开始对每一位进行排序 使用稳定的排序算法如计数排序对当前位上的数字进行排序 完成排序 重复2直到最高位 时间复杂度 O ( d ∗ ( n k ) ) O(d*(nk)) O(d∗(nk))其中d是位数n是数据大小k是基数
空间复杂度 O ( n k ) O(nk) O(nk) #include stdio.h
#include stdlib.h// 使用计数排序对数组的某一位进行排序
void countSort(int arr[], int size, int exp) {int output[size]; // 输出数组int count[10] {0}; // 计数数组// 统计当前位数字的频率for (int i 0; i size; i) {int digit (arr[i] / exp) % 10;count[digit];}// 计算累积频率for (int i 1; i 10; i) {count[i] count[i - 1];}// 按当前位数字将元素放入输出数组for (int i size - 1; i 0; i--) {int digit (arr[i] / exp) % 10;output[count[digit] - 1] arr[i];count[digit]--;}// 将排序结果复制回原数组for (int i 0; i size; i) {arr[i] output[i];}
}// 基数排序主函数
void radixSort(int arr[], int size) {// 找到最大值确定最高位int max arr[0];for (int i 1; i size; i) {if (arr[i] max) {max arr[i];}}// 从个位开始对每一位进行排序for (int exp 1; max / exp 0; exp * 10) {countSort(arr, size, exp);}
}void printArr(int arr[], int size) {for (int i 0; i size; i) printf(%-5d, arr[i]);printf(\n);
}int main() {int arr[] {1705, 43, 76, 90, 802, 24, 2, 66, 635};int size sizeof(arr) / sizeof(arr[0]);printArr(arr, size);radixSort(arr, size);printArr(arr, size);return 0;
}
