github博客传送门 博客园传送门 插入排序原理:#include<iostream> using namespace std;//插入排序 void InsertionSort(int a[], int size) {int i; //有序区间的最后一个元素的位置,i+1就是无序区间最左边元素的位置for(i = 0; i < size-1; ++i){int tmp = a[i + 1]; //tmp是待插入到有序区间的元素,即无序区间最左边的元素int j = i;while(j >= 0 && tmp < a[j]){ //寻找插入的位置 a[j + 1] = a[j]; //比tmp大的元素都往...
（1）算法描述 对于给定的一个线性空间，遍历考察每一个元素，将当前元素拷贝一份，并将前一个元素拷贝到当前元素的原位置。拷贝出来的元素与前一个元素进行比较，如果满足前一个元素大于或小于当前元素就将当前拷贝出来的元素放到当前位置，否则继续向前比较。 （2）图解算法（3）C/C++代码实现Custom.hvoid insertionAdvancedSort(int arr[], int number);Custom.cpp void insertionAdvancedSort(int arr[], int number) { // 一...
（1）算法描述 对于给定的线性空间，依次考察每个元素，当指定的元素比后一个元素大（或者小）的时候就交换位置，然后交换过来的后一个元素继续向前比较，只要比该元素大（或者小）就两两交换，直到不符合交换条件或者到达最前端。 （2）算法图解（3）C/C++代码实现CustomSort.hvoid insertionSort(int arr[], int number);CustomSort.cppvoid insertionSort(int arr[], int number) {// 一次考察每个元素for (int i = 1; i < numb...
直接插入排序 （Straight Insertion sort） 基本思想：把数组中待排序的n个元素看成一个有序表和无序表，开始时有序表只有一个元素，而元素表中包含有n-1个元素。排序过程中，每次取出无序表中第一个元素，将它插入到有序表的适当位置上，使之成为一个新的有序表，这样经过n-1次的插入后，无序表变成为空表，而有序表包含有n个元素，至此排序完毕。 存在的问题：如何将一个记录数插入到当前的有序区，并使插入后该区间的记录按关键...
排序分为内部排序和外部排序。 内部排序：是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 外部排序：指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。当N小于20的时候，插入排序具有最好的性能。 当N大于20时，快速排序具有最好的性能，尽管归并(merge sort)和堆排序(heap sort)复杂度都为nl...
插入排序原本的实现方式之一： public int[] sort_ori(int[] ins) {for (int i = 1; i < ins.length; i++) {int currentIndex = i;int currentValue = ins[i];int switchIndex = -1;for (int j = 0; j < currentIndex; j++) {if (ins[j] > currentValue) {switchIndex = j;break;}}System.out.println(switchIndex);if (switchIndex >= 0) {if (currentIndex - switchIndex >= 0)System.arraycopy(ins, switchIndex, ins, switchIn...
题干：n个数字从小到大排列。 算法思路： 将数组分成array[0]~array[i-1]和array[i]~array[array.length-1]两部分。 前面排好序，后面乱序，取array[i]和排好序的部分从后向前依次比较，找到合适位置插入，直到排序完成。 ? 基本实现： 思路：用两层循环实现，外层循环控制整体遍历的次数，内层循环控制当次遍历。var array = [65,97,76,13,27,49,58]; var preIndex,tmp; for(var i=1;i<array.length;i++){preIndex = i-1;tmp = a...
#!/usr/bin/env python # -*- coding: utf-8 -*- # 插入排序 # 时间复杂度 O(n) import timedef logger(func):start_time = time.time()def inner(*args, **kwargs): # 1return func(*args, **kwargs) # 2print(time.time() - start_time)return inner@logger def insertion_sort(array):length = len(array)for i in range(1, length):for m in range(i):if array[i] < array[m]:array[i], array[m] = array[m], array[i]if __n...
前言：感觉好久没写博客了，十月份的计划是：要开始深入攻克数据结构和算法，耽误好久了，这都月末了，抓紧时间又学习了一波，赶紧来分享了一下，使用的语言是C++，最开始学数据结构一定要用C，掌握扎实之后，想学算法，用C++比较好，C封装没有那么好，写起来没有那么容易了。一、准备工作这部分会封装一些接口，如生成数组、测试排序算法执行时间等，便于比较和调试。封装在.h中，如下：#ifndef SORTTESTHELPER_H_ #define SORTTE...
1.冒泡排序： 方法一：public static int[] MaoPao(int[] arr){//执行多少次for (int i = 0; i < arr.Length; i++){//每执行1次，把最大的放在最后for (int j = 0; j < arr.Length - 1; j++){int a = arr[j];int b = arr[j + 1];if (a>b){arr[j+1] = a;arr[j] = b;}}}return arr;} 冒泡排序2 public static int[] MaoPao2(int[] arr){for (int i = arr.Length-1; i >=1; i--){for (int j = 0; j<= j-1; j++){int a = arr[j];int...
伪代码：INSERTION-SORT for j <- 2 to length[A]key <- A[j]Insert A[j]into the sorted sequence A[l...j-1]. i <- j - 1while i > 0 and A[i] > keyA[i + 1] <- A[i]i <- i - 1A[i + 1] <- key C/C++代码：#include <stdio.h> #include <string.h>int main() {int n;int A[1000];int k = 0;while (scanf("%d", &n) != EOF) {A[k] = n;k++;}printf("input complete\n");for (int j = 1; j < k; j++) {int key = A[j];int i = ...
一、直接插入排序介绍 直接插入排序(Straight Insertion Sort)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。 二、直接插入排序的时间复杂度和稳定性 直接插入排序时间复杂度直接插入排序的时间复杂度是O(N2)。假设被排序的数列中有...
直接插入排序 最简单的排序方法。它的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录增1的有序表。把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。 ——————————那一季的银杏叶：https://www.cnblogs.com/snowcan/p/6244128.ht...
package algorithm;public class InsertSort {public static void main(String[] args) {int[] a = {6,2,5,4,7,1,3,9,8};insertSort(a, a.length);for (int i = 0; i < a.length; i++) {System.out.println(a[i]);} }/*** * @param a* @param n 表示第n个位置*/private static void insert(int[] a, int n){int key = a[n];int i = n;while(a[i-1] > key){a[i] = a[i-1];i--;if(i == 0){break;}}a[i] = key;}/*** * @param a* @p...
前言 最近买了一本算法导论的书籍，同学念研究生就是用的这本书，其实这些算法数据结构直接就该弄完的，都工作四年了，只是知道一点说来惭愧，不懂算法的程序员不是好的程序员。算法导论刚开，从前往后看的，第一章的插入法看书的图还是看的不明白容易产生误导，于是自己写了代码才更加的理解了。 正文 一是看书的文字描述比较枯燥，二是看书上的图感觉不对劲儿，也是自己理解有限。 这是书中的原图： ...