## 数据结构与算法——排序（C语言实现）

news/2024/5/26 19:21:45/文章来源:https://blog.csdn.net/weixin_74967884/article/details/136577457

✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追风赶月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平芜尽处是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

#### 🍋排序

• 🍑插入排序
• 🍍直接插入排序
• 🍍希尔排序
• 🍑选择排序
• 🍍选择排序
• 🍍堆排序
• 🍑交换排序
• 🍍冒泡排序
• 🍍快速排序
• 🍌快排（经典写法）
• 🍌快排（挖坑法）
• 🍌快排（双指针法）
• 🍌快排优化
• 🍑归并排序
• 🍍归并排序（递归）
• 🍍归并排序（非递归）

## 🍑插入排序

### 🍍直接插入排序

``````#include<stdio.h>
/// 直接插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 2; i++){int end = i;int cur = a[end + 1];while (cur >= 0){if (cur < a[end]){a[end + 1] = a[end];}else{break;}end--;}a[end + 1] = cur;}
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);InsertSort(a, size);for (int i = 0; i < size; i++){printf("%d ", a[i]);}return 0;
}
``````

0到end有序，把end+1序列插入到前序序列

### 🍍希尔排序

``````void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//保证了gap最小为1for (int i = 0; i < n - gap; i = i + gap){int end = i;int cur = a[end + gap];while (end >= 0){if (cur < a[end]){a[end + gap] = a[end];}else{break;}end = end - gap;}a[end + gap] = cur;}}
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);ShellSort(a, size);for (int i = 0; i < size; i++){printf("%d ", a[i]);}return 0;
}
``````

gap的作用就是分成多少组，一组一组的排

## 🍑选择排序

### 🍍选择排序

``````void Swap(int* a1, int* a2)
{int cur = *a1;*a1 = *a2;*a2 = cur;
}
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = begin;int min = begin;for (int i = begin+1; i <= end; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[begin], &a[min]);if (max == begin)//特殊情况{max = min;}Swap(&a[max], &a[end]);begin++;end--;}
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);SelectSort(a, size);Print(a, size);return 0;
}
``````

``````if (max == begin)//特殊情况{max = min;}
``````

## 🍑交换排序

### 🍍冒泡排序

``````void Swap(int* a1, int* a2)
{int cur = *a1;*a1 = *a2;*a2 = cur;
}void BuddleSort(int* a, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);BuddleSort(a, size);for (int i = 0; i < size; i++){printf("%d ", a[i]);}return 0;
}
``````

### 🍍快速排序

#### 🍌快排（经典写法）

``````void Swap(int* a1, int* a2)
{int cur = *a1;*a1 = *a2;*a2 = cur;
}
int PartSort1(int* a, int left, int right)//单趟
{int key = left;while (left < right){while (left < right && a[right] >= a[key]){right--;}while (left < right && a[left] <= a[key]){left++;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[key]);return left;
}void QuickSort1(int* a, int left, int right)
{if (left >= right)return;int key = PartSort1(a, left, right);QuickSort1(a, left, key - 1);QuickSort1(a, key + 1, right);
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);QuickSort1(a, 0, size - 1);Print(a, size);return 0;
}``````

（1）第一个坑就是在第一个while循环中有left<right了有的人就认为在while程序内部就会一直维持left<right，其实是错的。在单趟的走法中，无论是right往右走，还是left往左走，都有可能left>right发生。
（2）第二个坑就是在判断条件a[key]>=a[right]或者a[key]<=a[left]中，等号可不可以去掉。在这里可以肯定的是这个等号是不可以去掉的，去掉的话会陷入无限循环中。

#### 🍌快排（挖坑法）

``````int PartSort2(int* a, int left, int right)
{int key = a[left];int hold = left;while (left < right){//找小while (left < right && a[right] >= key){right--;}a[hold] = a[right];hold = right;//找大while (left < right && a[left] <= key){left++;}a[hold] = a[left];hold = left;}a[hold] = key;return hold;
}void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int key = PartSort2(a, left, right);QuickSort2(a, left, key - 1);QuickSort2(a, key + 1, right);
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);QuickSort1(a, 0, size - 1);Print(a, size);return 0;
}``````

#### 🍌快排（双指针法）

