本篇先上五种常用排序
分别是 冒泡排序、选择排序、直接插入排序、希尔排序、快速排序 五种
冒泡排序(bubbleSort)
冒泡排序是最常用最简单的排序，以亲民的代码，简单的思路广受码农的喜爱
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复地进行这个过程直到整个数列都有序。冒泡排序的时间复杂度为O(n^2)，因此对于大规模数据排序时效率较低，但对于小规模数据排序是一种简单且实用的排序算法。
此为一个arr[5]数组的排序过程，黑色为未排序，绿色未已完成排序，每次比较两个元素。
代码极为简单
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[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}如何学习冒泡排序
1. 了解冒泡排序的基本原理和算法流程；
2. 掌握冒泡排序的时间复杂度和空间复杂度；
3. 熟悉冒泡排序的代码实现；
4. 进行冒泡排序的练习和实践；
5. 总结冒泡排序的优缺点和适用场景。
选择排序(selectionSort)
选择排序是一种简单的排序算法，它的基本思想是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序的时间复杂度为O(n^2)，因此对于大规模数据排序时效率较低，但对于小规模数据排序是一种简单且实用的排序算法。
选择排序的算法流程如下：
1. 初始状态：无序区为R[1..n]，有序区为空；
2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3. n-1趟结束，数组有序化了。
讲一下无序区和有序区是什么意思
冒泡排序、选择排序和直接插入排序都是基于比较的排序算法，它们的基本思想都是将待排序的数据元素分成有序区和无序区，每次从无序区中选出一个元素，将它插入到有序区中的合适位置，从而逐渐将无序区中的元素插入到有序区中，最终得到一个有序的序列。
在冒泡排序和选择排序中，有序区和无序区的划分是通过排序轮数来实现的。每轮排序后，无序区的元素个数减少1个，有序区的元素个数增加1个，直到整个序列有序。
在直接插入排序中，有序区和无序区的划分是通过插入元素的位置来实现的。初始时，整个序列都是无序区，每次将无序区的第一个元素插入到有序区的合适位置，从而逐渐将无序区中的元素插入到有序区中，最终得到一个有序的序列。
因此，无序区就是待排序的数据元素中还没有被插入到有序区中的元素，有序区就是已经排好序的数据元素。
选择排序的代码实现如下：
void selectionSort(int arr[], int n) {
int i, j, min;
// 外层循环控制排序轮数，每轮确定一个最小值
for (i = 0; i < n-1; i++) {
// 假设当前轮数的第一个元素为最小值
min = i;
// 内层循环控制每轮到最小值的下标
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
// 将最小值与当前轮数的第一个元素交换位置
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}怎样学习选择排序
1. 了解选择排序的基本原理和算法流程；
2. 掌握选择排序的时间复杂度和空间复杂度；
3. 熟悉选择排序的代码实现；
4. 进行选择排序的练习和实践；
5. 总结选择排序的优缺点和适用场景。
此为一个arr[5]数组进行的选择排序
选择排序的优缺点和适用场景：
优点：
1. 简单，容易实现；
2. 不占用额外的内存空间。
缺点：
1. 时间复杂度为O(n^2)，效率较低；
2. 不稳定，可能会改变项。
适用场景：
选择排序适用于数据规模较小的情况，因为它的时间复杂度为O(n^2)，对于大规模数据排序时效率较低。但是，选择排序不需要额外的内存空间，因此在空间有限的情况下，选择排序是一种简单且实用的排序算法。
直接插入排序(insertionSort)
直接插入排序是一种简单的排序算法，它的基本思想是将待排序的数据元素插入到已经有序的序列中，从而得到一个新的、个数加一的有序序列。直接插入排序的时间复杂度为O(n^2)，因此对于大规模数据排序时效率较低，但对于小规模数据排序是一种简单且实用的排序算法。
此为一个arr[5]数组进行的直接插入排序
直接插入排序的算法流程如下：
1. 初始状态：无序区为R[1..n]，有序区为空；
2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-取出第一个元素R[i]，将它插入到有序区的合适位置，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3. n-1趟结束，数组有序化了。
直接插入排序的代码实现如下：
void insertSort(int arr[],int len){
int i,j,temp;
for(i=1;i<len;i++){ //从1开始，0位置当成有序
temp=arr[i]; //temp记录未排序第一个
for(j=i-1;j>=0&&arr[j]>temp;j--){
arr[j+1]=arr[j]; //元素后移，腾位置给插入元素
}
arr[j+1]=temp; //插入 比较的 后一位
}
}怎样学习直接插入排序：
1. 了解直接插入排序的基本原理和算法流程；
2. 掌握直接插入排序的时间复杂度和空间复杂度；
3. 熟悉直接插入排序的代码实现；
4. 进行直接插入排序的练习和实践；
5. 总结直接插入排序的优缺点和适用场景。
6. 了解直接插入排序的优化算法，如希尔排序；
直接插入排序的优缺点和适用场景：
优点：
1. 简单，容易实现；
2. 稳定，不会改变相同元素的相对位置；
3. 对于小规模数据排序时效率较高。
缺点：
1. 时间复杂度为O(n^2)，效率较低；
2. 对于大规模数据排序时效率较低。
适用场景：
直接插入排序适用于数据规模较小的情况，因为它的时间复杂度为O(n^2)，对于大规模数据排序时效率较低。但是，直接插入排序是一种稳定的排序算法，不会改变相同元素的相对位置，因此在需要保持相同元素相对位置的情况下，直接插入排序是一种简单且实用的排序算法。
希尔排序(shellSort)
希尔排序是直接插入排序的改进版，它通过将待排序的数据元素分组，对每组进行直接插入排序，从而使得整个序列逐步变得有序。希尔排序的时间复杂度为O(nlogn)，比直接插入排序的时间复杂度O(n^2)要低，因此对于大规模数据排序时效率更高。此外，希尔排序也是一种稳定的排序算法，不会改变相同元素的相对位置。因此，在需要保持相同元素相对位置的情况下，希尔排序是一种更好的选择。 (这也是希尔排序相比直接插入排序的优点与选择)
希尔排序的算法流程如下：
1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k趟排序；
3. 每趟排序，根据对应的增量dk，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
这是增量dk为2的arr[6]数组的第一次排序过程
希尔排序的代码实现如下：
//dk 是增量 步长
void shellInsert(int arr[],int len,int dk){
int i,j,temp;
for(i=dk;i<len;i++){
//判断每组的 第几个元素大小
if(arr[i]<arr[i-dk]){ //后边组小于前边组
temp=arr[i];
j=i-dk;
for(;j>=0&&temp<arr[j];j=j-dk){
//前面的值 给到 后面
arr[j+dk]=arr[j];
}
arr[j+dk]=temp;
}
}怎样学习希尔排序
1. 了解希尔排序的基本原理和算法流程；
2. 掌握希尔排序的时间复杂度和空间复杂度；
3. 熟悉希尔排序的代码实现；
4. 进行希尔排序的练习和实践；
5. 总结希尔排序的优缺点和适用场景；
6. 了解希尔排序的优化算法，如快速排序、归并排序等；
7. 进一步学习其他排序算法，如堆排序、计数排序、桶排序等。
希尔排序的优缺点和适用场景：
优点：
1. 时间复杂度为O(nlogn)，比直接插入排序的时间复杂度O(n^2)要低，对于大规模数据排序时效率更高；
2. 稳定，不会改变相同元素的相对位置。
缺点：
1. 实现较为复杂；
2. 不同的增量序列会影响排序效率。
适用场景：
希尔排序适用于数据规模较大的情况，因为它的时间复杂度为O(nlogn)，对于大规模数据排序时效率更高。此外，希尔排序也是一种稳定的排序算法，不会改变相同元素的相对位置。但是，希尔排序的实现较为复杂，需要选择合适的增量序列才能达到较好的排序效果。因此，在需要对大规模数据进行排序且不需要保持相同元素相对位置的情况下，希尔排序是一种较好的选择。
快速排序
快速排序是一种高效的排序算法，它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个序列有序的目的。快速排序的时间复杂度为O(nlogn)，是一种效率较高的排序算法。
快速排序的算法流程如下：
1. 选择一个基准元素，通常选择第一个元素或最后一个元素。
2. 将待排序序列分成两部分，一部分所有元素都比基准元素小，另一部分所有元素都比基准元素大。
3. 对两部分分别进行快速排序，递归进行，直到序列有序。
通过基准值分成两部分
快速排序的代码实现如下：
int getPivot(int arr[],int low,int high){
int pivot=arr[low];
while(low<high){ //i<j的时候
//j从后向前找比基准值小的元素f
while(low<high&&arr[high]>=pivot){
high--;
}
//找到了比基准值小的元素 将元素给到i位置
arr[low]=arr[high];
//i从前往后找比基准值大的元素
while(low<high&&arr[low]<=pivot){
low++;
}
arr[high]=arr[low];
}
//结束条件 i=j 找到了基准值的位置
arr[low]=pivot;
//返回基准值位置
return low;
}
void quickSort(int arr[],int low,int high){
if(low<high){
//基准值位置的变量
int pivot=getPivot(arr,low,high);
//递归对基准值位置左边进行快速排序
quickSort(arr,low,pivot-1);
//递归对基准值位置右边进行快速排序
quickSort(arr,pivot+1,high);
}
}怎样学习快速排序
1. 了解快速排序的基本原理和算法流程；
2. 掌握快速排序的时间复杂度和空间复杂度；
3. 熟悉快速排序的代码实现；
4. 进行快速排序的练习和实践；
5. 总结快速排序的优缺点和适用场景；
6. 了解快速排序的优化算法，如三路快排、随机化快排等；
7. 进一步学习其他排序算法，如归并排序、堆排序等。
快速排序的优缺点和适用场景：
优点：
1. 时间复杂度为O(nlogn)，比直接插入排序的时间复杂度O(n^2)要低，对于大规模数据排序时效率更高；
2. 稳定，不会改变相同元素的相对位置。
缺点：
1. 实现较为复杂；
2. 不同的增量序列会影响排序效率。
适用场景：
希尔排序适用于数据规模较大的情况，因为它的时间复杂度为O(nlogn)，对于大规模数据排序时效率更高。此外，希尔排序也是一种稳定的排序算法，不会改变相同元素的相对位置。但是，希尔排序的实现较为复杂，需要选择合适的增量序列才能达到较好的排序效果。因此，在需要对大规模数据进行排序且不需要保持相同元素相对位置的情况下，希尔排序是一种较好的选择。
本篇先上三种常用查找
分别是 顺序查找、二分查找、分块查找 三种
顺序查找
顺序查找，也称线性查找，是一种简单的查找算法，它的基本思想是从待查找的数据元素序列的第一个元素开始，依次比较每个元素，直到找到目标元素或查找完整个序列为止。顺序查找的时间复杂度为O(n)，因此对于大规模数据查找时效率较低，但对于小规模数据查找是一种简单且实用的查找算法。
顺序查找的算法流程如下：
1. 从待查找的数据元素序列的第一个元素开始；
2. 依次比较每个元素，直到找到目标元素或查找完整个序列为止。
顺序查找的代码实现如下：
int sequentialSearch(int arr[], int n, int target) {
int i;
for (i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;//找不到
}顺序查找的优缺点和适用场景：
优点：
1. 简单，容易实现；
2. 对于小规模数据查找时效率较高。
缺点：
1. 时间复杂度为O(n)，效率较低；
2. 不适用于大规模数据查找。
适用场景：
顺序查找适用于数据规模较小的情况，因为它的时间复杂度为O(n)，对于大规模数据查找时效率较低。但是，顺序查找是一种简单且实用的查找算法，对于小规模数据查找是一种较好的选择。在需要对大规模数据进行查找时，可以考虑使用其他更高效的查找算法，如二分查找、哈希查找等。
二分查找
二分查找，也称折半查找，是一种高效的查找算法，它的基本思想是将待查找的数据元素序列分成两部分，取中间位置的元素进行比较，如果中间位置的元素等于目标元素，则查找成功；如果中间位置的元素大于目标元素，则在左半部分继续查找；如果中间位置的元素小于目标元素，则在右半部分继续查找。通过不断缩小查找范围，最终可以找到目标元素或确定目标元素不存在。二分查找的时间复杂度为O(logn)，是一种效率较高的查找算法。
二分查找的算法流程如下：
1. 将待查找的数据元素序列按照大小顺序排列；
2. 取中间位置的元素进行比较，如果中间位置的元素等于目标元素，则查找成功；
3. 如果中间位置的元素大于目标元素，则在左半部分继续查找；
4. 如果中间位置的元素小于目标元素，则在右半部分继续查找；
5. 重复步骤2~4，直到找到目标元素或确定目标元素不存在。
如何学习二分查找
1. 了解二分查找的基本原理和算法流程；
2. 掌握二分查找的时间复杂度和空间复杂度；
3. 熟悉二分查找的代码实现；
4. 进行二分查找的练习和实践；
5. 总结二分查找的优缺点和适用场景；
6. 了解二分查找的变体算法，如插值查找、斐波那契查找等；
7. 进一步学习其他查找算法，如哈希查找、线性查找等。
二分查找分为递归和非递归两种。
二分查找递归和非递归的区别
二分查找的递归实现和非递归实现的区别在于递归实现使用函数调用栈来保存中间结果，而非递归实现使用循环来实现。递归实现的代码相对简洁，但是由于需要使用函数调用栈，可能会导致栈溢出的问题；非递归实现的代码相对复杂，但是由于不需要使用函数调用栈，可以避免栈溢出的问题。在实际应用中，可以根据具体情况选择递归实现或非递归实现。
二分查找的递归代码实现：
int binarySearch(int arr[],int low,int high,int key){
int mid; //中间下标
while(low<=high){
mid=(high+low)/2;
if(key==arr[mid]){
return mid; //递归出口
}
else if(key>arr[mid]){
return binarySearch(arr,mid+1,high,key);
}
else{
return binarySearch(arr,low,mid-1,key);
}
}
return -1;
}二分查找的递归代码实现：
//arr 数组 low 左边值 high 右边值 key 要查找的关键字
int binarySearch(int arr[],int low,int high,int key){
int mid; //中间值
while(low<=high){
mid=(low+high)/2; //找中间位置
if(key==arr[mid]){
return mid; //返回下标
}
else if(key>arr[mid]){
low=mid+1u
}
else{
high=mid-1;
}
}
//没有找到关键字
return -1;
}二分查找的优缺点和适用场景：
优点：
1. 时间复杂度为O(logn)，效率较高；
2. 对于有序数据元素序列查找时效率较高。
缺点：
1. 只适用于有序数据元素序列查找；
2. 数据元素序列变化较大时，需要重新排序。
适用场景：
二分查找适用于有序数据元素序列查找的情况，因为它的时间复杂度为O(logn)，对于有序数据元素序列查找时效率较高。但是，二分查找只适用于有序数据元素序列查找，如果数据元素序列变化较大时，需要重新排序。因此，在需要对有序数据元素序列进行查找时，二分查找是一种较好的选择。在需要对无序数据元素序列进行查找时，可以考虑使用其他更高效的查找算法，如哈希查找、线性查找等。
分块查找
分块查找，也称块查找，是一种基于分块思想的查找算法，它的基本思想是将待查找的数据元素序列分成若干块，每块中的数据元素可以是无序的，但块与块之间必须是有序的。然后，通过对块的查找和定位，缩小查找范围，最终在对应的块中进行顺序查找，从而找到目标元素。分块查找的时间复杂度为O(sqrt(n))，是一种效率较高的查找算法。
分块查找的算法流程如下：
1. 将待查找的数据元素序列分成若干块，每块中的数据元素可以是无序的，但块与块之间必须是有序的；
2. 对每个块进行查找和定位，缩小查找范围；
3. 在对应的块中进行顺序查找，从而找到目标元素。
分块查找的代码实现如下：
// 分块查找
int blockSearch(int arr[], int n, int m, int target) {
int blockSize = sqrt(n); // 每块的大小
int blockIndex = m / blockSize; // 目标元素所在块的索引
int left = blockIndex * blockSize; // 目标元素所在块的左边界
int right = (blockIndex + 1) * blockSize - 1; // 目标元素所在块的右边界
if (right >= n) { // 如果右边界超出数组范围，则将其设置为数组最后一个元素的索引
right = n - 1;
}
for (int i = left; i <= right; i++) { // 在目标元素所在块中进行顺序查找
if (arr[i] == target) {
return i;
}
}
return -1; // 如果未找到目标元素，则返回-1
}如何学习分块查找
1. 了解分块查找的基本原理和算法流程；
2. 掌握分块查找的时间复杂度和空间复杂度；
3. 熟悉分块查找的代码实现；
4. 进行分块查找的练习和实践；
5. 总结分块查找的优缺点和适用场景；
6. 了解分块查找的变体算法，如B+树、B树等；
7. 进一步学习其他查找算法，如二分查找、哈希查找等。
分块查找的优缺点和适用场景：
优点：
1. 时间复杂度为O(sqrt(n))，效率较高；
2. 对于大规模数据查找时效率较高。
缺点：
1. 实现较为复杂；
2. 对于数据元素序列变化较大的情况，需要重新构建块。
适用场景：
分块查找适用于大规模数据查找的情况，因为它的时间复杂度为O(sqrt(n))，对于大规模数据查找时效率较高。此外，分块查找也适用于数据元素序列变化较小的情况，因为只需要对块进行重新构建即可。但是，分块查找的实现较为复杂，需要对数据元素序列进行分块和排序，因此在需要对小规模数据进行查找时，可以考虑使用其他更简单的查找算法，如顺序查找、二分查找等。在需要对大规模数据进行查找时，分块查找是一种较好的选择。文章来源：https://www.toymoban.com/news/detail-763823.html
文章来源地址https://www.toymoban.com/news/detail-763823.html
到了这里，关于【C语言入门】五种排序，三种查找（配图新手向）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
