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

一、插入排序

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 insert(int arr[],int n){for(int i =1;i<n;i++){int temp = arr[i];int j = i-1;while(j>-1&&temp<arr[j]){arr[j+1]=arr[j];--j;}arr[j+1]=temp;}
}
void binaryInsert(int arr[],int n){for(int i = 1;i<n;i++){int left=0;int right=i-1;int temp = arr[i];//二分查找待插入位置while(left<=right){int mid = (left+right)/2;if(arr[mid]>temp){right = mid-1;}else{left = mid+1;}}for(int j = i;j>left;j--){arr[j]=arr[j-1];}//插入元素arr[left]=temp;}
}
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]);binaryInsert(arr,n);for(int i =0;i<n;++i){printf("%d ",arr[i]);}printf("\n");return 0;
}

二、希尔排序

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个元素。【注意：先移动right，避免left越界，超过right】
• 递归处理，直到空或只剩下一个为止。

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));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 ",arr[i]);}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]