常见的8种排序(含代码):插入排序、冒泡排序、希尔排序、快速排序、简单选择排序、归并排序、堆排序、基数排序

本文主要是介绍常见的8种排序(含代码):插入排序、冒泡排序、希尔排序、快速排序、简单选择排序、归并排序、堆排序、基数排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

时间复杂度O(n^2)

1、插入排序 (Insertion Sort)

        从第一个元素开始,该元素可以认为已经被排序;取出下一个元素,在已经排序的元素序列中从后向前扫描;如果该元素(已排序)大于新元素,将该元素移到下一位置;重复步骤,直到找到已排序的元素小于或者等于新元素的位置;将新元素插入到该位置后。

void insertionSort(int arr[], int n) {  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  while (j >= 0 && arr[j] > key) {  arr[j + 1] = arr[j];  --j;  }  arr[j + 1] = key;  }  
}

2、冒泡排序 (Bubble Sort)

        重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

void bubbleSort(int arr[], int n) {  for (int i = 0; i < n - 1; ++i) {  for (int j = 0; j < n - i - 1; ++j) {  if (arr[j] > arr[j + 1]) {  std::swap(arr[j], arr[j + 1]);  }  }  }  
}

3、简单选择排序 (Selection Sort)

        每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

void selectionSort(int arr[], int n) {  for (int i = 0; i < n - 1; i++) {  int min_idx = i;  for (int j = i + 1; j < n; j++) {  if (arr[j] < arr[min_idx]) {  min_idx = j;  }  }  std::swap(arr[min_idx], arr[i]);  }  
}  

时间复杂度O(nlog2n)

4、希尔排序(Shell Sort)

        是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法的基本思想是:先将整个待排序的记录序列分割成为若干子序列(由相隔某个“增量”的记录组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。
(这里只给出增量的简化选择,实际应用中增量序列的选择会更复杂)

void shellSort(int arr[], int n) {  int gap = n / 2;  while (gap > 0) {  for (int i = gap; i < n; ++i) {  int temp = arr[i];  int j = i;  while (j >= gap && arr[j - gap] > temp) {  arr[j] = arr[j - gap];  j -= gap;  }  arr[j] = temp;  }  gap /= 2;  }  
}

5、快速排序(Quick Sort)

        通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

int partition(int arr[], int low, int high) {  int pivot = arr[high];  int i = (low - 1);  for (int j = low; j <= high - 1; j++) {  if (arr[j] < pivot) {  i++;  std::swap(arr[i], arr[j]);  }  }  std::swap(arr[i + 1], arr[high]);  return (i + 1);  
}  void quickSort(int arr[], int low, int high) {  if (low < high) {  int pi = partition(arr, low, high);  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  
}

6、堆排序(Heap Sort)

        堆排序是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。堆排序主要要解决两个问题:

        1)如何根据给定的序列建初始堆

         2)如何在交换掉根结点后,将剩下的结点调整为新的堆(筛选)

void set(int p,int m){//小顶堆int i,j;i=p;j=i*2;while(j<=m){if(j<=m-1&&k[j]>k[j+1])//改为<j++;if(k[j]>=k[i])//改为<=,则为大顶堆break;else{swap(k[i],k[j]);i=j;j=i*2;}}
}void heapSort(){int i,j;for(i=n/2;i>0;i--)//建堆set(i,n);for(i=n;i>1;i--)//排序{swap(k[i],k[1]);set(1,i-1);}
}

7、归并排序 (Merge Sort)

        归并排序采用分治法的思想,将数组分成两半,分别对它们进行排序,然后将结果合并起来。

        1)编写一个辅助函数来合并两个已排序的子数组。

        2)编写主归并排序函数,该函数将递归地分解数组,直到子数组只包含一个元素(已排序),然后合并这些子数组,直到整个数组排序完成。

void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {  int i = 0, j = 0, k = 0;  while (i < leftSize && j < rightSize) {  if (left[i] <= right[j]) {  arr[k++] = left[i++];  } else {  arr[k++] = right[j++];  }  }  while (i < leftSize) {  arr[k++] = left[i++];  }  while (j < rightSize) {  arr[k++] = right[j++];  }  
}  void mergeSort(int arr[], int left, int right) {  if (left < right) {  int mid = left + (right - left) / 2;  int leftSize = mid - left + 1;  int rightSize = right - mid;  int leftArr[leftSize], rightArr[rightSize];  // 拷贝数据到临时数组  for (int i = 0; i < leftSize; i++) {  leftArr[i] = arr[left + i];  }  for (int j = 0; j < rightSize; j++) {  rightArr[j] = arr[mid + 1 + j];  }  // 递归地对子数组进行排序  mergeSort(leftArr, 0, leftSize - 1);  mergeSort(rightArr, 0, rightSize - 1);  // 合并两个已排序的子数组  merge(arr, leftArr, leftSize, rightArr, rightSize);  }  
}  

时间复杂度O(d(n+rd))

8、基数排序(Radix Sort)

        基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。为了适用于负数和非整数,这里给出一个简化的版本,仅适用于非负整数,并且假设所有整数的位数相同(或可以通过填充前导零来使它们具有相同的位数)。

#include <vector>  
#include <algorithm>  void countingSort(std::vector<int>& arr, int exp) {  std::vector<int> output(arr.size());  std::vector<int> count(10, 0);  // 存储每个桶中的元素数量  for (int i = 0; i < arr.size(); i++)  count[(arr[i] / exp) % 10]++;  // 更改count[i],使其包含每个数字小于或等于i的数量  for (int i = 1; i < 10; i++)  count[i] += count[i - 1];  // 构建输出数组  for (int i = arr.size() - 1; i >= 0; i--) {  output[count[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  }  // 复制回原数组  for (int i = 0; i < arr.size(); i++)  arr[i] = output[i];  
}  void radixsort(std::vector<int>& arr) {  int maxVal = *std::max_element(arr.begin(), arr.end());  // 找到最大数的位数  int exp = 1;  while (maxVal / exp > 0) {  countingSort(arr, exp);  exp *= 10;  }  
}  

