前言 最近买了一本算法导论的书籍，同学念研究生就是用的这本书，其实这些算法数据结构直接就该弄完的，都工作四年了，只是知道一点说来惭愧，不懂算法的程序员不是好的程序员。算法导论刚开，从前往后看的，第一章的插入法看书的图还是看的不明白容易产生误导，于是自己写了代码才更加的理解了。 正文 一是看书的文字描述比较枯燥，二是看书上的图感觉不对劲儿，也是自己理解有限。 这是书中的原图： ...
插入排序类似纸牌玩家整理手中的纸牌：每次取一张纸牌，并在取下一张之前，将它放在适当的位置，使手中的所有纸牌按顺序排列。 时间复杂度：O(N2) 空间复杂度：O(1) 稳定性：稳定// 插入排序 void insertion_sort(int list[], int listSize) {int i, j;int next;for (i = 1; i < listSize; ++i) {next = list[i];for (j = i - 1; j >= 0 && next < list[j]; --j) {list[j + 1] = list[j];}list[j + 1] = next;} }
排序 (参考大话数据结构第9章，归并排序没有看，快速排序的优化部分没有看) 相关概念： 1.内排序与外排序：根据在排序过程中待排序的记录是否全部被放置在内存中分为内排序和外排序。本文讨论的7种排序算法都是内排序。 2.稳定性：能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。即：如，如果Ai==Aj，Ai原来在Aj位置前，排序后Ai仍然是在Aj位置前 冒泡排序： bubbleSort0:最基础版冒泡排序...
#include <iostream>using namespace std;void Display(int *a, int n) {for (int i = 0; i < n; ++i){cout << a[i] << " ";}cout << endl; }void Swap(int *x, int *y) {int tmp = *x;*x = *y;*y = tmp; }void BubbleSort1(int *a, int n) {// Judge.if (n < 2){return;}int tmp = 0;for (int i = n - 1; i > 0; --i){bool isSwap = false;for (int j = 0; j < n - 1; ++j){if (a[j] > a[j + 1]){tmp = a[j];a[j] = a[j + 1];a[j ...
#include <iostream> #include <cstdio> using namespace std;const int N = 1e5+10;int n,num[N];void insert_sort(){int t,j;for(int i=2;i<=n;i++){t=num[i];j=i-1;while(j>=1 && num[j]>t){num[j+1]=num[j];j--;}num[j+1]=t;} }int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&num[i]);insert_sort();for(int i=1;i<n;i++)printf("%d ",num[i]);printf("%d",num[n]);return 0; }
1.普通冒泡排序 for(let i=0;i<arr.length-1;i++){????????????for(let?j=0;j<arr.length-1-i;j++){ ????????????????if(arr[j]>arr[j+1]){ ????????????????????let?t?=?arr[j] ????????????????????arr[j]?=?arr[j+1] ????????????????????arr[j+1]?=?t ????????????????} ????????????} ?} ? 2.选择排序 ?for(let?i=0;i<arr.length;i++){ ????????????let?index?=?i ????????????for(let?j=index+1;j<arr.length;j++){ ????????...
六大排序思路整理+代码 1、冒泡排序2、选择排序3、插入排序原理代码实现1、冒泡排序 2、选择排序 3、插入排序 原理 把4插入到有序数列[ 1、3、5 ]中还要使其有序。 从左往右的话，只需要找到第一个大于4的数，把4放在它的前面。 从右往左的话，只需要找到第一个小于4的数，把4放在它的后面。 初始有一组8个数字的无序数列： 插入排序就是利用这种思想，把数一个个插入使整个数列有序。第一轮插入： 第一个数47只有一个数所以是有...
插入排序 直接插入排序 插入排序（Insertion-Sort） 的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 public static void sort(int[] arr){if (arr.length == 0) retu...
前言 东方健康网 https://www.9559.org/cn/ 上一篇在聊时间复杂度和空间复杂度时，没有按指定格式显示(明明预览的时候没问题的)，强迫症的我稍微优化了一下重新发布，目的就是让小伙伴看着舒服。 上次聊到的直接插入排序在比较有序数据和待插入数据时，是通过依次遍历的方式进行比较，当数据量比较大时，得考虑进一步优化；折半插入排序就是通过减少有序数据与待插入数据的比较次数，从而提升效率。 正文 1. 先来熟悉一下折半查找...
插入排序 void insertion_sort(int arr[], int len){int i,j,key;for (i=1;i<len;i++){key = arr[i];j=i-1;while((j>=0) && (arr[j]>key)) {arr[j+1] = arr[j];j--;}arr[j+1] = key;} }
插入选择1.插入排序425163选定4, [0,0]这个区间是已处理的有序区间 现在遍历[1,5]这个区间，逐渐插入已处理的有序区间把2拿出来 与[4]比较，发现<4 ,把4挪到它后面的位置处考察之前的4所在的位置0位是不是应该插入的地,2与这个预插入位置之前的元素比较,发现已经到头所以0位是2正确插入的位置 插入后245163然后考察5 把5挖出来,看下5是否能放在2这个位置，需要和2位置前面的元素比较 发现5>前面的元素4，所以5 放进2这个位置245...
#include <iostream>void print_arrs(const int *, int N);void sort_arrs(int *pInt, int N);int main() {int arr[] = {1, 3, 5, 7, 6, 2, 4, 9, 8, 0};std::cout << "排序前:" << std::endl;print_arrs(arr, 10);sort_arrs(arr, 10);std::cout << "排序后:" << std::endl;print_arrs(arr, 10);return 0; }/*** 插入排序* @param pInt* @param N*/ void sort_arrs(int *const pInt, int N) {for (int i = 1; i < N; ++i) {int tem...
思路： 1.如果链表为空，则返回其本身； 2.如果链表不为空，初始化排序表最后指针lastsorted为head，当前需排序的指针curr为head->next； 3.为了方便将元素插入到head之前，设立Head_front指针，值设为0，指向head； 4.初始化完成后，对排好序的表利用指针prev进行遍历查找，找到适合插入的位置；ListNode *prev = Head_front;while (prev->next->val <= curr->val)prev = prev->next;5.将需排序元素curr原地删除，插入新的位置中；...
直接插入排序的核心思想：将待插入数插入已经有序数列中，插入后，新的数列仍然保持有序。 假设一个数组里有n个数，那么直接插入排序则需要n-1趟排序：第一趟排序将第一个数视为有序数列，将第二个数插入到有序数列中，插入后得到的新数列仍依然有序；第二趟排序前两个数组成的数列视为有序数列，将第三个数插入到有序数列中，插入后得到的新数列仍依然有序，以此类推，第n-1趟排序中，前n-1个数为有序数列，将第n个数插入到有序数...
2021-03-17：手写代码：单链表插入排序。 福大大 答案2021-03-17： 从链表的第二个节点开始遍历。当前节点的左边所有节点一定是有序的。先比较当前节点和左邻节点，如果左邻节点小于等于当前节点，直接下个节点；如果左邻节点大于当前节点，从链表的有序部分的第一个节点开始遍历，找到当前节点小于有序部分的某个节点，然后插入进去。 代码用golang编写，代码如下： package mainimport "fmt"func main() {//head := &ListNode{Va...