算法之插入排序
-
一：基本概念
插入排序(Insert Sort)，每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
二：图文说明
插入排序示意图.png
我们分析一下排序具体过程：
1. 我们先假设数组下标为0的数据是排好序的，即38是排好序的；{38}
2. 取出数组下标为1的数据10，因为10<38,所以将10放在38前面；{10,38}
3. 取出数组下标为2的数据97，因为97>38,所以不进行排序，直接插入；{10,38,97}
4. 取出数组下标为3的数据76，因为98>76>38,所以将76放在38后面97前面；{10,38,76,97}
5. 取出数组下标为4的数据13，因为38>13>10,所以将13放在10后面38前面；{10,13,38,76,97}
即得排序完之后的升序结果！
-
三：代码实现
- C语言实现
#include <stdio.h> /* 插入排序 */ void show(int arr[],int len); void insertSort(int arr[],int len); void swap(int arr[],int i,int j); int main(void) { int arr[] = {38,10,97,76,13}; int len = sizeof(arr)/sizeof(*arr); printf("待排序数组为:\n"); show(arr,len); insertSort(arr,len); printf("排序之后的数组为:\n"); show(arr,len); return 0; } void show(int arr[],int len) { int i; for(i=0;i<len;i++) { printf("%d ",arr[i]); } printf("\n"); } void insertSort(int arr[],int len) { int i=0; int j=0; int temp = -1; int k = -1; for(i=1;i<len;i++) { k=i; temp = arr[k]; for(j=i-1; (j>=0) && (arr[j]>temp); j--) { arr[j+1] = arr[j]; k = j; } arr[k] = temp; } } void swap(int arr[],int i,int j) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }2.JAVA实现
package com.data; import java.util.Arrays; /** * @author mxf * 插入排序 */ public class InsertSort { public static void main(String[] args) { int a[] = {38,10,97,76,13 }; System.out.println("排序前的数组为:"+Arrays.toString(a)); insertSort(a); System.out.println("排序后的数组为:"+Arrays.toString(a)); } public static void insertSort(int[] arr){ int i,j; int n = arr.length; int target; //待插入的元素 for(i = 1;i < n;i++){//默认第一个元素有序，直接从第二个元素开始进行插入 j = i; target = arr[i]; while(j>0 && target<arr[j-1]){//如果要插入的数据小于第j-1个元素则将第j-1个元素后移,找比target大的数字 arr[j] = arr[j-1]; j--;//将target元素依次和前面的所有数进行比较 } arr[j] = target; } } } -
四：插入排序的时间复杂度和稳定性
- 插入排序的时间复杂度
- 插入排序是通过将当前第i个待排元素i与数组中前i-1个已经有序的元素j 进行两两比较，如果元素 i 小于 j，便交换。直到遇到比i小的元素或者到达数组头。由于每一个元素的插入都会最多比较i - 1次，因此最坏的时间复杂度为 1 + 2 + 3 + ... + n - 1 = n * (n - 1) / 2 ， 因此时间复杂度也为O(n*n)。
- 插入排序稳定性
- 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，也就是第一个元素（默认它有序）。比较是从有序序列的末尾开始，也就是把待插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面。否则一直往前找直到找到它该插入的位置。如果遇见一个与插入元素相等的，那么把待插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序仍是排好序后的顺序，所以插入排序是稳定的。