``````void Swap(int* a1, int* a2)
{int cur = *a1;*a1 = *a2;*a2 = cur;
}
int PartSort3(int* a, int left, int right)
{int key = left;int cur = left + 1;int old = left;while (cur <= right){if (a[cur] <= a[key]){old++;Swap(&a[old], &a[cur]);}cur++;}Swap(&a[key], &a[old]);return old;
}void QuickSort3(int* a, int left, int right)
{if (left >= right)return;int key = PartSort3(a, left, right);QuickSort3(a, left, key - 1);QuickSort3(a, key + 1, right);
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);QuickSort3(a, 0, size - 1);Print(a, size);return 0;
}
``````

#### 🍌快排优化

``````// 三数取中
int GetMiddle(int* a, int left, int right)
{int mid = (left + right) / 2;// left mid rightif (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right])  // mid是最大值{return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]) // mid是最小{return left;}else{return right;}}
}``````

## 🍑归并排序

### 🍍归并排序（递归）

``````void _MergeSort(int* a, int *tem, int left, int right)
{//递归if (right <= left)return;int mid = (left + right) / 2;_MergeSort(a, tem, left, mid);_MergeSort(a, tem, mid+1, right);//归并，拷贝到tem中int left1 = left, right1 = mid;int left2 = mid + 1, right2 = right;int sum = left;while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){tem[sum++] = a[left1++];}else{tem[sum++] = a[left2++];}}while (left1 <= right1){tem[sum++] = a[left1++];}while (left2 <= right2){tem[sum++] = a[left2++];}memcpy(a + left, tem + left, (right - left + 1) * sizeof(int));}void MergeSort(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);if (tem == NULL){perror("malloc  fail");return;}_MergeSort(a, tem, 0, n - 1);free(tem);
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);MergeSort(a, size);Print(a, size);return 0;
}``````

### 🍍归并排序（非递归）

``````void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void MergeSortNort(int* a, int n)
{int* cur = (int*)malloc(n * sizeof(int));if (cur == NULL){perror("malloc  fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i = i + 2 * gap){int left1 = i, right1 = i + gap - 1;int left2 = i + gap, right2 = i + 2 * gap - 1;int sum = i;while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){cur[sum++] = a[left1++];}else{cur[sum++] = a[left2++];}}while (left1 <= right1){cur[sum++] = a[left1++];}while (left2 <= right2){cur[sum++] = a[left2++];}memcpy(a + i, cur + i, (2 * gap) * sizeof(int));}//printf("\n");gap = gap * 2;}}int main()
{int a[] = { 2,66,34,5,123,34,345,456, };int size = sizeof(a) / sizeof(a[0]);MergeSortNort(a, size);Print(a, size);return 0;
}
``````

``````void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void MergeSortNort(int* a, int n)
{int* cur = (int*)malloc(n * sizeof(int));if (cur == NULL){perror("malloc  fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i = i + 2 * gap){int left1 = i, right1 = i + gap - 1;int left2 = i + gap, right2 = i + 2 * gap - 1;printf("[%d  %d]  [%d  %d]\n", left1, right1, left2, right2);//如果第二组不存在，这一组就不用归并if (left2 >= n){break;}//如果第二组右边见越界了，就修正一下if (right2 >= n){right2 = n - 1;}int sum = i;while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){cur[sum++] = a[left1++];}else{cur[sum++] = a[left2++];}}while (left1 <= right1){cur[sum++] = a[left1++];}while (left2 <= right2){cur[sum++] = a[left2++];}memcpy(a + i, cur + i, (right2 - i + 1) * sizeof(int));}gap = gap * 2;}}int main()
{int a[] = { 2,66,34,5,123,34,345,456, 3};int size = sizeof(a) / sizeof(a[0]);MergeSortNort(a, size);Print(a, size);return 0;
}``````

### 探索Java高并发编程之道：理论与实践

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 简介 随着互联网和信息技术的快速发展&#x…

### 拼图小游戏制作教程：用HTML5和JavaScript打造经典游戏

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…

### 如何使用“Docker registry创建本地仓库，在服务器之间进行文件push和pull”？

1.1、在服务器1&#xff0c;运行registry docker run -d -p 5000:5000 -v \${PWD}/registry:/var/lib/registry --restart always --name registry registry:2.7.11.2、编辑/etc/docker/daemon.json 文件&#xff0c; 192.168.xxx.xxx 换成你自己 registry 服务的地址 sudo na…