这篇小日志，简单哦整理了下直接插入排序，参考过 八大排序算法和度娘的直接插入排序。其中八大排序算法整理的比较好，这里Copy部分讲解作为自己记录。将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。源码方面开始参考的两篇文章，但在尽量精简代码上发现还可以在原有代码上进行优化，自己整理的代码如下： // 时间复杂性为 O(n^2)// 空间复杂度为 O(1)// 直接插入排序：将一个记录插入到已排序好的有...
#include <stdio.h> #include <stdlib.h>void array_sort(int *a, int len) {int i, j, tmp;for (i = 0; i < len - 1; i++){for (j = i + 1; j < len; j++){if (a[i] > a[j]){tmp = a[i];a[i] = a[j];a[j] = tmp;}}}for (i = 0; i < len; i++){printf("%d ", a[i]);}system("pause"); }void main() {int a[] = { 1, 2, 4, 0, 2, 6, 5, 9 }, len = sizeof(a) / sizeof(a[0]);;array_sort(a, len); }
排序和查找可以说是计算机领域最经典的问题了，而C++标准库在头文件 algorithm 中已经内置了基于快速排序的函数sort，只需调用这个函数，就可以轻易地完成排序。 下面简要介绍sort函数：sort ( first, last, comp )函数有三个参数：1. first：待排序序列的起始地址 2. last：待排序序列的结束地址（最后一个元素的起始地址） 3. comp：排序方式，可以不填写，不填写时默认为升序方式 当然sort函数支持多种数据类型，除了in...
1.表外排序 对链表的排序可分为表内排序和表外排序，表内排序将改变链表内原来的排列顺序，而表外排序不改变原链表中的排列顺序，并且排序效率也较高，我们可以借助指针数组(迭代器数组)的方法实现表外排序，代码如下所示： #include <list> #include <iostream> #include <random> #include <time.h> using namespace std; typedef int DATA; //定义全局链表 list<DATA> g_list; typedef list<DATA>::iterator POSITION; //数据输...
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。是 最慢的排序算法。在实际运用中它是效率最低的算法。 时间复杂度： 它是最差时间复杂度为：O(n^2)，冒泡排序最好的 时间复杂度 为：O (n^2) ，平均时间复杂度为 ：O(n^2) 算法原理： 1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 ...
Lua这类脚本语言在处理业务逻辑作为配置文件的时候方便省事 但是在大量需要 运算的地方就显得略微不足 按照 Lua内建排序算法 对比C/C++ PHP Java等的快速排序算法进行一下比较。 快速排序算法是基于冒泡排序,优化而来，时间复杂度T(n)=O(nLog2n) ,可见内部采用了二分策略 。 发现在LuaIDE LDT下直接运行效率要比 通过C++加载运行Lua脚本效率高的多 拿500W个数据排序 来说 ,脚本如下 同样的排序脚本Lua解释器的内置排序算...
c/c++中qsort（快速排序）和bsearch（二分查找算法）前两天自己写代码的时候，在程序中对于一些简单的排序和查找算法都得自己去写，个人觉得非常麻烦，然后我看官方的api手册偶然发现了在其他标准库函数中有封装好了的快速排序算法和二分查找算法，然后经过本人的一中午的时间的硬肝，终于把其用法给搞懂了，现在给大家分享一下：这是我从官方的api手册中截图过来的，两个函数的参数在官方文档中解释的很清楚，我就不再解释了。对i...
文章目录1有关qsort2，具体形式3、实例说明4、C++中sort用法以及和c中qsort的区别1有关qsort排序方法有很多种：选择排序，冒泡排序，归并排序，快速排序等。 看名字都知道快速排序是目前公认的一种比较好的排序算法。因为他速度很快，所以系统也在库里实现这个算法，便于我们的使用。 这就是qsort函数(全称quicksort)。它是ANSI C标准中提供的，其声明在stdlib.h文件中，是根据二分法写的，其时间复杂度为n*log(n)qsort函数声明如下...
基数排序 也是采用分桶的思想，但是加入了按位比较的思想（可以理解为每位进行一次计数排序） 思路：计算数列中最大位数 按位数循环处理每位的排序代码实现： #include<iterator> #include<iostream> #include<vector> using namespace std;int maxbit(int data[], int n) //辅助函数，求数据的最大位数 {int d = 1; //保存最大的位数int p = 10;for (int i = 0; i < n; ++i){while (data[i] >= p){p *= 10;++d;}}return d; } void...
桶排序 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定 思路：根据数据规模，初始化合理桶数 将数列中的数据按照桶的规模进行映射，尽量保证数据被均匀的分布到桶中 每个桶使用插入排序排好子序列 最后使用双指针思想使用插入排序合并每个桶，完成排序代码实现： #include<iostream> #include<vector> using namespace std; const int BUCKET_NUM = 10; struct ListNode {explicit Li...
堆排序 通过将无序表转化为堆，可以直接找到表中最大值或者最小值，然后将其提取出来，令剩余的记录再重建一个堆， 取出次大值或者次小值，如此反复执行就可以得到一个有序序列，此过程为堆排序。 思路： 1.创建一个堆 H[0……n-1]； 2.把堆首（最大值）和堆尾互换； 3.把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置； 4.重复步骤 2，直到堆的尺寸为 1。 代码实现： #include <iostream> #incl...
对sort函数(需要algorithm头文件)，它的cmp可以是“函数”，也可以是“对象”bool myfunction (int i,int j) { return (i<j); }struct myclass {bool operator() (int i,int j) { return (i<j);} } myobject; int main () {int myints[] = {32,71,12,45,26,80,53,33};vector<int> myvector (myints, myints+8);//放进容器vectorsort(myfunction); //参数cmp是个函数sort(myobject);//参数cmp是个结构体对象return 0; }▲注意：这...
1.问题 二分归并排序：对n个不同的数构成的数组A[1…n]进行排序，其中n=2^k 2.解析 把数组分为两部分，从中间隔开，把这两部分分别存入left，right数组中，对两个数组分别进行遍历，在遍历的同时比较两个数组中的值。这个步骤进行完后，数组中的元素不一定是按从小到大的顺序。只是其中一部分排好了序。这时候需要对数组进行递归，直到拆分的数组长度已经是1，就是只含有一个数。左右只含有一个元素，进行大小比较，依次再向上递归...
冒泡 题目描述 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。 输入格式 ...
快速排序 1、快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。 2、快速排序的三个步骤： (1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot） (2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素...