建立一个国外的网站,漯河企业网站开发,如何自己动手做网站,网络营销推广公司网站有哪些以下是几种经典排序算法的C实现#xff0c;包含冒泡排序、选择排序、插入排序、快速排序和归并排序#xff1a;
#include iostream
#include vector
using namespace std;// 1. 冒泡排序
void bubbleSort(vectorint arr) {int n arr.size();f…以下是几种经典排序算法的C实现包含冒泡排序、选择排序、插入排序、快速排序和归并排序
#include iostream
#include vector
using namespace std;// 1. 冒泡排序
void bubbleSort(vectorint arr) {int n arr.size();for (int i 0; i n-1; i) {for (int j 0; j n-i-1; j) {if (arr[j] arr[j1]) {swap(arr[j], arr[j1]);}}}
}// 2. 选择排序
void selectionSort(vectorint arr) {int n arr.size();for (int i 0; i n-1; i) {int minIdx i;for (int j i1; j n; j) {if (arr[j] arr[minIdx]) {minIdx j;}}swap(arr[i], arr[minIdx]);}
}// 3. 插入排序
void insertionSort(vectorint arr) {int n arr.size();for (int i 1; i n; i) {int key arr[i];int j i - 1;while (j 0 arr[j] key) {arr[j1] arr[j];j--;}arr[j1] key;}
}// 4. 快速排序
int partition(vectorint 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;swap(arr[i], arr[j]);}}swap(arr[i1], arr[high]);return i1;
}void quickSort(vectorint arr, int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi-1);quickSort(arr, pi1, high);}
}// 5. 归并排序
void merge(vectorint arr, int left, int mid, int right) {int n1 mid - left 1;int n2 right - mid;vectorint L(n1), R(n2);for (int i 0; i n1; i) {L[i] arr[left i];}for (int j 0; j n2; j) {R[j] arr[mid 1 j];}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;}
}void mergeSort(vectorint 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);}
}// 测试代码
int main() {vectorint arr {64, 25, 12, 22, 11};// 选择一种排序算法调用// bubbleSort(arr);// selectionSort(arr);// insertionSort(arr);// quickSort(arr, 0, arr.size()-1);mergeSort(arr, 0, arr.size()-1);cout 排序后的数组: ;for (int num : arr) {cout num ;}cout endl;return 0;
}各排序算法特点 冒泡排序Bubble Sort 时间复杂度O(n²)稳定排序重复比较相邻元素并交换位置 选择排序Selection Sort 时间复杂度O(n²)不稳定排序每次从未排序部分选择最小元素放到已排序部分末尾 插入排序Insertion Sort 时间复杂度O(n²)稳定排序将未排序数据插入到已排序序列的合适位置 快速排序Quick Sort 平均时间复杂度O(n log n)不稳定排序分治法选择基准值并分区 归并排序Merge Sort 时间复杂度O(n log n)稳定排序分治法将数组分成两半分别排序后合并
在main函数中你可以取消注释相应的排序函数调用来测试不同的排序算法。
