前言
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
原理
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
关键码
关键码是数据元素中某个数据项的值，用它可以标示一个数据元素。通常会用记录来标示数据元素，一个记录可以有若干数据项组成。例如，一个学生的信息就是一条记录，它包括学号，姓名，性别等若干数据项。主关键码可以唯一的标示一个记录的关键码，如学号。次关键码是可以标示若干记录的关键字，如性别、姓名。
假设一个文件有n条记录{}，对应的关键码是{}，排序家就是将此n个记录按照关键码的大小递增（或递减）的次序排列起来，使这些记录由无序变为有序的一种操作。排序后的序列若为{}时，其对应的关键码值满足{}或{}。
若在待排序的记录中，存在两个或两个以上的关键码值相等的记录，经排序后这些记录的相对次序仍然保持不变，则称相应的排序方法是稳定的方法，否则是不稳定的方法。
内部排序和外部排序
根据排序过程中涉及的存储器不同，可以将排序方法分为两大类：一类是内部排序，指的是待排序的几率存放在计算机随机存储器中进行的排序过程；另一类的外部排序，指的是排序中要对外存储器进行访问的排序过程。
内部排序是排序的基础，在内部排序中，根据排序过程中所依据的原则可以将它们分为5类：插入排序、交换排序、选择排序、归并排序和基数排序；根据排序过程的时间复杂度来分，可以分为三类：简单排序、先进排序、基数排序。
评价排序算法优劣的标准主要是两条：一是算法的运算量，这主要是通过记录的比较次数和移动次数来反应；另一个是执行算法所需要的附加存储单元的的多少。
直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
例如,已知待排序的一组记录是：
60,71,49,11,24,3,66
假设在排序过程中，前3个记录已按关键码值递增的次序重新排列，构成一个有序序列：
49,60,71
将待排序记录中的第4个记录（即11）插入上述有序序列，以得到一个新的含4个记录的有序序列。首先，应找到11的插入位置，再进行插入。可以将11放入数组的第一个单元r[0]中，这个单元称为监视哨，然后从71起从右到左查找，11小于71，将71右移一个位置，11小于60，又将60右移一个位置，11小于49，又再将49右移一个位置，这时再将11与r[0]的值比较，11≥r[0]，它的插入位置就是r[1]。假设11大于第一个值r[1]。它的插入位置应该在r[1]和r[2]之间，由于60已经右移了，留出来的位置正好留给11.后面的记录依照同样的方法逐个插入到该有序序列中。若记录数n,续进行n-1趟排序，才能完成。
直接插入排序的算法思路：
（1） 设置监视哨r[0]，将待插入记录的值赋值给r[0]；
（2） 设置开始查找的位置j；
（3） 在数组中进行搜索，搜索中将第j个记录后移，直至r[0].key≥r[j].key为止；
（4） 将r[0]插入r[j+1]的位置上。
思路：
1、第一层循环遍历从第二个元素，直到最后一个元素；
2、取出的第二个元素 与前面的元素比较（第一个元素），第一个元素大于第二个元素则右移，
3、取出的元素放到第一个元素的位置；
4、以此取出第三个元素，然后比较，以此类推
对应待排序数据，在排好的数据中，比待排序数据大则右移，直到有不大于待排数据时，待排数据放到右移的空位子，
直接插入排序算法：
public void zjinsert (Redtype r[],int n)
{
int I,j;
Redtype temp;
for (i=1;i<n;i++)
{
temp = r[i];
j=i-1;
while (j>-1 &&temp.key<r[j].key)
{
r[j+1]=r[j];
j--;
}
r[j+1]=temp;
}
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
//直接插入排序
void insertion_sort(int array[], int first, int last) {
int i, j;
int temp;
for (i = first + 1; i < last; i++) {
temp = array[i];
j = i - 1;
//与已经排序的数逐一比较，大于temp时，该数移后
while ((j >= 0) && (array[j] > temp)) {
array[j + 1] = array[j];
j--;
}
//存在大于temp的数
if(j != i - 1) {
array[j + 1] = temp;
}
}
}
//直接插入排序
void insert_sort(int *array, int n) {
int i, j;
int temp;
for (i = 1; i < n; i++) {
temp = *(array + i);
for (j = i; j > 0 && *(array +j - 1) > temp; j--) {
*(array + j) = *(array + j - 1);
}
*(array + j) = temp;
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
// int arr[] = {2,5,3,8,9,4,7,6};
int numlength = 100;
int arr[numlength];
for (int i = 0; i < numlength; i++) {
arr[i] = rand()%100;
}
// int randArr[] =
printf("排序前：");
for (int i = 0; i< sizeof(arr)/sizeof(arr[0]); i++) {
printf("%d ", arr[i]);
}
insertion_sort(arr, 0, numlength);
// insert_sort(arr, numlength);
printf("\n排序后：");
for (int i = 0; i< sizeof(arr)/sizeof(arr[0]); i++) {
printf("%d ", arr[i]);
}
return 0;
}
网友评论