【基础算法】(01) 十二种排序算法（第一篇）

2024-06-06 17:58
文章标签 算法 01 十二种 第一篇 排序 基础

本文主要是介绍【基础算法】(01) 十二种排序算法（第一篇），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【基础算法】(01) 十二种排序算法（第一篇）

Auther: Thomas Shen
E-mail: Thomas.shen3904@qq.com
Date: 2017/10/20
All Copyrights reserved !

      • 基础算法01 十二种排序算法第一篇
        • 总述
        • 直接插入排序 Straight Insertion Sort
        • 二分插入排序 Binary insert sort
        • 希尔Shell排序
        • 选择排序简单选择排序Simple Selection Sort
        • 选择排序堆排序Heap Sort
        • 交换排序冒泡排序Bubble Sort
        • 鸡尾酒排序双向冒泡排序
        • 交换排序快速排序Quick Sort
        • 归并排序Merge Sort
        • 桶排序 Bucket sort
        • 计数排序 Counting sort
        • 基数排序 Radix Sort
        • 总结
        • References

1. 总述：

本系列总结了常用的十二种排序算法，每个算法都包括算法原理, 代码实现, 面试例题 三部分。

其中本文是排序算法系列的第一篇，介绍了三种插入排序方法：

  • 2. 直接插入排序 (Straight Insertion Sort),
  • 3. 二分插入排序 （Binary Insert Sort),
  • 4. 希尔排序 （Shell’s Sort）

排序有内部排序和外部排序：

这里写图片描述

当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

排序算法大体可分为两种：

  • 一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：
    • 直接插入排序，希尔排序，
    • 冒泡排序，快速排序，
    • 简单选择排序，堆排序，
    • 归并排序，等。
  • 另一种是非比较排序，时间复杂度可以达到O(n)，主要有：
    • 计数排序，基数排序，桶排序等。

这里写图片描述

2. 直接插入排序 (Straight Insertion Sort)：

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

算法描述和分析:
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序;
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描;
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置;
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

这里写图片描述

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。

平均来说插入排序算法复杂度为O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

时间复杂度：O（n^2）；

2.2 代码实现：

void print(int a[], int n ,int i){  cout<<i <<":";  for(int j= 0; j<8; j++){  cout<<a[j] <<" ";  }  cout<<endl;  
}  void InsertSort(int a[], int n)  
{  for(int i= 1; i<n; i++){  if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入  int j= i-1;   int x = a[i];  //复制为哨兵，即存储待排序元素  a[i] = a[i-1]; //先后移一个元素  while(x < a[j]){  //查找在有序表的插入位置  a[j+1] = a[j];  j--;         //元素后移  }  a[j+1] = x;      //插入到正确位置  }  print(a,n,i);        //打印每趟排序的结果  }  
}  int main(){  int a[8] = {3,1,5,7,2,4,9,6};  InsertSort(a,8);  print(a,8,8);  
}

2.3 面试例题：

2.3.1 链表的插入排序程序:

template<typename T>  
struct list_node  
{  struct list_node<T> *next;  T value;  
};  
template<typename T>  
struct _list  
{  struct list_node<T> *head;  int size;  
};  
template<typename T>  
void SortLink(struct _list<T> * link) {  struct list_node<T> *pHead,*pRear,*p,*tp;  if (!link) return;  for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {  for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)  if (pHead->value>=p->value)  tp->next=p->next,p->next=pHead,pHead=p,p=tp;  if (!pRear) link->head=pHead;  else pRear->next=pHead;  pRear=pHead;  }  
}
3. 二分插入排序 （Binary insert sort)：

二分（折半）插入（Binary insert sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。

3.1 原理简介：

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序;
  2. 取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置;
  3. 将新元素插入到该位置后;
  4. 重复上述两步。
  • 稳定
  • 空间代价：O(1)
  • 时间代价：插入每个记录需要O(log i)比较，最多移动i+1次，最少2次。最佳情况O(n log n)，最差和平均情况O(n^2)。

二分插入排序是一种稳定的排序。当n较大时，总排序码比较次数比直接插入排序的最差情况好得多，但比最好情况要差，所元素初始序列已经按排序码接近有序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。

3.2 代码实现：

void BinInsertSort(int a[], int n)   
{   int key, left, right, middle;   for (int i=1; i<n; i++)   {   key = a[i];left = 0;   right = i-1;   while (left<=right){   middle = (left+right)/2;   if (a[middle]>key)   right = middle-1;   elseleft = middle+1;}for(int j=i-1; j>=left; j--)   {   a[j+1] = a[j];}              a[left] = key;          }   
}
4. 希尔（Shell）排序：

