下载文档原格式
各种排序算法代码（C语⾔版）选择排序#include <stdio.h>/** 选择排序* 稳定性：不稳定* 时间复杂度：O(N^2)**/void select_sort(int a[], int l, int r){for (int m_v, m_idx, t, i = l; i < r; ++i) {m_v = a[i]; m_idx = i;for (int j = i + 1; j < r; ++j) {if (m_v > a[j]) {m_v = a[j];m_idx = j;}}t = a[i]; a[i] = a[m_idx]; a[m_idx] = t;}}int main(void){int a[100];int n; scanf("%d", &n);for (int i = 0; i < n; ++i) scanf("%d", &a[i]);select_sort(a, 0, n);for (int i = 0; i < n; ++i) printf("%d ", a[i]);return0;}冒泡排序#include <stdio.h>/** 冒泡排序* 稳定性：稳定void bubble_sort(int a[], int l, int r){for (int i = l; i < r; ++i) {for (int j = l; j < r - i - 1; ++j) {if (a[j] > a[j + 1]) {int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}}}int main(void){int a[100];int n; scanf("%d", &n);for (int i = 0; i < n; ++i) scanf("%d", &a[i]); bubble_sort(a, 0, n);for (int i = 0; i < n; ++i) printf("%d ", a[i]);return0;}插⼊排序#include <stdio.h>/** 插⼊排序* 稳定性：稳定* 时间复杂度： O(N^2)**/void insert_sort(int a[], int l, int r){for (int tmp, j, i = l + 1; i < r; ++i) {tmp = a[i], j = i - 1;while (j >= l && tmp < a[j]) a[j+1] = a[j--]; a[j+1] = tmp;}}int main(void){for (int i = 0; i < n; ++i) scanf("%d", &a[i]); insert_sort(a, 0, n);for (int i = 0; i < n; ++i) printf("%d ", a[i]);return0;}希尔排序#include <stdio.h>/** 希尔排序* 稳定性：不稳定* 时间复杂度：O(N*logN)**/void shell_insert_sort(int a[], int l, int r, int d) {for (int tmp, j, i = l + d; i < r; ++i) {tmp = a[i], j = i - d;while (j >= l && tmp < a[j]) {a[j + d] = a[j];j -= d;}a[j + d] = tmp;}}void shell_sort(int a[], int l, int r){int d = (r - l) / 2;while (d >= 1) {shell_insert_sort(a, l, r, d);d /= 2;}}int main(void){int a[100];int n; scanf("%d", &n);for (int i = 0; i < n; ++i) scanf("%d", &a[i]); shell_sort(a, 0, n);for (int i = 0; i < n; ++i) printf("%d ", a[i]);归并排序/** 归并排序* 稳定性：稳定* 时间复杂度：O(N*logN)**/void merge(int a[], int n, int b[], int m, int t[]) {int i, j, k;i = j = k = 0;while (i < n && j < m) {if (a[i] < b[j]) t[k++] = a[i++];else t[k++] = b[j++];}while (i < n) t[k++] = a[i++];while (j < m) t[k++] = b[j++];}void my_merge_sort(int a[], int l, int r, int t[]) {int mid = (l + r) >> 1;int n = r - l;int i;if (l + 1 < r) {my_merge_sort(a, l, mid, t);my_merge_sort(a, mid, r, t);merge(a+l, mid-l, a+mid, r-mid, t);for (i = 0; i < n; ++i) a[i + l] = t[i];}}void merge_sort(int a[], int l, int r){int *t = (int *)malloc((r-l) * sizeof (int));my_merge_sort(a, l, r, t);free(t);}堆排序* 堆排序* 稳定性：不稳定* 时间复杂度：O(N*logN)**/// big top pilevoid heap_adjust(int a[], int fa, int n){int cd = fa * 2 + 1;while (cd < n) {if (cd + 1 < n && a[cd] < a[cd + 1]) cd++;if (a[fa] >= a[cd]) break;int tmp = a[fa];a[fa] = a[cd];fa = cd;cd = fa * 2 + 1;a[fa] = tmp;}}void build_heap(int a[], int n){// ignore leap nodefor (int i = (n - 1) / 2; i >= 0; --i) {heap_adjust(a, i, n);}}void heap_sort(int a[], int l, int r){build_heap(a + l, r - l);for (int tmp, i = r - 1; i > l; --i) {tmp = a[i]; a[i] = a[0]; a[0] = tmp;heap_adjust(a + l, 0, i);}}int main(void){int a[100];int n; scanf("%d", &n);for (int i = 0; i < n; ++i) scanf("%d", &a[i]); heap_sort(a, 0, n);return0;}快速排序/** 快速排序* 稳定性：不稳定* 时间复杂度：O(N*logN)**/void quick_sort(int a[], int l, int r){if (l + 1 >= r) return ;int low = l, high = r;int key = a[l];while (low < high) {while (low < high && a[--high] >= key); a[low] = a[high];while (low < high && a[++low] < key); a[high] = a[low];}a[low] = key;quick_sort(a, l, low);quick_sort(a, low+1, r);}基数排序/** 基数排序* 稳定性：稳定* 时间复杂度：O(d(n+radix)) [d个关键码，关键码的取值范围为radix] **/int tmp[100000000];void radix_sort(int arr[], int beg, int ed){static int a[9] = {1, 10, 100, 1000, 10000, 100000, 1000000};int cnt[10]; // 0~9⼗个数字int digit = 0; // 最⼤位数for (int i = beg; i < ed; ++i)while (arr[i] / a[digit + 1] > 0) digit++;for (int idx = 0; idx <= digit; ++idx) {for (int i = 0; i < 10; ++i) cnt[i] = 0; // 桶计数清零for (int i = beg; i < ed; ++i) cnt[ arr[i]/a[idx]%10 ]++; // 统计每个数字出现的次数// 前缀和统计每个数字前⾯的数字个数这样就可以知道每个数字应该排在第⼏位了for (int i = 1; i < 10; ++i) cnt[i] += cnt[i - 1];for (int i = ed - 1; i >= beg; --i) tmp[ --cnt[arr[i]/a[idx]%10] ] = arr[i];for (int i = beg, j = 0; i < ed; ++i, ++j) arr[i] = tmp[j];}}测试性能int a[100000000];double test(void(*fun)(int*, int, int), int range){for (int i = 0; i < range; ++i) a[i] = rand();clock_t start = clock();fun(a, 0, range);clock_t finish = clock();//for (int i = 0; i < range; ++i) printf("%d\n", a[i]);return ((double)finish - start) / CLOCKS_PER_SEC;}int main(){srand((unsigned)time(NULL));printf(" 数据范围堆排序归并排序希尔排序快速排序插⼊排序冒泡排序选择排序基数排序\n");for (int range = 100; range <= 100000; range *= 10) {printf("%9d %8.3f %8.3f %8.3f %8.3f %8.3f %8.3f %8.3f\n", range, test(heap_sort, range), test(merge_sort, range), test(shell_sort, range), test(quick_sort, range), test(insert_sort, range), test(bubble_sort, range), test(select_sort, range), test(radix_sort, range));}for (int range = 1000000; range <= 10000000; range *= 10) {printf("%9d %8.3f %8.3f %8.3f %8.3f %8.3f\n", range, test(heap_sort, range), test(merge_sort, range), test(shell_sort, range),test(quick_sort, range), test(radix_sort, range));}return0;。
使⽤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语言数字从大到小排列C语言数字从大到小排列C语言中，数字的排序是程序员需要掌握的计算机技能之一。
下面将介绍如何使用C语言编写程序来实现数字从大到小的排序。
I. 程序思路1. 输入需要排序的数字，将其存储在数组中；2. 从数组中选择一个数字作为基准点，将比基准点小的数字放在基准点左边，比基准点大的数字放在基准点右边；3. 对基准点左边和右边的数字重复第2步，直到所有数字都排列完成。
II. 编程实现1. 定义函数来实现数字排序：```void sort(int arr[], int left, int right){int i, j, pivot, temp;if (left < right) {pivot = left;i = left;j = right;while (i < j) {while (arr[i] >= arr[pivot] && i < right)i++;while (arr[j] < arr[pivot])j--;if (i < j) {temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}temp = arr[pivot];arr[pivot] = arr[j];arr[j] = temp;sort(arr, left, j - 1);sort(arr, j + 1, right);}}```2. 在主函数中输入需要排序的数字，并输出排序结果：```int main(){int arr[100], i, n;printf("请输入数字的个数：");scanf("%d", &n);for (i = 0; i < n; i++) {printf("请输入第 %d 个数字：", i + 1);scanf("%d", &arr[i]);}sort(arr, 0, n - 1);printf("数字按从大到小排列的结果：\n");for (i = 0; i < n; i++)printf("%d ", arr[i]);return 0;}```在上述代码中，sort函数使用快速排序算法实现数字从大到小的排列。
C语言中的算法实现算法是计算机科学中非常重要的概念，它是解决问题的一系列步骤或指令集。
在C语言中，我们可以使用不同的方法来实现算法。
本文将介绍一些常见的C语言算法实现方式。
一、排序算法1. 冒泡排序冒泡排序是一种简单但效率较低的排序算法。
它通过不断比较相邻的元素，并按照规则交换它们的位置，直到整个序列排序完成。
2. 选择排序选择排序是一种简单而直观的排序算法。
它每次从未排序的序列中选择最小（或最大）的元素，并将其放置在已排序序列的末尾。
3. 插入排序插入排序是一种简单且高效的排序算法。
它通过构建有序序列，对未排序的元素逐个插入到已排序的序列中，直到所有元素都被插入完成。
二、查找算法1. 顺序查找顺序查找是一种简单的查找算法。
它从列表的开头开始逐个比较元素，直到找到目标元素或查找完整个列表。
2. 二分查找二分查找是一种高效的查找算法，但要求列表必须是有序的。
它通过将待查找区域分成两部分，判断目标元素落在哪一部分，从而缩小查找范围，直到找到目标元素或确定不存在。
三、递归算法递归是一种常用的算法设计技巧。
它通过在函数内调用自身来解决相同问题的不同实例。
在C语言中，递归函数需要定义出口条件，以避免无限递归。
四、动态规划算法动态规划是一种用于解决具有重叠子问题和最优子结构性质的问题的方法。
它将问题分解为一系列子问题，并以自底向上的方式求解子问题，最终得到整体问题的解。
在C语言中，可以使用循环、数组和指针等特性来实现动态规划算法，从而有效地解决问题。
五、图算法图是一种用于描述对象之间关系的数据结构，图算法是解决图相关问题的一类算法。
常见的图算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。
六、字符串算法字符串算法用于处理字符串相关的问题，如字符串匹配、编辑距离等。
C语言提供了一系列字符串处理函数，如strlen、strcpy等，可以方便地实现字符串算法。
七、数学算法C语言在数学算法方面提供了丰富的库函数支持，如求平方根、对数、指数等。
#include<stdio.h>#include<stdlib.h>//冒泡排序voidbubleSort(int data[], int n);//快速排序voidquickSort(int data[], int low, int high); intfindPos(int data[], int low, int high);//插入排序voidbInsertSort(int data[], int n);//希尔排序voidshellSort(int data[], int n);//选择排序voidselectSort(int data[], int n);//堆排序voidheapSort(int data[], int n);void swap(int data[], inti, int j);voidheapAdjust(int data[], inti, int n);//归并排序voidmergeSort(int data[], int first, int last);void merge(int data[], int low, int mid, int high); //基数排序voidradixSort(int data[], int n);intgetNumPos(intnum, intpos);int main() {int data[10] = {43, 65, 4, 23, 6, 98, 2, 65, 7, 79}; inti;printf("原先数组:");for(i=0;i<10;i++) {printf("%d ", data[i]);}printf("\n");/*printf("冒泡排序:");bubleSort(data, 10);for(i=0;i<10;i++) {printf("%d ", data[i]);}printf("\n");printf("快速排序:");quickSort(data, 0, 9);for(i=0;i<10;i++) {printf("%d ", data[i]);}printf("\n");printf("插入排序:");bInsertSort(data,10);for(i=0;i<10;i++) {printf("%d ", data[i]);}printf("\n");printf("希尔排序:");shellSort(data, 10);for(i=0;i<10;i++) {printf("%d ", data[i]);}printf("\n");printf("选择排序:");selectSort(data, 10);for(i=0;i<10;i++) {printf("%d ", data[i]);}printf("\n");int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79}; inti;printf("原先数组:");int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79}; for(i=1;i<11;i++) {printf("%d ", data[i]);}printf("\n");printf(" 堆排序:");heapSort(data, 10);for(i=1;i<11;i++) {printf("%d ", data[i]);}printf("\n");printf("归并排序:");mergeSort(data, 0, 9);for(i=0;i<10;i++) {printf("%d ", data[i]);}printf("\n");*/printf("基数排序:");radixSort(data, 10);for(i=0;i<10;i++) {printf("%d ", data[i]);}printf("\n");return 0;}/*--------------------冒泡排序---------------------*/ voidbubleSort(int data[], int n) {inti,j,temp;//两个for循环，每次取出一个元素跟数组的其他元素比较//将最大的元素排到最后。
数组排序函数c语言数组排序函数是计算机编程中常用的一种函数，它的作用是将一个数组中的元素按照一定的规则进行排序。
在C语言中，有多种方法可以实现数组的排序，包括冒泡排序、选择排序、插入排序、快速排序等。
本文将介绍这些排序算法的原理和实现方式。
一、冒泡排序冒泡排序是一种简单直观的排序算法，它的原理是通过比较相邻元素的大小，将较大的元素逐渐“冒泡”到数组的末尾。
具体实现时，我们可以使用两层循环来完成冒泡排序的过程。
外层循环控制比较的轮数，内层循环用于比较相邻元素的大小并进行交换。
经过多轮比较和交换，最终数组中的元素按照从小到大的顺序排列。
二、选择排序选择排序是一种简单但低效的排序算法，它的原理是每次从未排序的元素中选择最小的元素，然后与未排序部分的第一个元素交换位置，这样每一轮都能确定一个最小元素的位置。
具体实现时，我们可以使用两层循环来完成选择排序的过程。
外层循环控制比较的轮数，内层循环用于寻找未排序部分的最小元素并进行交换。
经过多轮比较和交换，最终数组中的元素按照从小到大的顺序排列。
三、插入排序插入排序是一种简单直观的排序算法，它的原理是将一个元素插入到已经排好序的数组中的合适位置。
具体实现时，我们可以使用两层循环来完成插入排序的过程。
外层循环控制待插入的元素，内层循环用于比较已排序部分的元素并进行移动。
经过多轮比较和移动，最终数组中的元素按照从小到大的顺序排列。
四、快速排序快速排序是一种高效的排序算法，它的原理是通过选择一个基准元素，将数组分成两部分，左边部分的元素都小于基准元素，右边部分的元素都大于基准元素，然后递归地对左右两部分进行排序。
具体实现时，我们可以使用递归函数来完成快速排序的过程。
在每一轮排序中，我们选择一个基准元素，将数组分成两部分，并对这两部分进行递归排序。
经过多轮递归排序，最终数组中的元素按照从小到大的顺序排列。
以上是常见的几种数组排序函数的原理和实现方式。
在实际编程中，我们可以根据具体的需求选择合适的排序算法。
C语言超算法大全1.快速排序算法：快速排序是一种高效的排序算法，基于分治法的思想。
它通过选择一个基准元素，将数组划分为两个子数组，其中一个子数组的所有元素小于基准元素，另一个子数组的所有元素大于基准元素。
然后递归地对两个子数组进行快速排序，最终得到排序后的数组。
2.归并排序算法：归并排序也是一种高效的排序算法，基于分治法的思想。
它将数组分为两个子数组，然后递归地对每个子数组进行归并排序，最后将两个有序的子数组合并成一个有序的数组。
3.堆排序算法：堆排序是一种树形选择排序算法，利用堆数据结构来实现。
它通过构建一个最大堆，将堆顶元素与最后一个元素交换，然后重新调整堆，重复这个过程，最终得到排序后的数组。
4.二分查找算法：二分查找算法是一种在有序数组中查找特定元素的算法。
它通过将待查找区间的中间元素与目标元素进行比较，根据比较结果调整区间范围，直到找到目标元素或区间为空。
5.图的深度优先算法：图的深度优先算法是一种用于遍历图的算法。
它从一个顶点开始，递归地访问所有与该顶点相连的未访问过的顶点，直到所有顶点都被访问过为止。
6.图的广度优先算法：图的广度优先算法也是一种用于遍历图的算法。
它从一个顶点开始，依次访问与该顶点相邻的顶点，并将这些相邻顶点加入到一个队列中，然后继续对队列中的顶点进行同样的操作，直到队列为空为止。
7.迪杰斯特拉算法：迪杰斯特拉算法是一种用于求解单源最短路径问题的算法。
它通过动态规划的方式，逐步更新起始顶点到其他顶点的最短路径长度。
8.动态规划算法：动态规划算法是一种用于解决多阶段决策问题的算法。
它通过将原问题划分为若干个子问题，并记忆已经解决的子问题的结果，从而避免重复计算，提高计算效率。
9.最小生成树算法：最小生成树算法是一种用于求解连通图的最小成本生成树的算法。
它通过选择具有最小权值的边来构建最小生成树，直到所有顶点都被包含在生成树中。
10.拓扑排序算法：拓扑排序算法是一种用于对有向无环图进行排序的算法。
C语言常用简单算法C语言是一种广泛应用的编程语言，支持各种算法的实现。
以下是一些常用的简单算法，涵盖了排序、查找、递归等方面。
1. 冒泡排序（Bubble Sort）：通过不断比较相邻元素的大小，将较大的元素逐步“冒泡”到数组的末尾。
2. 选择排序（Selection Sort）：每次从未排序的数组中选择最小（或最大）的元素，放到已排序数组的末尾。
3. 插入排序（Insertion Sort）：将数组分为已排序和未排序两个部分，每次将未排序部分中的元素插入到已排序部分的正确位置。
4. 快速排序（Quick Sort）：选择一个基准元素，将数组分成两部分，将小于基准的元素放在左边，大于基准的元素放在右边，然后递归地对两部分进行排序。
5. 归并排序（Merge Sort）：将待排序数组递归地分成两部分，分别进行排序，然后再将两个有序的数组合并成一个有序的数组。
6. 二分查找（Binary Search）：对于有序数组，通过比较中间元素和目标值的大小，缩小查找范围，直到找到目标值或查找范围为空。
7. 线性查找（Linear Search）：对于无序数组，逐个比较数组中的元素和目标值，直到找到目标值或遍历完整个数组。
8. 求阶乘（Factorial）：使用递归方式或循环方式计算给定数字的阶乘。
9. 斐波那契数列（Fibonacci Sequence）：使用递归方式或循环方式生成斐波那契数列。
10. 汉诺塔（Tower of Hanoi）：使用递归方式实现汉诺塔问题的解决，将一组盘子从一个柱子移动到另一个柱子。
11. 判断回文数（Palindrome）：判断给定数字是否为回文数，即正序和倒序相同。
12.求最大公约数（GCD）：使用辗转相除法或欧几里德算法求两个数的最大公约数。
13.求最小公倍数（LCM）：通过最大公约数求得最小公倍数。
14. 求质数（Prime Number）：判断给定数是否为质数，即只能被1和自身整除。
#include <stdio.h>#include <stdlib.h>#define Max 20 //最大顶点数//顺序存储方式使用的结构体定义typedef struct vexType{char data;int indegree;}Vex;typedef struct Graph{int vexnum; //顶点数量int arcnum; //边数Vex vex_array[Max]; //存放顶点的数组int arc_array[Max][Max]; //存放邻接矩阵的二维数组}Graph; //图的定义//链式存储使用的结构体定义typedef struct arcType{char vex1,vex2; //边所依附的两点int arcVal; //边的权值}Arc; //边的定义typedef struct LinkType{int index; //在顶点表的下标struct LinkType *nextarc; //指向下一个顶点结点}LinkNode; //边表定义typedef struct vexNode{char data;int add; //在顶点数组的下表位置LinkNode *firstarc; //指向边表的第一个结点int indegree; //入度}VexNode; //顶点边定义typedef struct LGraph{VexNode vex_array[Max]; //顶点数组int vexnum; //图中顶点数}LGraph;/*函数功能：图的创建入口参数：图G返回值：无*/void Creat_G(Graph *G){char v;int i=0;int j=0;G->vexnum=0;printf("输入说明。
有权值请输入权值，无权值请输入1，无边请输入0\n");printf("\n请输入所有顶点(不超过20个，按‘#’结束输入)：\n");do{printf("输入第%d 个顶点：",G->vexnum+1);scanf(" %c",&v);G->vex_array[G->vexnum].data = v;G->vexnum++;}while(v!='#');G->vexnum--;printf("输入邻接矩阵（%d * %d）：",G->vexnum,G->vexnum);for(i=0; i<G->vexnum; i++){printf("输入%c 到以下各点的权值：\n",G->vex_array[i].data);for(j=0; j<G->vexnum; j++){printf("<%c, %c>: ",G->vex_array[i].data,G->vex_array[j].data);scanf("%d",&G->arc_array[i][j]);}}printf("\n构建图的顶点为：\n");for(i=0; i<G->vexnum; i++){printf("%c ",G->vex_array[i].data);}printf("\n构建图的邻接矩阵为：\n");for(i=0; i<G->vexnum; i++){for(j=0; j<G->vexnum; j++){printf("%d ",G->arc_array[i][j]);}printf("\n");}}/*函数功能：统计各点的入度入口参数：指向图的指针*G返回值：无*/void Count_indegree(Graph *G){int i;int j;for(j=0; j<G->vexnum; j++){G->vex_array[j].indegree =0;for(i=0; i<G->vexnum; i++){if(G->arc_array[i][j]!=0)G->vex_array[j].indegree++;}}}/*函数功能：对邻接矩阵进行拓扑排序入口参数：指向图的指针*G返回值：无*/void Topol_sort(Graph *G){int i,j;char topo[Max]; //存放拓扑排序的结果int count=0; //记录topo[]中的元素个数，便于与vexnum比较，判断是有环图还是无环图char stack[Max]; //存放indegree=0的顶点所在vex_array[]中的下标int top=0; //栈的指针int bool=1; //弹栈的标准int no; //接收stack[]栈中弹出的顶点下标for(i=0; i<G->vexnum; i++){if(G->vex_array[i].indegree==0){stack[top] = i;top++;}}do{if(top==-1)bool=0;else{top--;no = stack[top];topo[count] = G->vex_array[no].data;count++;for(j=0; j<G->vexnum; j++){if(G->arc_array[i][j]!=0){G->vex_array[j].indegree--;if(G->vex_array[j].indegree==0){stack[top] = j;top++;}}}}}while(bool==1);count--;if(count < G->vexnum){printf("\n结果：原图中有环，无法形成拓扑序列!\n");}else{printf("\n结果：原图的拓扑序列为：\n");for(i=0; i<count; i++){printf("%c ",topo[i]);}printf("\n");}}/*函数功能：邻接矩阵及相关操作入口参数：指向图的指针*G返回值：无*/void LinJieJuZhen(Graph *G){int choice;printf("\n1 图的创建(针对有向图)\n2 拓扑排序\n0 退出\n请选择：");scanf("%d",&choice);do{switch(choice){case 1:Creat_G(G);break;case 2:Count_indegree(G);Topol_sort(G);break;case 0:break;}printf("请选择：");scanf("%d",&choice);if(choice==0)break;}while(choice!=0);}/*函数功能：创建邻接链表T入口参数：指向连接链表的指针*T返回值：无*/void Creat_LinkT(LGraph *T){char v;int i,j,k;char answer;int count;int f=1; //标志边表的第一个结点LinkNode *p=NULL;LinkNode *q=NULL;T->vexnum = 0;printf("\n输入说明。
有权值请输入权值，无权值请输入1，无边请输入0\n");printf("\n请输入所有顶点(不超过20个，按‘#’结束输入)\n");do{printf("输入第%d 个顶点：",T->vexnum+1);scanf(" %c",&v);T->vex_array[T->vexnum].data = v;T->vex_array[T->vexnum].firstarc = NULL;T->vexnum++;}while(v!='#');T->vexnum--;for(i=0; i<T->vexnum; i++){f=1;printf("\n以顶点%c 为始点是否有边(Y / N): ",T->vex_array[i]);scanf(" %c",&answer);if(answer=='Y'){printf("输入以%c 为始点的所有终点个数：",T->vex_array[i]);scanf("%d",&count);for(j=0; j<count; j++){p = (LinkNode *)malloc(sizeof(LinkNode));p->nextarc=NULL;printf("输入第%d 个顶点：",j+1);scanf(" %c",&v);for(k=0; k<T->vexnum; k++){if(v==T->vex_array[k].data){p->index = k; //找到该元素，并记录下标if(f==1) //是第一个结点,放在T->vex_array[i].firstarc上{T->vex_array[i].firstarc = p;q = p;f = 0;}else{q->nextarc = p;q = p;}}}}}}printf("创建链表为:\n");for(i=0; i<T->vexnum; i++){printf("%c ---->",T->vex_array[i].data);p = T->vex_array[i].firstarc;while(p!=NULL){printf("%c ---->",T->vex_array[p->index].data);p=p->nextarc;}printf("NULL\n");}}/*函数功能：统计各个点的入度入口参数：指向图的指针*T返回值:无*/void Count_T_indegree(LGraph *T){int i;LinkNode *p=NULL;for(i=0; i<T->vexnum; i++){T->vex_array[i].indegree = 0;}for(i=0; i<T->vexnum; i++){p = T->vex_array[i].firstarc;while(p!=NULL){T->vex_array[p->index].indegree++;p=p->nextarc;}}}/*函数功能：拓扑排序入口参数：指向图的指针*T返回值：无*/void L_Topol_sort(LGraph *T){int i,j;int no;int stack[Max];int top=0;int topo[Max];int count=0;int bool=1;LinkNode *p=NULL;for(i=0; i<T->vexnum; i++){if(T->vex_array[i].indegree==0){stack[top] = i;top++;}}do{if(top==0)bool=0;else{top--;no = stack[top];topo[count] = T->vex_array[no].data;count++;p = T->vex_array[no].firstarc;while(p!=NULL){T->vex_array[p->index].indegree--;if(T->vex_array[p->index].indegree==0){stack[top] = p->index;top++;}p = p->nextarc;}}}while(bool==1);//printf("检测\n");if(count < T->vexnum)printf("原图有环，无法形成拓扑排序！\n");else{printf("原图的拓扑排序为：\n");for(i=0; i<count; i++){printf("%c ",topo[i]);}}}/*函数功能：邻接链表及拓扑排序入口参数：指向图的指针*T返回值：无*/void LinJieLianBiao(LGraph *T){int choice;printf("\n1 图的创建(针对有向图)\n2 拓扑排序\n0 退出\n");do{printf("\n请选择：");scanf("%d",&choice);switch(choice){case 1:Creat_LinkT(T);printf("图已创建完成！\n");break;case 2:Count_T_indegree(T);L_Topol_sort(T);break;case 0:break;}if(choice==0)break;}while(choice!=0);}void main(){int choice;//邻接矩阵中的变量Graph G;LGraph T;printf("---------------------------\n\n");printf("1、图的顺序存储--邻接矩阵并进行拓扑排序\n2、图的连式存储--邻接链表并进行拓扑排序\n0、退出\n");do{printf("请选择主菜单操作：");scanf("%d",&choice);switch(choice){case 1:printf("\n****图的顺序存储--邻接矩阵****\n");LinJieJuZhen(&G);break;case 2:printf("\n****图的链式存储--邻接链表****\n");LinJieLianBiao(&T);break;case 0:exit(0);default:printf("输入错误！\n");break;}}while(choice!=0);}#include <stdio.h>#include <stdlib.h>#define Max 20typedef struct list{int array[Max];int length;}List;/*数组复制*/void Copy(List *L,List *Lx){int i;Lx->length = L->length;for(i=1; i<=L->length; i++){Lx->array[i] = L->array[i];}/*创建顺序表*/void Creat(List *L){int data=0;int i;L->length=1;printf("输入数据，以-100为结束输入标志\n");while(data!=-100){printf("输入第%d 个元素值：",L->length);scanf("%d",&data);L->array[L->length] = data;L->length++;}L->length = L->length-2;printf("输入的元素值为：");for(i=1; i<=L->length; i++){printf("%d ",L->array[i]);}printf("\n");}/*直接插入排序*/void ZhiJieChaRu_sort(List *L){int i;int j;for(i=2; i<=L->length; i++){if(L->array[i] < L->array[i-1]){L->array[0] = L->array[i];L->array[i] = L->array[i-1];for(j=i-2; L->array[0] < L->array[j]; j--){L->array[j+1] = L->array[j];}L->array[j+1] = L->array[0];}}printf("\n----------------直接插入法排序结果为-------------\n");for(i=1; i<=L->length; i++)printf("%d ",L->array[i]);printf("\n");}/*二分法排序*/void ErFenFa_sort(List *L){int i;int j;int low;int high;int mid;for(i=2; i<=L->length; i++){low = 1;high = i-1;L->array[0] = L->array[i];while(low <= high){mid = (low+high)/2;if(L->array[0] < L->array[mid])high = mid - 1;elselow = mid + 1;}for(j=i-1; j>=high+1; j--){L->array[j+1] = L->array[j];}L->array[high+1] = L->array[0];}printf("\n-------------------二分法排序结果为-----------------\n");for(i=1; i<=L->length; i++)printf("%d ",L->array[i]);printf("\n");}//一次增量下的希尔排序void Shell_pass(List *L,int d){int i;int j;for(i=d+1; i<=L->length; i++){if(L->array[i] < L->array[i-d]){L->array[0] = L->array[i];L->array[i] = L->array[i-d];for(j=i-2*d; j>0 && L->array[0]<L->array[j]; j--)L->array[j] = L->array[j-d];L->array[j+d] = L->array[0];}}}//希尔排序void Shell_sort(List *L,int d[]){int i;for(i=0; i<4; i++) //一次取出d中的增量值Shell_pass(L,d[i]);printf("\n-----------------希尔排序结果为-----------------\n");for(i=1; i<=L->length; i++)printf("%d ",L->array[i]);printf("\n");}//冒泡排序void MaoPao_sort(List *L){int i;int j;int flag=1; //问题：课件上显示为已注销的部分，但是无法排序（没有交换=？=已经排好了）for(i=1; i<=L->length; i++) //控制趟数{// flag=1;for(j=1; j<=L->length-i; j++) //一趟的循环,第i趟结束后就筛选出第i个最小值，所以只需从前length-i个中冒出最小值{if(L->array[j+1] < L->array[j]){flag=0;L->array[0] = L->array[j+1];L->array[j+1] = L->array[j];L->array[j] = L->array[0];}// if(flag==1)// break;}}printf("\n-----------------冒泡排序结果为-----------------\n");for(i=1; i<=L->length; i++)printf("%d ",L->array[i]);printf("\n");}//快速排序的一次枢轴定位int KuaiSu_sort(List *L, int low, int high){int pivotkey; //枢轴L->array[0] = L->array[low]; //每次排序序列的第一个值作为枢轴,即low作为枢轴pivotkey = L->array[low];while(low < high){while(low<high && pivotkey<=L->array[high]) //无论是哪种退出循环方式，都恰好是high的位置就是枢轴位置high--;if(low<high){L->array[low] = L->array[high];low++;}while(low<high && pivotkey>=L->array[low])low++;if(low<high){L->array[high] = L->array[low];high--;}}//整个循环退出就得到枢轴在真正序列中的位置为low（也是high）L->array[low] = L->array[0];/* printf("\n-----------------分步排序结果为-----------------\n");for(i=1; i<=L->length; i++)printf("%d ",L->array[i]);printf("\n");*/return low;}//完整快速排序void KuaiSuPaiXu_sort(List *L,int low,int high){int pivotloc; //接收一次枢轴定位的位置if(low < high){pivotloc = KuaiSu_sort(L,low,high); //也可写为(L,low,pivotkey-1)KuaiSuPaiXu_sort(L,low,pivotloc-1);KuaiSuPaiXu_sort(L,pivotloc+1,high); //也可写为(L,high,pivotkey-1) }}//简单选择排序void JianDanXuanZe_sort(List *L){int i;int j;int min;for(i=1; i<L->length; i++) //冒泡排序的最后一个值不用参与比较{min = i;for(j=i+1; j<=L->length; j++){if(L->array[j] < L->array[min])min = j;}if(min!=i){L->array[0] = L->array[min];L->array[min] = L->array[i];L->array[i] = L->array[0];}}printf("\n-----------------简单选择排序结果为-----------------\n");for(i=1; i<=L->length; i++)printf("%d ",L->array[i]);printf("\n");}/*2—路归并排序一趟合并函数功能：将L[s...m] 和L[m+1...t]和并为T[s...t]入口参数：原列表L，合并后的列表T,起始值s,中间值m，终点值t 返回值：无void GuiBing_pass(List *L,List *T,int s,int m,int t){int i;int j;int k=1;for(i=1,j=m+1; i<=m,j<=t; k++){if(L->array[i] < L->array[j])T->array[k] = L->array[i++];elseT->array[k] = L->array[j++];}while(i < m){T->array[k++] = L->array[i++];}while(j<t){T->array[k++] = L->array[j++];}}2-归并排序递归分解函数功能：将L[s..t]归并为T2[s...t],再将T2[s..t]归并为T1[s..t]void GuiBing_sort(List *L,List *T1,int s,int t){int m;List Tx;List *T2 = &Tx;Tx.length = 6;if(s==t)L->array[s] = T2->array[s];else{m = (s+t)/2;GuiBing_sort(L,T2,s,m);GuiBing_sort(L,T2,m+1,t);GuiBing_pass(T2,T1,s,m,t);}}*/void main(){int choice;int i;int d[4] = {7,5,3,1}; //希尔排序的增量数组List L;List Lx; //每次使用一中排序后就会对数组改变，所以复制下来检测每一种排序方法List T; //存放2路归并排序的结果T.length = 6;printf("1 创建顺序表\n2 直接插入排序\n3 二分法插入排序\n4 希尔排序\n5 冒泡排序\n6 快速排序\n7 简单选择排序\n0 退出\n");do{printf("请选择：");scanf("%d",&choice);switch(choice){case 1:Creat(&L);break;case 2:Copy(&L,&Lx);ZhiJieChaRu_sort(&Lx);break;case 3:Copy(&L,&Lx);ErFenFa_sort(&Lx);break;case 4:Copy(&L,&Lx);Shell_sort(&Lx,d);break;case 5:Copy(&L,&Lx);MaoPao_sort(&Lx);break;case 6:Copy(&L,&Lx);KuaiSuPaiXu_sort(&Lx,1,Lx.length);printf("\n-----------------快速排序结果为-----------------\n");for(i=1; i<=Lx.length; i++)printf("%d ",Lx.array[i]);printf("\n");break;case 7:Copy(&L,&Lx);JianDanXuanZe_sort(&Lx);break;/* case 8:Copy(&L,&Lx);GuiBing_sort(&Lx,&T,1,Lx.length);printf("\n-----------------2-路排序结果为-----------------\n");for(i=1; i<=Lx.length; i++)printf("%d ",T.array[i]);printf("\n");break;*/case 0:printf("退出操作!\n");exit(0);break;default :printf("输入错误");break;}}while("choice!=0");}。
