C++ 数据结构算法 学习笔记(32) -五大排序算法

embedded/2024/10/24 1:41:08/

C++ 数据结构算法 学习笔记(32) -五大排序算法

选择算法

如下若有多个女生的身高需要做排序:

在这里插入图片描述

常规思维:

  1. 第一步先找出所有候选美女中身高最高的，与最后一个数交换

在这里插入图片描述

  1. 第二步再找出除最后一位美女外其它美女中的最高者，与倒数第二个美女交换位置

在这里插入图片描述

  1. 再找出除最后两位美女外其它美女中的最高者，与倒数第三个美女交换位置，因为倒数 第三个本身已是最大的，所以实际无需交换.

在这里插入图片描述

  1. 重复以上步骤，直到最后只剩下一人，此时，所有的美女均已按照身高由矮到高的 顺序排列

在这里插入图片描述

代码实现:

#include<stdio.h>
#include<stdlib.h>
void swap(int* num1, int* num2)//交换两个变量的值
{int temp = *num1;*num1 = *num2;*num2 = temp;
}void SelectSort1(int arr[], int len) {for (int i = 0; i < len - 1; i++) {int max = 0;for (int j = 1; j < len - i; j++) { //查找未排序的元素if (arr[j] > arr[max]) { //找到目前最小值max = j;}}//printf("max:%dbeauties%d\n",max,len-i-1);if (max != (len - i - 1)) {swap(&arr[max], &arr[len - i - 1]);}}
}
void SelectSort2(int arr[], int len) {int i, j;for (i = 0; i < len - 1; i++){int min = i;for (j = i + 1; j < len; j++) { //查找未排序的元素if (arr[j] < arr[min]) { //找到目前最小值min = j; //记录最小值}}swap(&arr[min], &arr[i]); //交换}
}
int main(void) {int beauties[] = { 163,161,158,165,171,170,163,159,162 };int len = sizeof(beauties) / sizeof(beauties[0]);SelectSort2(beauties, len);for (int i = 0; i < len; i++) {printf("%d ", beauties[i]);}system("pause");
}

冒泡算法

当我们采用前面的选择排序时，我们仍然要将候选者遍历5遍，才能完成最终的排序，但其 实，本身这些美女出了第一个外，已经很有序了，我们只需要把第一个和第二个交换，然后又和 第三个交换，如此循环，直到和最后一个交换后，整个数组基本就有序了！

在这里插入图片描述

当然，并不是每次都这么幸运，像下面的情况就会更复杂一些，一趟并不能完全解决问题， 我们需要多趟才能解决问题.

在这里插入图片描述

经过上述五步后,得到的结果:

在这里插入图片描述

此时,我们只保障了最后一个数是最大的,并不能保障前面的数一定会有序,所以,我们继续按 照上面五步对剩下的5个数继续进行一次排序,数组就变得有序了. 以上过程就是冒泡排序:通过重复地遍历未排序的数列，一次比较两个元素，如果它们的顺 序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列 已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢得像泡泡一样“浮”到数 列的顶端,故而得名

代码实现:

#include <iostream>
#include <string>using namespace std;void swap(int* tmp1, int* tmp2)
{int tmp3 = *tmp1;*tmp1 = *tmp2;*tmp2 = tmp3;
}int main()
{int height2[] = { 156,162,161,172,167,169,155 };int height[] = { 155,158,161,163,172,174 };int size = sizeof(height) / sizeof(height[0]);for (int i = 0; i < size-1; i++){bool sorted = true;for (int j = 0; j < size-i-1; j++){if (height[j] > height[j+1]){	sorted = false;swap(&height[j], &height[j + 1]);}}if (sorted == true)	break;}for (int i = 0; i < size; i++){cout << height[i] << " ";}system("pause");return 0;
}

插入排序

在这里插入图片描述

  1. 首先,我们只考虑第一个元素,从第一个元素171开始，该元素可以认为已经被排序；

在这里插入图片描述

  1. 取下一个元素161并记录，并让161所在位置空出来,在已经排序的元素序列中从后向前扫 描；

    在这里插入图片描述

  2. 该元素（171）大于新元素，将该元素移到下一位置；

    在这里插入图片描述

  3. 171前已经没有最大的元素了,则将161插入到空出的位置

    在这里插入图片描述

  4. 取下一个元素163，并让163所在位置空出来,在已经排序的元素序列中从后向前扫描；

    在这里插入图片描述

  5. 该元素（171）大于新元素163，将该元素移到下一位置

    在这里插入图片描述

  6. 继续取171前的元素新元素比较,直到找到已排序的元素小于或者等于新元素的位置；新 元素大于161,则直接插入空位中

    在这里插入图片描述

  7. 重复步骤2~7，直到完成排序

    在这里插入图片描述

插入排序:它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描， 找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间 的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供 插入空间。

具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序；

  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；

  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置； 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

  4. 将新元素插入到该位置； 重复步骤2~5

代码实现::

#include <iostream>
#include <string>using namespace std;void InsertSort(int* height, int size) 
{int current = 0;int preIndex = 0;for (int i = 1; i < size; i++){current = height[i];preIndex = i-1;while (preIndex >= 0 && height[preIndex] > current){height[preIndex + 1] = height[preIndex];preIndex--;}height[preIndex + 1] = current;}
}int main()
{int height[] = { 152,163,161,159,172,170,168,151 };int size = (sizeof(height) / sizeof(height[0]));InsertSort(height, size);cout << "The sorting result is" << endl;for (int i = 0; i < size; i++){cout << height[i] << " ";}system("pause");return 0;
}

希尔排序

插入排序虽好,但是某些特殊情况也有很多缺点,比如像下面这种情况

在这里插入图片描述

169前的元素基本不用插入操作就已经有序,元素1和2的排序几乎要移动数组前面的所有 元素!!!于是,有个老帅哥就提出了优化此问题的希尔排序!

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排 序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。它与插入排序 的不同之处在于，它会优先比较距离较远的元素。

希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐 渐减少，每组包含的元素越来越多，当增量减至1时，所有元素被分成一组,实际上等同于执行一 次上面讲过的插入排序，算法便终止。

希尔排序的基本步骤：

选择增量：gap=length/2，缩小增量：gap=gap/2

增量序列：用序列表示增量选择，{n/2,(n/2)/2,…,1}

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

按增量序列个数k，对序列进行k趟排序；

每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进 行直接插入排序;

仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

在这里插入图片描述

#include <iostream>
#include <string>
using namespace std;void InsertSort(int arr[], int len)
{int gap = len / 2;for (; gap > 0; gap = gap / 2) {for (int i = gap; i < len; i++) {int current = arr[i];int j = 0;for (j = i - gap; j >= 0 && arr[j] > current; j -= gap) {arr[j + gap] = arr[j];}arr[j + gap] = current;}}
}int main()
{int height[] = { 152,163,161,159,172,170,168,151 };int size = (sizeof(height) / sizeof(height[0]));InsertSort(height, size);cout << "The sorting result is" << endl;for (int i = 0; i < size; i++){cout << height[i] << " ";}system("pause");return 0;
}

归并排序

当两个组数据已经有序，我们可以通过如下方式（以下简称归并大法）让两组数据快速有序

在这里插入图片描述

我们可以依次从两组中取最前面的那个最小元素依次有序放到新的数组中，然后再把新数组 中有序的数据拷贝到原数组中，快速完成排序
在这里插入图片描述

具体步骤:

对于下面这一组待排序的数组

在这里插入图片描述

先以中间为界，把其均分为A和B两个数组（如果是奇数个，允许两组数相差一个）

在这里插入图片描述

如果A和B两组数据能够有序，则我们可以通过上面的方式让数组快速排好序。 此时，A组有4个成员，B组有5个成员,但两个数组都无序，然后我们可以采用分治法继 续对A组和B组进行均分，以A组为例，又可以均分A1和A2两个组如下：

在这里插入图片描述

均分后，A1组和A2组仍然无序，继续利用分治法细分，以A1组为例，A1又可分成如下 两组

在这里插入图片描述

数组细分到一个元素后，这时候，我们就可以采用归并法借助一个临时数组将数组A1有序化！ A2同理！

在这里插入图片描述

依次类推，将A1组和A2组归并成有序的A组，B组同理！

在这里插入图片描述

最后，将A和B组使用归并大法合并，就得到了完整的有序的结果！

在这里插入图片描述

代码实现:

#include <iostream>
#include <string>using namespace std;//void mergeAdd_demo(int arr[], int left, int mid, int right)
//{
//	int temp[64] = { 0 };
//	int i = left;
//	int j = mid;
//	int k = 0;
//
//	while (i < mid && j <= right)
//	{
//		if (arr[i] < arr[j])
//		{
//			temp[k++] = arr[i++];
//		}
//		else
//		{
//			temp[k++] = arr[j++];
//		}
//	}
//	while (i < mid)
//	{
//		temp[k++] = arr[i++];
//	}
//
//	while (j <= right)
//	{
//		temp[k++] = arr[j++];
//	}
//
//	memcpy(arr + left, temp, sizeof(int) * (right - left + 1));
//}void mergeAdd(int arr[], int left, int mid, int right, int* temp)
{//int temp[64] = { 0 };int i = left;int j = mid;int k = left;while (i < mid && j <= right){if (arr[i] < arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}while (i < mid){temp[k++] = arr[i++];}while (j <= right){temp[k++] = arr[j++];}memcpy(arr + left, temp + left, sizeof(int) * (right - left + 1));
}void mergeSort(int arr[], int left, int right, int* temp)
{int mid = 0;if (left < right){mid = left+(right-left)/2;mergeSort(arr, left, mid, temp);mergeSort(arr, mid + 1, right, temp);mergeAdd(arr, left, mid+1, right, temp);}
}int main()
{int height[] = { 10,11,12,13,2,4,5,8 };int len = sizeof(height) / sizeof(height[0]);int* temp = new int[len];//int mid = len / 2;mergeSort(height, 0, len - 1, temp);//mergeAdd(height, 0, mid, len - 1,temp);for (int i = 0; i < len; i++){cout << height[i] << " ";}system("pause");return 0;
}

快速排序

具体做法为:

  1. 每次选取第一个数为基准数；
  2. 然后使用“乾坤挪移大法”将大于和小于基准的元素分别放置于基准数两边；
  3. 继续分别对基准数两侧未排序的数据使用分治法进行细分处理，直至整个序列有序。

对于下面待排序的数组:

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码实现:

#include <iostream>
#include <string>using namespace std;
int partition(int arr[], int low, int high)
{int i = low;int j = high;int base = arr[low];if (low < high){while (i < j){while (i < j && arr[j] >= base){j--;}if (i < j){arr[i++] = arr[j];}while (i < j && arr[i] < base){i++;}if (i < j){arr[j--] = arr[i];}}arr[i] = base;}return i;
}void QuickSort(int* arr, int low, int high)
{if (low < high){int index = partition(arr, low, high);QuickSort(arr, low, index - 1);QuickSort(arr, index + 1, high);}
}int main()
{int arr[] = { 163,161,158,165,171,170,163,159,162 };int len = sizeof(arr) / sizeof(arr[0]);//int index = partition(arr, 0, len - 1);QuickSort(arr, 0, len - 1);cout << "Executing the Quick Sort, result as" << endl;for (int i = 0; i < len; i++){cout << arr[i] << " ";}system("pause");return 0;
}

各大算法对比图

在这里插入图片描述


http://www.ppmy.cn/embedded/42821.html

相关文章

NB65 第k轻的牛牛

NB65 第k轻的牛牛

描述 在农场里&#xff0c;农民们有一群牛&#xff0c;每头牛的体重不同。农民们将所有牛的体重记录在一个数组中。现在农民们想要知道&#xff0c;如果将这些牛的体重从小到大排序&#xff0c;那么第k小的体重是多少。请你编写一个程序&#xff0c;找出数组中第k小的元素。 你…
阅读更多...
自定义RedisTemplate序列化器

自定义RedisTemplate序列化器

大纲 RedisSerializerFastJsonRedisSerializer自定义二进制序列化器总结代码 在《RedisTemplate保存二进制数据的方法》一文中&#xff0c;我们将Java对象通过《使用java.io库序列化Java对象》中介绍的方法转换为二进制数组&#xff0c;然后保存到Redis中。实际可以通过定制Red…
阅读更多...
MyBatis常见报错：org.apache.ibatis.binding.BindingException

MyBatis常见报错：org.apache.ibatis.binding.BindingException

哈喽&#xff0c;大家好&#xff0c;我是木头左&#xff01; 异常现象描述 当开发者在使用MyBatis进行数据库操作时&#xff0c;可能会遇到org.apache.ibatis.binding.BindingException: Parameter appId not found这样的错误提示。这个错误通常会让程序无法正常运行&#xff…
阅读更多...
leetcode每日一题第八十九天

leetcode每日一题第八十九天

class Solution { public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> mp;mp[0] 1;int count 0,pre 0;for(auto x:nums){pre x;if(mp.find(pre-k) ! mp.end()){count mp[pre-k];}mp[pre];}return count;} };
阅读更多...
Vue小程序项目知识积累（三）

Vue小程序项目知识积累（三）

1.CSS中的var( ) var() 函数用于插入自定义属性&#xff08;也称为CSS变量&#xff09;的值。 var(--main-bg-color,20rpx) 设置一个CSS变量的值&#xff0c;但是如果 --main-bg-color 变量不存在&#xff0c;它将默认返回 20rpx。 CSS变量必须在一个有效的CSS规则&#xf…
阅读更多...
Autodesk 3DS Max v2025 解锁版安装教程 (3D 建模软件)

Autodesk 3DS Max v2025 解锁版安装教程 (3D 建模软件)

前言 Autodesk 3ds Max 是一款功能强大的 3D 建模和动画解决方案&#xff0c;游戏开发人员、视觉效果艺术家和平面设计师使用它来创建庞大的世界、令人惊叹的场景和引人入胜的虚拟现实 (VR) 体验。 Autodesk 3DS MAX是业界使用最广泛的3D建模和动画软件程序之一&#xff0c;它…
阅读更多...
python-pytorch 下批量seq2seq+Bahdanau Attention实现问答1.0.000

python-pytorch 下批量seq2seq+Bahdanau Attention实现问答1.0.000

python-pytorch 下批量seq2seq+Bahdanau Attention实现简单问答1.0.000 前言原理看图数据准备分词、index2word、word2index、vocab_size输入模型的数据构造注意力模型decoder的编写关于损失函数和优化器在预测时完整代码参考前言 前面实现了 luong的dot 、general、concat注意…
阅读更多...
java继承使用细节二

java继承使用细节二

构造器 主类是无参构造器时会默认调用 public graduate() {// TODO Auto-generated constructor stub也就是说我这里要用构造器会直接调用父类。它是默认看不到的 &#xff0c;System.out.println("graduate");} 但当主类是有参构造器如 public father_(int s,doubl…
阅读更多...
最新文章

Copyright @ 2022~2023