当前位置： 首页 > news >正文

3、排序算法1---按考研大纲做的

news 2025/4/21 2:57:02

一、插入排序

1、直接插入排序

推荐先看这个视频

1.1、原理

  • 第一步，索引0的位置是有序区（有序区就是有序的部分，刚开始就只有第一个数据是有序的）。
  • 第二步，将第2个位置到最后一个位置的元素，依次进行排序，而这个排序的过程，类似于扑克牌。（我们将后面的2~n个元素一个一个的与有序区对比，将它插入到有序区里面的适当位置）。

我们采用顺序查找的方式，来找到要插入位置，进行插入------>这就是直接插入排序。

在这里插入图片描述

1.2、代码实现（C语言）

  • while和for来实现
#include <stdio.h>
void insertionSort1(int arr[], int n) {for (int i = 1; i < n; i++) {int temp = arr[i];int j = i - 1;// 从后向前扫描，移动大于key的元素while (j >= 0 && arr[j] > temp) {arr[j + 1] = arr[j];j--;}arr[j + 1] = temp;}
}
  • 2个for实现
#include <stdio.h>
void insertSort2(int arr[],int n){for(int i =1;i<n;i++){int temp = arr[i];int j;for(j = i;j>0&&temp<arr[j-1];--j){arr[j]=arr[j-1];}arr[j]=temp;}
}

2、折半插入排序

折半插入排序视频。

2.1、原理

  • 在直接插入排序基础上，使用二分查找确定插入位置，减少比较次数。
  • 算法步骤
    • 从第一个元素开始，该元素可认为已排序
    • 取出下一个元素，在已排序序列中使用二分查找找到插入位置
    • 将插入位置后的所有元素后移一位
    • 将新元素插入到找到的位置
    • 重复步骤2~4

2.2、代码实现（C语言）

#include <stdio.h>
void binaryInsertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int left = 0, right = i - 1;// 二分查找插入位置while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] > temp) {right = mid - 1;} else {//arr[mid]<=temp:只要小于了就说明找到left了。 left = mid + 1;}}// 移动元素for (int j = i - 1; j >= left; j--) {arr[j + 1] = arr[j];}// 插入元素arr[left] = temp;}
}

二、希尔排序

1、原理

  • 希尔排序也是插入排序的升级版。
  • 希尔排序的第一步是设计增量（一般默认为序列长度的一半）。

在这里插入图片描述

  • 开始分组，第一组从0 开始，以增量5为例，我们需要 0 ，5，10位置的数据进行交换（这里是用直接插入排序来进行的交换）。
    在这里插入图片描述
  • 那么第2组就是从1开始，以增量5为例，我们需要1,6位置的数据进行交换。依次下去，直到最后一个元素。
  • 增量就需要进行再次改变，设置为之前的一半，向下取整。例如 5/2=2 。
  • 继续分组交换数据（这里是用直接插入排序来进行的交换）。

增量会不断减小的，为了得到最终结果，我们的最后一个增量是1的大小，只有这样才能得到最终结果。

2、代码实现（C语言）

