数组的排序几乎所有人都很熟悉了，常用的算法插入、冒泡、归并以及快排等都会或多或少依赖于数组可以在O(1)时间随机访问的特点。
当然不止。我觉得刷题是一件有意思的事，就像小猫小狗咬自己尾巴，玩弄的不亦乐乎。比喻可能不太恰当，是有种沉迷小游戏的感觉。可是在艰难打野的过程中，我们不要忘了，最重要的是：了解每种技能包的特点，适合解决的问题和场景。在特定实战场景下能够使用特定的技能包，自创技能包。这才是武功的至高境界。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
示例1 输入： {1,2,3,3,4,4,5} 返回值： {1,2,5} 示例2 输入： {1,1,1,8} 返回值： {8}
10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树； 10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态 规划、字符串匹配算法。
排序（sorting） 什么是排序 将一组杂乱无章的数据按一定规律顺次排列起来。 数据表 (datalist)：它是待排序数据对象的有限集合。 主关键字(key): 数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分对象, 作为排序依据，称为关键字。也称为排序码。 排序的目的是什么？ 便于查找！ 什么叫内部排序？什么叫外部排序？ 若待排序记录都在内存中，称为内部排序； 若待排序记录一部分在内存，一部分在外存，则称为外部排序。 外部排序时，要将数据分批调入内存来排序，中间结果还要及时放
从第一个元素开始，该链表可以被认为已经部分排序。 每次迭代时，从输入数据中移除一个元素，并原地将其插入到已排好序的链表中。
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
PHP数据结构（二十）——其他插入排序 （原创内容，转载请注明来源，谢谢） 注：本文是衔接直接插入排序的，因此直接插入排序的相关内容请点击——PHP数据结构（十八） ——直接插入排序。 一、概述 当数据量n较小时，直接插入排序是一个很好的方法。但是，当n较大时，采用直接插入排序，速度较慢，效果不好。其他插入排序主要是指折半插入排序、2-路插入排序、表插入排序，两者在直接插入排序的基础上，减少比较和移动的次数，以达到加快速度。 二、折半插入排序 直接插入排序中，当需要查找第i个值应该放于哪个位
转载自: http://blog.csdn.net/northplayboy/article/details/552388
[81] 以下两种初始化的方式有什么区别:“int a;” and “const int a;”？
#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR -1 typedef struct LNode { int data; struct LNode *next; }LNode, *LinkList; LinkList createlist(LinkList L, int n); //采用尾插法创建链表 LinkList createlist_tail(LinkList L, int
题目: 给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。
链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素;……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”(表示“空地址”)，链表到此结束。
本文记录了一些数据结构面试常见问题，本意用于考研复试，以下面试题为网上整理的问题以及自己加入的一些问题，答案仅供参考！
插入排序也是一种非常容易理解的算法，核心思想就是每次将新的元素往原本有序的数组中插入。
1、数据结构被形式地定义为(D，R)，其中D是数据的_ 有限集合___，R是关系的有限集合。
排序：就是将一组无序的记录序列按照某种逻辑顺序重新排序，调整为有序的记录序列的过程。简单的说，对于一组记录序列而言，就是根据记录的关键字递增顺序或者递减关系，将记录的次序进行重新排列，使得原来一组次序任意的记录序列转变为按其值有序排列的一组记录序列。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
1.数组和链表的区别，请详细解释。 从逻辑结构来看： a) 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。 b) 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素 从内存存储来看： a) (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小 b) 链表从堆中分配空间, 自由度大但是申请管理比较麻烦 从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了。
链表概述 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。 链表的各类操作
使用插入排序对链表进行排序。 Sort a linked list using insertion sort.
上节介绍了链表的基本操作史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
先说第一块，线性结构。这里涉及的主要知识点就是顺序表和链表，以及衍生出来的栈和队列。顺序表不必多说，就是内存中一块连续的区域，紧密排列了若干个相同类型的数据。显然，这种设计需要事先知道同样的元素一共有多少，不然就无法开辟出合适的内存区域（即会存在浪费或者不足）。为了解决数组这种元素数量不灵活的缺点而提出的方法就是链表。链表的基本单位是节点，每个节点拥有一个数据区和一个next指针，其中数据区用于存放数据，next指针指向下一个节点。与顺序表相比，链表可以根据需要自由选择节点的数量，从而解决了内存分配不合适的问题。
数组存储前提下，插入排序算法，在最坏情况下，前面的元素需要不断向后移，以便在插入点留出空位，让目标元素插入。 换成链表时，显然无需做这种大量移动，根据每个节点的前驱节点“指针”，向前找到插入点后，直接把目标值从原链表上摘下，然后在插入点把链表断成二截，然后跟目标点重新接起来即可。 <!doctype html> <html> <head> <title>双链表-插入排序</title> <meta http-equiv="Content-Type" content="text/html;
题意 用插入排序对链表排序 样例 给予 1->3->2->0->null, 返回 0->1->2->3->null 思路 将接受到的链表当做未排序链表，再创建一个链表存放已排序链表，并创建一个已排序链表的指针。 依次将未排序链表的元素与已排序链表中的每一个元素进行比较(也就是先用未排序链表的第一个与已排序链表的每一个进行比较，然后用未排序链表的第二个，第三个….依次进行比较，直到最后一个元素) 由于题意是升序排序，所以只要未排序链表中的元素大于已排序链表中的元素，那么就将未排序链表的这个元素放到第一个比它大
1. 顺序存储结构 ——把数据元素存放在地址连续的存储单元中，其数据间的逻辑关系和物理关系是一致的。
不同数据结构内部的存储与组织方式各异，其操作接口的使用方式及时空性能也不尽相同。引入列表结构的目的在于弥补向量结构在解决某些应用问题时，在功能及性能方面的不足。二者之间的差异，表面上体现于对外的操作方式，但根源则在于其内部存储方式的不同。
static int count = 0;//目前已经放了多少个数(相当于栈顶位置)
对于直接插入排序的内容请移步我之前的博客：简单排序 对于单链表的内容请移步我之前的博客：单链表
9月底收到创新工场offer，本早就该写一篇博客来总结在校招季遇到到的问题的，但近期比較懈怠直到如今才整理出这篇博客。
在计算机里，不保存在连续存储空间中，而每一个元素里都保存了到下一个元素的地址的数据结构，我们称之为链表（Linked List）。链表上的每一个元素又可以称它为节点（Node），而链表中第一个元素，称它为头节点（Head Node），最后一个元素称它为尾节点（Tail Node）。
题目：Sort a linked list using insertion sort. 即使用插入排序对链表进行排序。
题目汇总 以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。 目前范围：Leetcode前150题 单链表 Reverse Linked List/Reverse Linked List II 翻转链表（必考） Add Two Numbers 给定两个链表分别代表两个非负整数。数位以倒序存储，并且每一个节点包含一位数字。将两个数字相加并以链表形式返回。 Remove Nth Node From End of List 删除链表中倒数第n个节点 Merge Two Sorted
权当Go练习打的娱乐，Go有很多编程语言的影子，相对于C C++ Python Java而言，Go有C和C++的指针，有面向对象，输入像C，输出和Java、python差不多。
读者：我想用 strcmp() 作为比较函数, 调用 qsort() 对一个字符串数组
查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。通常查找和排序算法的考察是面试的开始，如果这些问题回答不好，估计面试官都没有继续面试下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握，有必要时要熟练写出代码。
本文是王争老师的《算法与数据结构之美》的学习笔记，详细内容请看王争的专栏 。有不懂的地方指出来，我做修改。
此文章是跟DataWhale开源组织刷leetcode算法题时所写，主要内容借鉴算法通关手册
PHP数据结构（二十六）——基数排序实现36进制数排序 （原创内容，转载请注明来源，谢谢） 一、概述 插入排序、选择排序、快速排序等，都是通过关键字之间的比较和移动进行的。基数排序完全不同，其是借助多个关键字排序的思想对单逻辑关键字进行排序的方法。 所谓多关键字，可以理解为带权值的关键字。例如： 现有序列{a0,a1,a2,a3,b0,b1,b2,b3}，假设a<b，数字按数字正常的大小。现要求对这个序列进行排序，但是要求数字的优先级更高，即a0<b0<a1<b1。则这种排序可以认为是多关键字的排序
排序的概念 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。 内部排序：数据元素全部放在内存中的排序。 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。 常见排
今天我们介绍两个复杂点的排序算法随机快排和希尔排序，这也是面试的重点，考察范围包括代码书写，复杂度分析以及稳定性比较！好吧，让我们开始今天的算法之旅吧！
最近想回过头来看看以前写的一些代码，可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录，后面也没再遇到相同的问题，忘的都差不多了。只能勉强整理了下面写的一些代码，这些代码有的有参考别人的代码，但都是自己曾经一点点敲的，挂出来，虽然很基础，但希望能对别人有帮助。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