希尔排序（Shell`s Sort）相对直接排序有较大的改进。希尔排序又叫缩小增量排序。

4.1 原理简介：

  1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  2. 按增量序列个数k，对序列进行k 趟排序；
  3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序

4.2 代码实现：

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 …..1} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

void print(int a[], int n ,int i){  cout<<i <<":";  for(int j= 0; j<8; j++){  cout<<a[j] <<" ";  }  cout<<endl;  
}  
/** * 直接插入排序的一般形式 * @param int dk 缩小增量，如果是直接插入排序，dk=1 */  void ShellInsertSort(int a[], int n, int dk)  
{  for(int i= dk; i<n; ++i){  if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入  int j = i-dk;     int x = a[i];           //复制为哨兵，即存储待排序元素  a[i] = a[i-dk];         //首先后移一个元素  while(x < a[j]){     //查找在有序表的插入位置  a[j+dk] = a[j];  j -= dk;             //元素后移  }  a[j+dk] = x;            //插入到正确位置  }  print(a, n,i );  }  }  /** * 先按增量d（n/2,n为要排序数的个数进行希尔排序 */  
void shellSort(int a[], int n){  int dk = n/2;  while( dk >= 1  ){  ShellInsertSort(a, n, dk);  dk = dk/2;  }  
}  int main(){  int a[8] = {3,1,5,7,2,4,9,6};  //ShellInsertSort(a,8,1); //直接插入排序  shellSort(a,8);           //希尔插入排序  print(a,8,8);  
}

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的。

但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。

希尔排序方法是一个不稳定的排序方法。

5. 选择排序—简单选择排序（Simple Selection Sort）：
6. 选择排序—堆排序（Heap Sort）：
7. 交换排序—冒泡排序（Bubble Sort）：
8. 鸡尾酒排序/双向冒泡排序：
9. 交换排序—快速排序（Quick Sort）：
10. 归并排序（Merge Sort）：
11. 桶排序 (Bucket sort)：
12. 计数排序 (Counting sort)：
13. 基数排序 (Radix Sort)：

参见第二、三、四篇；

14. 总结：

这里写图片描述

References. ：
  • [ 1 ]. Coursera | Java程序设计 | PKU
  • [ 2 ]. 转载自：八大排序算法
  • [ 3 ]. 转载自：12种排序算法详解

这篇关于【基础算法】(01) 十二种排序算法（第一篇）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1036820。

相关文章

RedHat运维-Linux文本操作基础-AWK进阶

RedHat运维-Linux文本操作基础-AWK进阶

你不用整理，跟着敲一遍，有个印象，然后把它保存到本地，以后要用再去看，如果有了新东西，你自个再添加。这是我参考牛客上的shell编程专项题，只不过换成了问答的方式而已。不用背，就算是我自己亲自敲，我现在好多也记不住。 1. 输出nowcoder.txt文件第5行的内容 2. 输出nowcoder.txt文件第6行的内容 3. 输出nowcoder.txt文件第7行的内容 4. 输出nowcode
阅读更多...
Vim使用基础篇

Vim使用基础篇

本文内容大部分来自 vimtutor，自带的教程的总结。在终端输入vimtutor 即可进入教程。 先总结一下，然后再分别介绍正常模式，插入模式，和可视模式三种模式下的命令。 目录 看完以后的汇总 1.正常模式（Normal模式） 1.移动光标 2.删除 3.【:】输入符 4.撤销 5.替换 6.重复命令【. ; ,】 7.复制粘贴 8.缩进 2.插入模式 INSERT
阅读更多...
零基础STM32单片机编程入门(一)初识STM32单片机

零基础STM32单片机编程入门(一)初识STM32单片机

文章目录 一.概要二.单片机型号命名规则三.STM32F103系统架构四.STM32F103C8T6单片机启动流程五.STM32F103C8T6单片机主要外设资源六.编程过程中芯片数据手册的作用1.单片机外设资源情况2.STM32单片机内部框图3.STM32单片机管脚图4.STM32单片机每个管脚可配功能5.单片机功耗数据6.FALSH编程时间，擦写次数7.I/O高低电平电压表格8.外设接口
阅读更多...
ps基础入门

ps基础入门

1.基础      1.1新建文件      1.2创建指定形状      1.4移动工具          1.41移动画布中的任意元素          1.42移动画布          1.43修改画布大小          1.44修改图像大小      1.5框选工具      1.6矩形工具      1.7图层          1.71图层颜色修改          1
阅读更多...
C++入门01

C++入门01

1、.h和.cpp 源文件 (.cpp)源文件是C++程序的实际实现代码文件，其中包含了具体的函数和类的定义、实现以及其他相关的代码。主要特点如下：实现代码: 源文件中包含了函数、类的具体实现代码，用于实现程序的功能。编译单元: 源文件通常是一个编译单元，即单独编译的基本单位。每个源文件都会经过编译器的处理，生成对应的目标文件。包含头文件: 源文件可以通过#include指令引入头文件，以使
阅读更多...
代码随想录算法训练营：12/60

代码随想录算法训练营：12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ，Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充： 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用） 2. std::stringstream 3. std::atoi, std
阅读更多...
人工智能机器学习算法总结神经网络算法(前向及反向传播)

人工智能机器学习算法总结神经网络算法(前向及反向传播)

1.定义，意义和优缺点 定义: 神经网络算法是一种模仿人类大脑神经元之间连接方式的机器学习算法。通过多层神经元的组合和激活函数的非线性转换，神经网络能够学习数据的特征和模式，实现对复杂数据的建模和预测。(我们可以借助人类的神经元模型来更好的帮助我们理解该算法的本质，不过这里需要说明的是，虽然名字是神经网络，并且结构等等也是借鉴了神经网络，但其原型以及算法本质上还和生物层面的神经网络运行原理存在
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...
[FPGA][基础模块]跨时钟域传播脉冲信号

[FPGA][基础模块]跨时钟域传播脉冲信号

clk_a 周期为10ns clk_b 周期为34ns 代码: module pulse(input clk_a,input clk_b,input signal_a,output reg signal_b);reg [4:0] signal_a_widen_maker = 0;reg signal_a_widen;always @(posedge clk_a)if(signal_a)
阅读更多...
00 - React 基础

00 - React 基础

1. React 基础 安装react指令 可参考： 官网官网使用教程 如： npx create-react-app 项目名如：npx create-react-app react-redux-pro JSX JSX 是一种 JavaScript 的语法扩展，类似于 XML 或 HTML，允许我们在 JavaScript 代码中编写 HTML。 const element =
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2