在internet上建设网站可选择,百度云引擎搜索,农产品价格实时价格网,湘潭网站开发公司#x1f60f;★,:.☆(#xffe3;▽#xffe3;)/$:.★ #x1f60f; 这篇文章主要介绍常用排序算法。 学其所用#xff0c;用其所学。——梁启超 欢迎来到我的博客#xff0c;一起学习#xff0c;共同进步。 喜欢的朋友可以关注一下#xff0c;下次更新不迷路#x1… ★,°:.☆(▽)/$:.°★ 这篇文章主要介绍常用排序算法。 学其所用用其所学。——梁启超 欢迎来到我的博客一起学习共同进步。 喜欢的朋友可以关注一下下次更新不迷路 文章目录 :smirk:1. 算法介绍:blush:2. C实现 1. 算法介绍
排序算法是计算机科学中常见的一类算法用于将一组数据按照特定的顺序进行排列。下面介绍几种常见的排序算法
冒泡排序Bubble Sort
从待排序序列的第一个元素开始两两比较相邻元素的大小如果顺序不对则交换位置。每一轮结束后最大或最小的元素会移动到末尾。时间复杂度平均情况和最坏情况下为 O(n^2)最好情况下为 O(n)。空间复杂度O(1)。
插入排序Insertion Sort
将未排序序列的第一个元素插入已排序序列的正确位置。从第二个元素开始依次与前面的元素比较并插入到正确位置。时间复杂度平均情况和最坏情况下为 O(n^2)最好情况下为 O(n)。空间复杂度O(1)。
选择排序Selection Sort
每一轮从待排序序列中选择最小或最大的元素与当前位置交换。每一轮结束后当前位置之前的元素都是有序的。时间复杂度平均情况和最坏情况下为 O(n^2)。空间复杂度O(1)。
快速排序Quick Sort
选择一个基准元素将序列分为比基准小的元素和比基准大的元素。递归地对划分后的子序列进行快速排序。时间复杂度平均情况下为 O(nlogn)最坏情况下为 O(n^2)。空间复杂度平均情况下为 O(logn)最坏情况下为 O(n)。
归并排序Merge Sort
将序列递归地拆分成两个子序列对子序列进行排序然后合并两个有序子序列。使用分治法思想将排序问题分解为较小的子问题。时间复杂度平均情况下为 O(nlogn)。空间复杂度O(n)。
2. C实现
#include iostream
#include cstdlib
#include ctime// 冒泡排序 bubbleSort 两两比较
void bubbleSort(int arr[], int n) {for (int i 0; i n-1; i) {for (int j 0; j n-i-1; j) {if (arr[j] arr[j1]) {std::swap(arr[j], arr[j1]);}}}
}// 选择排序 selectionSort 选最小值
void selectionSort(int arr[], int n) {for (int i 0; i n-1; i) {int minIndex i;for (int j i1; j n; j) {if (arr[j] arr[minIndex]) {minIndex j;}}std::swap(arr[i], arr[minIndex]);}
}// 插入排序 insertionSort 依次成序
void insertionSort(int arr[], int n) {for (int i 1; i n; i) {int key arr[i];int j i - 1;while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}
}// 归并排序 mergeSort
void merge(int arr[], int left, int mid, int right) {int n1 mid - left 1;int n2 right - mid;int* L new int[n1];int* R new int[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;int j 0;int 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;}delete[] L;delete[] R;
}void mergeSort(int arr[], int left, int right) {if (left right) {int mid left (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);merge(arr, left, mid, right);}
}// 快速排序 quickSort
int 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;std::swap(arr[i], arr[j]);}}std::swap(arr[i1], arr[high]);return i1;
}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 printArray(int arr[], int size) {for (int i 0; i size; i) {std::cout arr[i] ;}std::cout std::endl;
}int main() {const int SIZE 10;// 生成随机整数数组int arr[SIZE];srand(time(0));for (int i 0; i SIZE; i) {arr[i] rand() % 100; // 生成 0 到 99 的随机数}std::cout Original array: ;printArray(arr, SIZE);// 使用冒泡排序进行排序bubbleSort(arr, SIZE);std::cout Array after bubble sort: ;printArray(arr, SIZE);// 使用选择排序进行排序selectionSort(arr, SIZE);std::cout Array after selection sort: ;printArray(arr, SIZE);// 使用插入排序进行排序insertionSort(arr, SIZE);std::cout Array after insertion sort: ;printArray(arr, SIZE);// 使用归并排序进行排序mergeSort(arr, 0, SIZE-1);std::cout Array after merge sort: ;printArray(arr, SIZE);// 使用快速排序进行排序quickSort(arr, 0, SIZE-1);std::cout Array after quick sort: ;printArray(arr, SIZE);return 0;
}编译运行
g -o main main.cpp ./main以上。