void shellSort(int arr[],int n){int gap;for(gap=n/2;gap>0;gap/=2){//确定增量for(int i = 0;i<gap;++i){//每一个增量的分组个数for(int j = i+gap;j<n;j+=gap){//直接插入排序int temp = arr[j];int k = j-gap;while(k>-1&&temp<arr[k]){arr[k+gap]=arr[k];k-=gap;}arr[k+gap]=temp;}}}
}
int main(int argc, char const *argv[])
{int arr[]={36,27,20,60,55,7,28,36,67,44,16};shellSort(arr,11);for(int i =0;i<11;++i){printf("%d ",arr[i]);}printf("\n");return 0;
}

三、冒泡排序

冒泡排序视频。

1、原理

  • 每一轮的相邻元素进行比较，这2个元素，如果逆序，就交换数据。
  • 每轮可以排好1个元素，总共n-1轮，每轮都会少比较一对数据。

由此我们可知：
n是元素个数。
轮数是n-1次。
比较是n-i-1次。i 是第几轮。

2、代码实现（C语言）

  • 第1种方法----经典写法
void bubbleSort(int arr[],int n){for(int i =0;i<n-1;i++){//要进行的轮数,写成n也可以for(int j =0;j<n-i-1;j++){//比较的次数if(arr[j+1]<arr[j]){int temp = arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}
}
int main(int argc, char const *argv[])
{int arr[]={36,27,20,60,55,7,28,36,67,44,16};bubbleSort(arr,11);for(int i =0;i<11;++i){printf("%d ",arr[i]);}printf("\n");return 0;
}
  • 第2种方法-----标记交换
    • 有的时候，并不是每一轮都需要交换，flag标记上一轮是否交换了，就可以减少比较次数。
void bubbleSort(int arr[],int n){for(int i =0;i<n-1;i++){//要进行的轮数,写成n也可以int flag = 1;for(int j =0;j<n-i-1;j++){//比较的次数if(arr[j+1]<arr[j]){int temp = arr[j];arr[j]=arr[j+1];arr[j+1]=temp;flag = 0;//交换了，flag改为0}}if(flag==1){break;}}
}
int main(int argc, char const *argv[])
{int arr[]={36,27,20,60,55,7,28,36,67,44,16};bubbleSort(arr,11);for(int i =0;i<11;++i){printf("%d ",arr[i]);}printf("\n");return 0;
}
  • 第3种方法----do while优化（推荐这种写法）
    • 先把newIndex设置为0，只要交换数据了，newIndex就改变。
      • newIndex来保存交换的元素位置
    • 下一次就只需要进行0到newIndex之间的比较，后面的元素不用比较了，因为它们是有序的。
    • 如果newIndex 没有变化，还是0，就说明不需要排序了。直接结束排序了。
void bubbleSort(int arr[],int n){int newIndex;int temp_length=n;do{newIndex = 0;for(int i =0;i<n-1;i++){if(arr[i]>arr[i+1]){int temp = arr[i];arr[i]=arr[i+1];arr[i+1]=temp;newIndex = i+1;}}n=newIndex;}while(newIndex>0);
}

四、简单选择排序

简单选择排序

1、原理

  • 每次从待排序序列中选择最小（或最大）的元素，放到已排序序列的末尾（或前面），直到全部元素有序。

2、代码实现（Cpp语言和c语言）

  • cpp版本
void selectionSort(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; i++) {int minIndex = i;  // 记录最小元素的索引for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}swap(arr[i], arr[minIndex]);  // 将最小值放到已排序区间末尾}
}
  • c语言版本
void selectSort(int arr[],int n){for(int i =0;i<n;i++){int minIndex = i;for(int j =i+1;j<n;j++){if(arr[j]<arr[minIndex]){minIndex=j;}}swap(arr[minIndex],arr[i]);}
}

五、快速排序

1、原理

  • 第一步：确定枢轴（pivot），枢轴可以是任意位置。
  • 第二步：设置left、right指针来寻找第一个比pivot大的元素和第一个比pivot小的元素，然后交换这2个元素。
  • 递归处理，直到空或只剩下一个为止。

2、代码实现（C语言）

  • 第1种：双边循环

/*#include <stdio.h>
#include <vector>
#include<iostream>
#include<cmath>
#include<algorithm>
#include <ctime>
using namespace std;
int quickDoubleSort(int arr[],int startIndex,int endIndex){srand(time(NULL));swap(arr[startIndex],arr[rand()%(endIndex-startIndex+1)+startIndex]);int pivot = arr[startIndex];int left = startIndex;int right = endIndex;while(left<right){while(left<right&&arr[left]<=pivot){left++;}while(left<right&&pivot<arr[right]){right--;}if(left<right){swap(arr[left],arr[right]);}}swap(arr[left],arr[startIndex]);return left;
}
void quickSort(int arr[],int startIndex,int endIndex){if(startIndex>=endIndex)return;int pivot = quickDoubleSort(arr,startIndex,endIndex);quickSort(arr,startIndex,pivot-1);quickSort(arr, pivot+1,endIndex);
}
int main() {int arr[]={36,27,20,60,55,7,28,36,67,44,16};//             36     27     20    16     55     7     28    36     67     44     60//             36     27     20    16     36     7     28    55     67     44     60int n =sizeof(arr)/sizeof(arr[0]);quickSort(arr,0,n-1);for(int i =0;i<n;++i){printf("%d ",arr[i]);}printf("\n");return 0;
}*/
#include <stdio.h>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;int quickDoubleSort(int arr[], int startIndex, int endIndex) {srand(time(NULL));int randomIndex = rand() % (endIndex - startIndex + 1) + startIndex;swap(arr[startIndex], arr[randomIndex]);  // 随机选择基准并交换到开头int pivot = arr[startIndex];  // 现在再取基准值int left = startIndex;int right = endIndex;while (left < right) {while (left < right && arr[right] > pivot) {  // 先移动 right，避免 left 越界right--;}while (left < right && arr[left] <= pivot) {  // 再移动 leftleft++;}if (left < right) {swap(arr[left], arr[right]);}}swap(arr[left], arr[startIndex]);  // 把基准值放到正确位置return left;
}void quickSort(int arr[], int startIndex, int endIndex) {if (startIndex >= endIndex) return;int pivot = quickDoubleSort(arr, startIndex, endIndex);quickSort(arr, startIndex, pivot - 1);quickSort(arr, pivot + 1, endIndex);
}int main() {int arr[] = {36, 27, 20, 60, 55, 7, 28, 36, 67, 44, 16};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);for (int i = 0; i < n; ++i) {printf("%d ", arr[i]);}printf("\n");return 0;
}
  • 第2种：单边循环
int singleQuickSort(int arr[],int startIndex,int endIndex){int tmp = arr[startIndex];int mark = startIndex;for(int i = startIndex+1;i<=endIndex;++i){if(arr[i]<tmp){mark++;swap(arr[mark],arr[i]);}}swap(arr[mark],arr[startIndex]);return mark;
}
void singleQuick(int arr[],int startIndex,int endIndex){if(startIndex>=endIndex)return;int pivot= singleQuickSort(arr,startIndex,endIndex);singleQuick(arr,startIndex,pivot-1);singleQuick(arr,pivot+1,endIndex);
}
int main(int argc,char*const argv[]){int arr[]={36,27,20,60,55,7,28,36,67,44,16};int n = sizeof(arr) / sizeof(arr[0]);singleQuick(arr,0,n-1);for(int i =0;i<n;i++){printf("%d ");}printf("\n");
}
  • 第3种：算法常用的写法—ACWing里面的写法。(c++)
  • 可以发现到，它没有swap( arr [ mark ] , q[ i ] )这一步，所以它是把这一步放入到了quick_sort( q , l , j ) 。
#include <algorithm>
#include <vector>
#include<iostream>
using namespace std;
const int N = 1e5+10;
int q[N];
int n;
void quick_sort(int q[],int l,int r){if(l>=r)return;int x = q[l];int i = l-1;int j = r+1;while(i<j){do i++;while(q[i]<x);do j--;while(q[j]>x);if(i<j)swap(q[i],q[j]);}quick_sort(q,l,j);quick_sort(q,j+1,r);
}
int main(int argc,char*const argv[]){cin>>n;for(int i =0;i<n;i++){cin>>q[i];}quick_sort(q,0,n-1);for(int i=0;i<n;i++){cout<<q[i]<<" ";}cout<<endl;
}

六、堆排序

堆排序视频

1、原理

1.1、大根堆
  • 大根堆（完全二叉树）
    • 任一节点大于等于左右孩子
    • 第i节点的左孩子是2i，右孩子是2i+1，而它的父亲是i/2的绝对值。【下标1开始存储的规律】
    • 虽然是完全二叉树的理想结构，实际上是用数组来存储数据，进行操作。

步骤

  • 1、插入节点
    • 是插入到完全二叉树的最后一个位置。然后开始上移操作。
  • 2、获取/移除最小元素
    • 获取和删除的是堆顶节点。
    • 删除后，就需要把最后一个节点临时补充到原本堆顶的位置。再判断堆顶的顺序进行交换。
1.2、小根堆
  • 小根堆（完全二叉树）
    • 任一节点小于等于左右孩子
    • 第i节点的左孩子是2i，右孩子是2i+1，而它的父亲是i/2的绝对值。【下标1开始存储的规律】
    • 虽然是完全二叉树的理想结构，实际上是用数组来存储数据，进行操作。

步骤

  • 1、插入节点
    • 是插入到完全二叉树的最后一个位置。然后开始上移操作。
  • 2、获取/移除最小元素
    • 获取和删除的是堆顶节点。
    • 删除后，就需要把最后一个节点临时补充到原本堆顶的位置。再判断堆顶的顺序进行交换。

在这里插入图片描述
在这里插入图片描述

  • 时间复杂度
    • 插入 (push)：O(log n)
    • 删除 (pop)：O(log n)
    • 获取堆顶 (top)：O(1)

2、代码实现（Cpp语言）

  • 大根堆
#include <algorithm>
#include <vector>
#include<iostream>
using namespace std;
class MaxHeap{
private:vector<int> heap;//  i/2              (j-1)/4//   i        =>     (j-1)/2//2i    2i+1     j-1           j//上浮调整(插入时，使用)void shiftUp(int index){//index是插入的位置while(index>0){int parent = (index-1)/2;if(heap[parent]>=heap[index]){break;}swap(heap[parent],heap[index]);index = parent;}}//下浮调整(删除时，使用)void shiftDown(int index){int size = heap.size();int leftChild = 2*index+1;while(leftChild<size){int rightChild = leftChild+1;int maxChild = leftChild;//假设左节点是最大值if(rightChild<size&&heap[rightChild]>heap[leftChild]){maxChild = rightChild;}if(heap[index]>=heap[maxChild]){break;//当前节点是最大}swap(heap[index],heap[maxChild]);index = maxChild;leftChild=2*index +1;}}
public:void push(int val){heap.push_back(val);shiftUp(heap.size()-1);}void pop(){if(heap.empty())return;//为空就不进行了swap(heap[0],heap.back());heap.pop_back();shiftDown(0);}int top()const{if(!heap.empty())return heap[0];throw runtime_error("Heap is empty");}bool empty()const{return heap.empty();}
};
int main(int argc,char*const argv[]){// 大根堆测试MaxHeap maxHeap;maxHeap.push(3);maxHeap.push(1);maxHeap.push(4);std::cout << "MaxHeap Top: " << maxHeap.top() << std::endl; // 4maxHeap.pop();std::cout << "After pop, MaxHeap Top: " << maxHeap.top() << std::endl; // 3cout<<endl;
}
  • 小根堆
class MinHeap {
private:std::vector<int> heap;void siftUp(int idx) {while (idx > 0) {int parent = (idx - 1) / 2;if (heap[parent] <= heap[idx]) break;  // 父节点更小，无需调整std::swap(heap[parent], heap[idx]);idx = parent;}}void siftDown(int idx) {int size = heap.size();int leftChild = 2 * idx + 1;while (leftChild < size) {int rightChild = leftChild + 1;int minChild = leftChild; // 假设左子节点是最小值if (rightChild < size && heap[rightChild] < heap[leftChild]) {minChild = rightChild; // 右子节点更小}if (heap[idx] <= heap[minChild]) break;  // 当前节点已满足小根堆性质std::swap(heap[idx], heap[minChild]);idx = minChild;leftChild = 2 * idx + 1;}}public:void push(int val) {heap.push_back(val);siftUp(heap.size() - 1);}void pop() {if (heap.empty()) return;std::swap(heap[0], heap.back());heap.pop_back();siftDown(0);}int top() const {if (!heap.empty()) return heap[0];throw std::runtime_error("Heap is empty");}bool empty() const {return heap.empty();}
};
#include <iostream>
#include <vector>
int main() {// 小根堆测试MinHeap minHeap;minHeap.push(3);minHeap.push(1);minHeap.push(4);std::cout << "MinHeap Top: " << minHeap.top() << std::endl; // 1minHeap.pop();std::cout << "After pop, MinHeap Top: " << minHeap.top() << std::endl; // 3return 0;
}

七、归并排序

归并排序视频

1、原理

  • 分治思想
    • 将数组递归地二分，直到子数组长度为1（天然有序）
    • 合并两个已排序的子数组
  • 合并操作
    • 用双指针比较两个子数组的元素
    • 每次选择较小者放入新数组
    • 剩余元素直接追加

2、代码实现（C语言）

static void merge(int arr[],int left,int right,int mid){const int n1 = mid - left+1;//左边空间的个数const int n2 = right - mid;//右边空间的个数int arr1[n1];//暂时存储左边的值int arr2[n2];//暂时存储右边的值for(int i =0;i<n1;++i){arr1[i]=arr[left+i];}for(int i =0;i<n2;++i){arr2[i]=arr[mid+1+i];}int i =0;int j =0;int k =left;while(i<n1&&j<n2){if(arr1[i]<=arr2[j]){arr[k]=arr1[i++];}else if(arr1[i]>arr2[j]){arr[k]=arr2[j++];}++k;}//不一定全部arr数据都重新传入了，可能还剩一些while(i<n1){arr[k++]=arr1[i++];}while(j<n2){arr[k++]=arr2[j++];}
}
void mergeLoop(int arr[],int left,int right){if(left==right){return;}int mid = (left+right)/2;mergeLoop(arr,left,mid);mergeLoop(arr,mid+1,right);//拆分完后进行归并merge(arr,left,right,mid);
}
int main(int argc,char*const argv[]){int arr[] = {36 ,27 ,20 ,60 ,55 ,7 ,28 ,36, 67 ,44 ,16};int n =sizeof(arr)/sizeof(arr[0]);mergeLoop(arr,0,n-1);for(int i =0;i<n;++i){printf("%d ",arr[i]);}
}

八、基数排序

基数排序视频。

1、原理

  • 基数排序的核心：
    • 将整数按每一位（从低位到高位，或高位到低位）依次排序。由于每个位的排序必须稳定（相同值的元素顺序不变），多次排序后整体数组有序。
  • 具体步骤（以 LSD 为例）：
    • 确定最大数的位数（决定排序轮次）。
    • 从最低位开始（个位 → 十位 → 百位…）：
    • 将数字按当前位的数值分到 10 个桶（0~9）。
    • 按桶顺序（0→9）合并所有元素，形成新数组。
    • 重复步骤 2 直到所有位处理完毕。
      在这里插入图片描述

2、代码实现（Cpp语言）（支持非负整数）

#include <vector>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
void radixSort(vector<int>&arr){if(arr.empty())return ;//找到最大数的位数int maxVal = *max_element(arr.begin(),arr.end());//获取最大数int maxDigit = 0;//记录位数while(maxVal>0){maxVal/=10;maxDigit++;}//从低到高位排序vector<vector<int>>buckets(10);//设置10个桶for(int i =0;i<maxDigit;i++){//将元素按当前位分到桶中for(int num:arr){int digit = (num/static_cast<int>(pow(10,i)))%10;//digit的作用是 从整数 num 中提取第 i 位的数字（从右往左数，最低位为第0位）//pow计算 10 的 i 次方//static_cast<int>强制转换，避免浮点数影响//num/pow(10,i)将num右移i位，例如num=1234->1234/100 = 12//%10:得到最右边的数字 12%10=2buckets[digit].push_back(num);}//合并桶，形成新的数组int index =0;for(auto & bucket:buckets){for(int num:bucket){arr[index++]=num;}bucket.clear();}}
}int main() {std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};radixSort(arr);std::cout << "Sorted Array: ";for (int num : arr) {std::cout << num << " ";}// 输出：2 24 45 66 75 90 170 802return 0;
}
  • 例子
原数组：[170, 45, 75, 90, 802, 24, 2, 66]
最大数 802 → 3 位第一轮（个位）分桶：
0: 170, 90 
2: 802, 2
4: 24
5: 45, 75
6: 66
合并后：[170, 90, 802, 2, 24, 45, 75, 66]第二轮（十位）分桶：
0: 802, 2
2: 24
6: 66 
7: 170, 75 
9: 90 
5: 45 
合并后：[802, 2, 24, 45, 66, 170, 75, 90]第三轮（百位）分桶：
0: 2, 24, 45, 66, 75, 90 
8: 802 
合并后：[2, 24, 45, 66, 75, 90, 802]

http://www.mrgr.cn/news/98954.html

相关文章：

  • Model Context Protocol (MCP) 开放协议对医疗多模态数据整合的分析路径【附代码】
  • 【失败】Gnome将默认终端设置为 Kitty
  • 【从零实现高并发内存池】申请、释放内存过程联调测试 与 大于256KB内存申请全攻略
  • 2D物体检测学习
  • C++ `shared_ptr` 多线程使用
  • 深入理解C++中string的深浅拷贝
  • day1-小白学习JAVA---JDK安装和环境变量配置（mac版）
  • 认知觉醒是什么? 如何做到 ? ( 持续更新ing )
  • cpolar 内网穿透 实现公网可以访问本机
  • [编程基础] Java · 学习手册
  • MATLAB 控制系统设计与仿真 - 35
  • 下拉框select标签类型
  • 基于linux 设置无线网卡Monitor模式 sniffer抓包
  • Git-使用教程（新手向）
  • 向量数据库前沿：Faiss 向量数据库的配置与使用（文中有彩蛋）
  • 高频面试题：Android MVP/MVVM/MVI这几种架构在实际生产中，各自的优缺点和适用场景是什么
  • STM32单片机C语言
  • 《系统分析师-第三阶段—总结（一）》
  • SQL：聚合函数（Aggregate Functions）
  • docker.desktop下安装普罗米修斯prometheus、grafana并看服务器信息