站长工具爱情岛,软件公司网站系统集成建设,个人网站制作视频,网站seo 教程文章目录 排序算法小结排序算法C实现 排序算法小结
C语言中常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。下面我们来一一介绍#xff1a;
冒泡排序#xff08;Bubble Sort#xff09;#xff1a;冒泡排序是通过比较相邻元素的大小进行排… 文章目录 排序算法小结排序算法C实现 排序算法小结
C语言中常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。下面我们来一一介绍
冒泡排序Bubble Sort冒泡排序是通过比较相邻元素的大小进行排序。如果当前元素比下一个元素大就交换它们两个的位置。重复这个过程直到最后最大的元素就会“冒”到数组的最后。然后再从头开始重复这个过程但是最后一个元素不再考虑。这个过程会一直进行直到没有元素需要交换也就是整个数组已经排序完成。冒泡排序的时间复杂度是O(n^2)。选择排序Selection Sort选择排序是每次从未排序的元素中选择最小或最大的元素放到未排序元素的开始位置直到所有元素都已排序。选择排序的时间复杂度也是O(n^2)。插入排序Insertion Sort插入排序的思路是将未排序的元素依次插入到已排序元素的适当位置。开始时第一个元素被认为已排序然后将第二个元素和它比较决定第二个元素在已排序元素中的位置然后再将第三个元素和已排序的元素比较依次进行。插入排序的时间复杂度是O(n^2)。快速排序Quick Sort快速排序是一种使用分治策略的排序算法。它的基本思想是选择一个基准元素将数组分为两部分一部分的元素都比基准元素小另一部分的元素都比基准元素大。然后对这两部分再分别进行快速排序。快速排序最坏的时间复杂度是O(n^2)但是在平均情况下快速排序的时间复杂度是O(n log n)。归并排序Merge Sort归并排序也是一种使用分治策略的排序算法。它的基本思想是将数组分为两半分别对它们进行归并排序然后将两个已排序的子数组合并成一个完整的已排序数组。归并排序的时间复杂度是O(n log n)。堆排序Heap Sort堆排序是基于二叉堆的一种排序方法。首先将数组构建成一个最大堆或最小堆然后依次移除堆顶的元素并调整堆以保持堆的性质直到堆为空此时数组已排序。堆排序的时间复杂度是O(n log n)。
总的来说这些排序算法各有各的优点和适用场景例如冒泡排序、选择排序和插入排序适用于小规模数据或者部分有序数据而快速排序、归并排序和堆排序通常适用于大规模数据排序。
排序算法C实现
#include stdio.h//冒泡排序
void 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;}}}
}
//选择排序
void selectionSort(int arr[], int n)
{int i, j, minIndex, temp;for (i 0; i n-1; i) {minIndex i;for (j i1; j n; j) if (arr[j] arr[minIndex]) {minIndex j;}temp arr[minIndex];arr[minIndex] arr[i];arr[i] temp;}
}
//插入排序
void insertionSort(int arr[], int n)
{int i, key, j;for (i 1; i n; i) {key arr[i];j i - 1;while (j 0 arr[j] key) {arr[j 1] arr[j];j j - 1;}arr[j 1] key;}
}
//快速排序
int partition(int arr[], int low, int high)
{int pivot arr[high];int i (low - 1);for (int j low; j high- 1; j) {if (arr[j] pivot) {i;swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);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, pi 1, high);}
}
//归并排序
void merge(int arr[], int l, int m, int r)
{int i, j, k;int n1 m - l 1;int n2 r - m;int L[n1], R[n2];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-l)/2;mergeSort(arr, l, m);mergeSort(arr, m1, r);merge(arr, l, m, r);}
}
//堆排序
void 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) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}
void heapSort(int arr[], int n)
{for (int i n / 2 - 1; i 0; i--) {heapify(arr, n, i);}for (int in-1; i0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}
