建设厅施工员证查询网站,wordpress筛选热门列表,.vip域名做网站,汕尾住房和建设局网站首页排序算法是计算机科学中的一个重要概念,它是一种将一个无序的数列重新排列成有序的方法。常见的排序算法有:
选择排序#xff08;Selection Sort#xff09;
选择排序是一种简单直观的排序演算法。它的工作原理:首先在未排序序列中找到最小(大)元素#xff0c;存放到排序序…排序算法是计算机科学中的一个重要概念,它是一种将一个无序的数列重新排列成有序的方法。常见的排序算法有:
选择排序Selection Sort
选择排序是一种简单直观的排序演算法。它的工作原理:首先在未排序序列中找到最小(大)元素存放到排序序列的起始位置然后,再從剩餘未排序元素中继续寻找最小(大)元素然后放到已排序序列的末尾。以上步骤反复执行直到所有数据元素均排序完毕。
#include stdio.hvoid selection_sort(int arr[], int n)
{int i, j, min_idx;for (i 0; i n-1; i) {min_idx i;for (j i1; j n; j) {if (arr[j] arr[min_idx]) {min_idx j;}}int temp arr[i];arr[i] arr[min_idx];arr[min_idx] temp;}
}int main()
{int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);selection_sort(arr, n);printf(Sorted array is:\n);for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);return 0;
}冒泡排序Bubble Sort
最简单的排序算法通过重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。
#include stdio.hvoid bubbleSort(int arr[], int n)
{int i, j;for (i 0; i n-1; i) {for (j 0; j n-i-1; j) {if (arr[j] arr[j1]) {int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}
}int main()
{int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);printf(Sorted array is:\n);for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);return 0;
}插入排序Insertion Sort
插入排序是一种简单直观的排序演算法。通过构建有序序列对未排序数据在已排序序列中从后向前扫描找到相应位置并插入。
#include stdio.hvoid insertionSort(int arr[], int n)
{int i, j;for (i 1; i n; i) {int temp arr[i];j i - 1;while (j 0 arr[j] temp) {arr[j 1] arr[j];j--;}arr[j 1] temp;}
}int main()
{int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);insertionSort(arr, n);printf(Sorted array is:\n);for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);return 0;
}希尔排序Shell Sort
希尔排序是一种插入排序的改进版本。希尔排序的基本思想是使数组中的元素像是在一个具有各种尺寸的篮子里进行排序。希尔排序通过设定一个步长将数组分为若干个子序列然后对这些子序列分别进行插入排序。当步长为1时希尔排序就退化为插入排序。希尔排序的步长可以选择不同的值通常选择2的幂次方比如12481632等。
#include stdio.hvoid shellSort(int arr[], int n)
{int i, j, gap;for (gap n/2; gap 0; gap / 2) {for (i gap; i n; i) {int temp arr[i];for (j i-gap; j 0 arr[j] temp; j - gap) {arr[jgap] arr[j];}arr[jgap] temp;}}
}int main()
{int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);shellSort(arr, n);printf(Sorted array is:\n);for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);return 0;
}归并排序Merge Sort
是建立在归并操作上的一种有效的排序算法该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
#include stdio.h
#include stdlib.hvoid merge(int arr[], int l, int m, int r)
{int i, j, k, n1, n2;int L[m-l1], R[r-m];n1 m - l 1;n2 r - m;for (i 0; i n1; i)L[i] arr[l i];for (j 0; j n2; j)R[j] arr[m 1 j];i 0;j 0;k l;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;}
}void mergeSort(int arr[], int l, int r)
{if (l r) {int m (l r) / 2;mergeSort(arr, l, m);mergeSort(arr, m 1, r);merge(arr, l, m, r);}
}int main()
{int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);mergeSort(arr, 0, n-1);printf(Sorted array is:\n);for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);return 0;
}快速排序Quick Sort
快速排序是一种高效的排序算法基于分治法(Divide and Conquer)的一个策略。将要排序的数组分为两个子数组一个包含相应的元素一个包含其他的元素。
#include stdio.hvoid quickSort(int arr[], int left, int right)
{if (left right) {int pivot arr[(left right) / 2];int i left, j right;while (i j) {while (arr[i] pivot) i;while (arr[j] pivot) j--;if (i j) {int temp arr[i];arr[i] arr[j];arr[j] temp;i;j--;}}quickSort(arr, left, j);quickSort(arr, i, right);}
}int main()
{int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n-1);printf(Sorted array is:\n);for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);return 0;
}堆排序Heap Sort
是一种比较高效的选择排序无论原址排序还是非原址排序都有其实现。
#include stdio.h
#include stdlib.hvoid max_heapify(int arr[], int n, int i)
{int largest i;int l 2*i 1;int r 2*i 2;if (l n arr[l] arr[largest])largest l;if (r n arr[r] arr[largest])largest r;if (largest! i) {int temp arr[i];arr[i] arr[largest];arr[largest] temp;max_heapify(arr, n, largest);}
}void heap_sort(int arr[], int n)
{for (int i n/2 - 1; i 0; i--)max_heapify(arr, n, i);for (int i n-1; i 0; i--) {int temp arr[0];arr[0] arr[i];arr[i] temp;max_heapify(arr, i, 0);}
}int main()
{int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);heap_sort(arr, n);printf(Sorted array is:\n);for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);return 0;
}桶排序
桶排序是计算机科学中的一种排序算法工作原理是将要排序的元素划分到不同的桶然后分别对每个桶中的元素进行排序最后将每个桶中的元素合并成一个有序的序列。
#include stdio.hvoid bucketSort(int arr[], int n, int maxValue) {int i, j;int count[maxValue1];int output[n];for (i 0; i maxValue; i)count[i] 0;for (i 0; i n; i)count[arr[i]];for (i 1; i maxValue; i)count[i] count[i - 1];for (i n - 1; i 0; i--) {output[count[arr[i]] - 1] arr[i];count[arr[i]]--;}for (i 0; i n; i)arr[i] output[i];
}int main() {int arr[] {37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54};int n sizeof(arr) / sizeof(arr[0]);int maxValue 100;bucketSort(arr, n, maxValue);printf(Sorted array: \n);for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}计数排序
计数排序是一种线性时间复杂度的排序算法这种算法对输入的数据有一定的限制如它们都是非负整数。计数排序是一种非比较排序算法其核心思想是将输入的数据值转化为键存储在额外开辟的数组空间中。当输入数据是非负整数时计数排序是一个线性时间排序算法。
#include stdio.hvoid countSort(int arr[], int n) {int max arr[0];int min arr[0];// 找到数组中的最大和最小值for (int i 1; i n; i) {if (arr[i] max)max arr[i];if (arr[i] min)min arr[i];}// 初始化计数数组int range max - min 1;int count[range];for (int i 0; i range; i)count[i] 0;// 计算每个元素的数量for (int i 0; i n; i)count[arr[i] - min];// 修改计数数组,使得每个元素的值表示该元素在数组中的位置for (int i 1; i range; i)count[i] count[i - 1];// 创建一个结果数组,每个元素的位置由计数数组决定int output[n];for (int i n - 1; i 0; i--) {output[count[arr[i] - min] - 1] arr[i];count[arr[i] - min]--;}// 将结果数组复制到原数组for (int i 0; i n; i)arr[i] output[i];
}int main() {int arr[] {10, 20, 7, 8, 9, 1, 5};int n sizeof(arr) / sizeof(arr[0]);countSort(arr, n);printf(Sorted array: \n);for (int i 0; i n; i)printf(%d , arr[i]);return 0;
}基数排序
基数排序是一种非比较整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。通常适用于对小范围整数的排序。将整个整数(例如名字或日期)中的每个数字或字母类似于排序每个单独的数字。
#include stdio.hvoid countingSort(int arr[], int n, int exp) {int output[n]; int i;int count[10] {0}; for (i 0; i n; i)count[(arr[i] / exp) % 10];for (i 1; i 10; i)count[i] count[i - 1];for (i n - 1; i 0; i--) {output[count[(arr[i] / exp) % 10] - 1] arr[i];count[(arr[i] / exp) % 10]--;}for (i 0; i n; i)arr[i] output[i];
}void radixsort(int arr[], int n) {int m getMax(arr, n);for (int exp 1; m / exp 0; exp * 10)countingSort(arr, n, exp);
}int getMax(int arr[], int n) {int mx arr[0];for (int i 1; i n; i)if (arr[i] mx)mx arr[i];return mx;
}void print(int arr[], int n) {for (int i 0; i n; i)printf(%d , arr[i]);printf(\n);
}int main() {int arr[] {170, 45, 75, 90, 802, 24, 2, 66};int n sizeof(arr) / sizeof(arr[0]);radixsort(arr, n);print(arr, n);return 0;
}斐波那契排序
这是一个对冒泡排序的改进通过引入斐波那契数列的概念减少了比较的次数。工作原理是通过两层循环外层循环控制整个排序过程内层循环控制每一轮的排序。如果前一个元素大于后一个元素就交换它们的位置。这样一轮比较下来最大的元素就会移动到它应该在的位置上。
#include stdio.hvoid swap(int *a, int *b) {int temp *a;*a *b;*b temp;
}void fbSort(int arr[], int n) {int i, j;for (i 0; i n-1; i) {for (j 0; j n-i-1; j) {if (arr[j] arr[j1]) {swap(arr[j], arr[j1]);}}}
}int main() {int arr[] {5, 8, 1, 3, 9, 6};int n sizeof(arr)/sizeof(arr[0]);fbSort(arr, n);printf(Sorted array: \n);for (int i0; in; i) {printf(%d , arr[i]);}return 0;
}哈夫曼排序:
哈夫曼排序是一种优先队列排序,它的基本思想是将待排序的序列看作是一棵完全二叉树,然后从上到下和从左到右进行排序。
#includestdio.h
#includestdlib.htypedef struct Node {int data;int freq;struct Node *left, *right;
} Node;Node* newNode(int data, int freq) {Node* node (Node*)malloc(sizeof(Node));node-data data;node-freq freq;node-left node-right NULL;return node;
}int isLeaf(Node* node) {return (!node-left !node-right);
}int max(Node *a, Node *b) {return (a-freq b-freq)? a-freq : b-freq;
}Node *decodeHuff(Node* root, string s, int i) {if (root NULL) return root;if (isLeaf(root)) return root;if (s[i] 0) {return decodeHuff(root-left, s, i1);}else return decodeHuff(root-right, s, i1);
}void printCodes(Node* root, string s) {if (root NULL) return;if (isLeaf(root)) {printf(%c : , root-data);printf(%s\n, s);return;}printCodes(root-left, strcat(s, 0));printCodes(root-right, strcat(s, 1));
}int main() {string s aabcccccaaa;int freq[256];memset(freq, 0, sizeof(freq));for (int i0; istrlen(s); i) freq[s[i]];Node* root NULL;for (int i0; i256; i)if (freq[i] 0)root insertNode(root, newNode(i, freq[i]));printCodes(root, );return 0;
}
