王道计算机数据结构+插入排序、冒泡排序、希尔排序、快速排序、简单选择排序

server/2024/12/23 1:22:15/

本内容是基于王道计算机数据结构的插入排序、冒泡排序、希尔排序、快速排序、简单选择排序整理。

文章目录

  • 插入排序
    • 算法
    • 性能
    • 代码
  • 冒泡排序
    • 算法
    • 性能
    • 代码
  • 希尔排序
    • 算法
    • 性能
    • 代码
  • 快速排序
    • 算法
    • 性能
    • 代码
  • 简单选择排序
    • 算法
    • 性能
    • 代码

插入排序

算法

算法思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成。

性能

  • 空间复杂度:O(1)
  • 时间复杂度:
    • 最好:原本就有序;O(n)
    • 最坏:原本为逆序;O(n2);
    • 平均:O(n2);
  • 稳定性:稳定;

代码

image.png
image.png
image.png

#include <iostream>
using namespace std;void InsertSort(int a[],int n) {int i, j, temp;for(i = 1; i < n; i++) {if (a[i] < a[i - 1]) {temp = a[i];for (j = i - 1; j >= 0 && a[j] > temp; j--) {a[j + 1] = a[j];}a[j + 1] = temp;}}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[8] = {38, 49, 65, 97, 76, 13, 27, 49};int n = 8;cout << "插入排序前的数组为: ";printfarray(a, n);cout << endl;InsertSort(a,n);cout << "插入排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png

冒泡排序

算法

  • 从后往前(或从前往后)两两比较相邻元素的值,若为逆序(即A[i-1]>A[i]),则交换它们,直到序列比较完。称这样过程为“一趟”冒泡排序。
  • 第一趟排序使关键字值最小的一个元素“冒”到最前面;
  • 每一趟排序都可以使一个元素移动到最终位置,已经确定最终位置的元素在之后的处理中无需再对比;
  • 若某一趟排序没有发生“交换”,说明此时已经整体有序。

性能

  • 空间复杂度:O(1)
  • 时间复杂度:
    • 最好:原本就有序;O(n)
    • 最坏:原本为逆序;O(n2);
    • 平均:O(n2);
  • 稳定性:稳定;

代码

image.png

#include <iostream>
using namespace std;void swap(int &a, int &b){int temp = a;a = b;b = temp;
}void BubbleSort(int a[],int n) {for(int i = 0; i < n-1; i++) {bool flag = false; // 表示本趟冒泡是否发生交换的标志for (int j = n - 1; j > i; j--) {if (a[j-1] > a[j]) {swap(a[j-1],a[j]);flag = true;}}if (flag == false) {return;}}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[8] = {38, 49, 65, 97, 76, 13, 27, 49};int n = 8;cout << "冒泡排序前的数组为: ";printfarray(a, n);cout << endl;BubbleSort(a,n);cout << "冒泡排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png

希尔排序

算法

  • 先将待排序表分割成若干形如L[i, i+d, i+2d, … ,i + kd]的“特殊”子表,对各个子表分别进行直接插入排序。缩小增量d,重复上述过程,直到d=1为止。
  • 先追求表中元素部分有序,再逐渐逼近全局有序。

性能

  • 空间复杂度:O(1)
  • 时间复杂度:未知,但优于直接插入排序
  • 稳定性:不稳定;

代码

image.png
image.png
image.png
image.png

#include <iostream>
using namespace std;void ShellSort(int a[],int n) {int i, j, d, temp;for (d = n / 2; d >= 1; d = d / 2) {for(i = d; i < n; i++) {if(a[i] < a[i-d]) {temp = a[i];for(j = i - d; j >= 0 && a[j] > temp; j-=d) {a[j + d] = a[j];}a[j + d] = temp;}}}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[11] = {38, 6, 9, 3, 49, 65, 97, 76, 13, 27, 49};int n = 11;cout << "希尔排序前的数组为: ";printfarray(a, n);cout << endl;ShellSort(a,n);cout << "希尔排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png

快速排序

算法

算法思想:在待排序表L[1 … n]中任取一个元素pivot作为枢轴(或基准,通常取首元素),通过一趟排序将待排序表划分为独立的两部分L[1 … k-1]和L[k+1 … n],使得L[1 … k-1]中的所有元素小于pivot,L[k+1 … n]中的所有元素大于等于pivot,则pivot放在了其最终位置L(k) 上,这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程,直至每部分内只有一个元素或空为止,即所有元素放在了其最终位置上。
算法表现主要取决于递归深度,若每次“划分”越均匀,则递归深度越低。“划分”越不均匀,递归深度越深。

性能

  • 空间复杂度:
    • 最好:O(n)
    • 最坏:O(log(n))
  • 时间复杂度:
    • 最好:每次划分很均匀;O(n2)
    • 最坏:原本为正序或逆序;O(n log(n));
    • 平均:O(n log(n));
  • 稳定性:不稳定;

代码

image.png
image.png

#include <iostream>
using namespace std;int Partition(int a[],int low, int high) {int pivot = a[low];while (low < high) {while(low < high && a[high] >= pivot) high--;a[low] = a[high];while(low < high && a[low] <= pivot) low++;a[high] = a[low];}a[low] = pivot;return low;
}void QuickSort(int a[],int low, int high) {if (low < high) {int pivotpos = Partition(a,low,high); // 划分QuickSort(a, low, pivotpos-1); // 划分左子表QuickSort(a, pivotpos + 1, high); // 划分右子表}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[11] = {38, 6, 9, 3, 49, 65, 97, 76, 13, 27, 49};int n = 11;cout << "快速排序前的数组为: ";printfarray(a, n);cout << endl;QuickSort(a,0,n-1);cout << "快速排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png

简单选择排序

算法

  • 每一趟在待排序元素中选取关键字最小的元素加入有序子序列
  • 必须进行总共 n - 1 趟处理;

性能

  • 空间复杂度:O(1)
  • 时间复杂度:O(n2)
  • 稳定性:不稳定;

代码

image.png

#include <iostream>
using namespace std;void swap(int &a, int &b){int temp = a;a = b;b = temp;
}void SelectSort(int a[],int n) {for (int i = 0; i < n-1; i++) {int min = i;for(int j = i + 1; j < n; j++) {if (a[j] < a[min])min = j;}if (min != i) {swap(a[i],a[min]);}}
}void printfarray(int a[], int n) {for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;
}int main() {int a[11] = {38, 6, 9, 3, 49, 65, 97, 76, 13, 27, 49};int n = 11;cout << "选择排序前的数组为: ";printfarray(a, n);cout << endl;SelectSort(a,n);cout << "选择排序后的数组为: ";printfarray(a, n);cout << endl;
}

image.png


http://www.ppmy.cn/server/59998.html

相关文章

sqlite 数据库 介绍

文章目录 前言一、什么是 SQLite &#xff1f;二、语法三、SQLite 场景四、磁盘文件 前言 下载 目前已经出到了&#xff0c; Version 3.46.0 SQLite&#xff0c;是一款轻型的数据库&#xff0c;是遵守ACID的关系型数据库管理系统&#xff0c;它包含在一个相对小的C库中。它是…

Redis基础教程(十九):Redis分区

&#x1f49d;&#x1f49d;&#x1f49d;首先&#xff0c;欢迎各位来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里不仅可以有所收获&#xff0c;同时也能感受到一份轻松欢乐的氛围&#xff0c;祝你生活愉快&#xff01; &#x1f49d;&#x1f49…

Docker常用操作速查表

Docker 文章目录 Docker1. 使用逻辑2. 镜像docker searchdocker pulldocker imagesdocker rmi 3. 容器docker rundocker psdocker stopdocker startdocker renamedocker logs 4. 容器-->镜像docker commit 5. 其他docker save/load 6. 构建docker buildDockerfile1. FROM2. …

测试驱动开发的艺术:Xcode中实现TDD的全面指南

测试驱动开发的艺术&#xff1a;Xcode中实现TDD的全面指南 在软件开发过程中&#xff0c;测试驱动开发&#xff08;Test-Driven Development&#xff0c;TDD&#xff09;是一种以测试为先导的开发模式&#xff0c;它强调先编写测试用例&#xff0c;再编写功能代码&#xff0c;…

codeforce 954 div3 G2题

思路&#xff1a; 质因子分解可以顺着分解&#xff0c;也可以逆着分解 即找到每一个数字的倍数&#xff0c;再找到每一个数字的因数 const int N 5e510; vector<int> ff[N]; vector<int> f[N]; vector<int> g[N];void solve(){int n;cin>>n;vector&l…

解决:使用WCHISPStudio_V360的RISCV系统出现由于找不到 CH375DLLDLL,无法继续执行代码。重新安装程序可能会解决此问题。

在使用WCHISPStudio_V360进行程序烧录的时候 选择riscv出现如下报错 说明你的电脑没有安装对应的驱动。 说明安装的程序有问题&#xff0c;无法在你的C:\Windows\SysWOW64中安装CH375DLL.DLL 解决方法一&#xff1a; 这个软件我是通过MounDriver打开的&#xff0c;所以重新执…

ubuntu18.04下载vscode

1、进入官网vscode下载对应的.deb安装包 2、打开文件对应目录下的终端进行安装 sudo dpkg -i code_1.73.1-1667967334_amd64.deb 3、运行vscode code 4、打开vscode安装中文包

新型开发语言的试用感受-仓颉语言发布之际

经常听一些媒体介绍一些新型的开发语言&#xff0c;所以最近心血来潮&#xff0c;安装了几种感受了一些。 先看名气&#xff0c;如ziglang&#xff0c;网址为&#xff1a;Home ⚡Zig Programming Language 号称是可以取代C语言的一门新语言&#xff0c;其实我主要是受下面这篇…