或者

#include <iostream>  
#include <cmath>  
#include <algorithm> // 使用std::max来找到数组中的最大值  // 获取数组中的最大值  
int getMax(int arr[], int n) {  int mx = arr[0];  for (int i = 1; i < n; i++) {  if (arr[i] > mx) {  mx = arr[i];  }  }  return mx;  
}  // 基数排序函数  
void radixsort(int arr[], int n) {  // 找到数组中的最大值  int maxVal = getMax(arr, n);  // 基数排序使用计数排序作为子程序  // 这里为了简单起见,我们假设所有的整数都是非负的  // 如果有负数,需要做适当的转换  // 对每一位执行计数排序  for (int exp = 1; maxVal / exp > 0; exp *= 10) {  int output[n]; // 输出数组  int count[10] = {0}; // 计数器数组  // 存储每个元素的频次  for (int i = 0; i < n; i++) {  int index = (arr[i] / exp) % 10;  count[index]++;  }  // 更改count[i]的值,这样它现在包含位置i处之前的所有元素  for (int i = 1; i < 10; i++) {  count[i] += count[i - 1];  }  // 生成输出数组  for (int i = n - 1; i >= 0; i--) {  int index = (arr[i] / exp) % 10;  output[count[index] - 1] = arr[i];  count[index]--;  }  // 将排序后的元素复制回原数组  for (int i = 0; i < n; i++) {  arr[i] = output[i];  }  }  
}  int main() {  int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};  int n = sizeof(arr) / sizeof(arr[0]);  radixsort(arr, n);  std::cout << "Sorted array: \n";  for (int i = 0; i < n; i++) {  std::cout << arr[i] << " ";  }  std::cout << std::endl;  return 0;  
}

28edbba515494195b2405823ebde7468.png

 

这篇关于常见的8种排序(含代码):插入排序、冒泡排序、希尔排序、快速排序、简单选择排序、归并排序、堆排序、基数排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1084957

相关文章

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理;Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期

Java 方法重载Overload常见误区及注意事项

《Java方法重载Overload常见误区及注意事项》Java方法重载允许同一类中同名方法通过参数类型、数量、顺序差异实现功能扩展,提升代码灵活性,核心条件为参数列表不同,不涉及返回类型、访问修饰符... 目录Java 方法重载(Overload)详解一、方法重载的核心条件二、构成方法重载的具体情况三、不构

SQL中如何添加数据(常见方法及示例)

《SQL中如何添加数据(常见方法及示例)》SQL全称为StructuredQueryLanguage,是一种用于管理关系数据库的标准编程语言,下面给大家介绍SQL中如何添加数据,感兴趣的朋友一起看看吧... 目录在mysql中,有多种方法可以添加数据。以下是一些常见的方法及其示例。1. 使用INSERT I

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL 中的 CAST 函数详解及常见用法

《MySQL中的CAST函数详解及常见用法》CAST函数是MySQL中用于数据类型转换的重要函数,它允许你将一个值从一种数据类型转换为另一种数据类型,本文给大家介绍MySQL中的CAST... 目录mysql 中的 CAST 函数详解一、基本语法二、支持的数据类型三、常见用法示例1. 字符串转数字2. 数字

Python中win32包的安装及常见用途介绍

《Python中win32包的安装及常见用途介绍》在Windows环境下,PythonWin32模块通常随Python安装包一起安装,:本文主要介绍Python中win32包的安装及常见用途的相关... 目录前言主要组件安装方法常见用途1. 操作Windows注册表2. 操作Windows服务3. 窗口操作

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

ModelMapper基本使用和常见场景示例详解

《ModelMapper基本使用和常见场景示例详解》ModelMapper是Java对象映射库,支持自动映射、自定义规则、集合转换及高级配置(如匹配策略、转换器),可集成SpringBoot,减少样板... 目录1. 添加依赖2. 基本用法示例:简单对象映射3. 自定义映射规则4. 集合映射5. 高级配置匹

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