一、C语言代码实现：
/******************************************************* * Description: 直接插入排序算法 * Author: shujuxiong * Version: 1.0 * Time: 2018-06-19 * Copyright: *******************************************************/ #include<stdio.h> //函数：打印数组 void PrintDataArray(int a[], int n) { for(int i=0; i<n; i++) printf("%d ",a[i]); printf("\n"); } //函数：交换数组元素 void swap(int *x, int *y) { int temp; temp = *x; *x = *y; *y = temp; } //直接插入排序，版本1 void InsertSort1(int a[], int n) { int i,j,k; for(i=1; i<n; i++) { //找到要插入的位置 for(j=0; j<i; j++) { //插入并后移剩余元素，后移元素的操作类似于冒泡排序 if(a[j] >= a[i]) { int temp=a[i]; for(k = i-1; k>=j; k--) a[k+1] = a[k]; a[j] = temp; } } } PrintDataArray(a, n); } //直接插入排序，版本2，搜索和后移同时进行 void InsertSort2(int a[], int n) { int i,j,k; for(i=1; i<n; i++) { if(a[i]<a[i-1]) { //插入并后移剩余元素 int temp = a[i]; for(j=i-1; j>=0 && a[j]>temp; j--) { a[j+1] = a[j]; } a[j+1] = temp; } } PrintDataArray(a, n); } //插入排序，版本3：用数据交换代替版本2的数据后移(比较对象只考虑两个元素)，像冒泡排序？ //算法4中使用该方法 void InsertSort3(int a[], int n) { for(int i=1; i<n; i++) for(int j=i-1; j>=0 && a[j+1]<a[j];j--) { swap(&a[j+1], &a[j]); /*或者 int tmp = a[j+1]; a[j+1] = a[j]; a[j] = tmp;*/ } PrintDataArray(a, n); } //测试用例 int main() { int a[] = {3,1,7,5,2,4,9,6}; int len = sizeof(a)/sizeof(a[0]); InsertSort1(a, len); InsertSort2(a, len); InsertSort3(a, len); return 0; }运行结果：
二、Java代码实现：
/** * @description: 直接插入排序算法 * @author： shujuxiong * version: 1.0 * @time: 2018-06-20 */ public class InsertSort { public static void sort(int[] a) { int N = a.length; for(int i = 1; i < N; i++) { for(int j = i-1; j >= 0 && a[j+1] < a[j]; j--) { exch(a, j+1, j); /*或者 int tmp = a[j+1]; a[j+1] = a[j]; a[j] = tmp; */ } } } //方法：交换数组元素 private static void exch(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } //方法：打印数组 private static void printDataArray(int[] a) { int N = a.length; for(int i = 0; i < N; i++) System.out.printf("%d ",a[i]); System.out.printf("\n"); } //测试用例 public static void main(String[] args) { int[] arr = {3,1,7,5,2,4,9,6}; sort(arr); printDataArray(arr); } }运行结果：
三、Python 代码实现：
# -*- coding: utf-8 -*- """ Description: 直接插入排序算法 Author: shujuxiong Version: 1.0 Date: 2018-06 -24 """ import copy ##直接插入排序，版本1，最简单方式 def insertSort1(relist): n = len(relist) for i in range(1, n): for j in range(i): # 首先碰到第一个比自己大的数字，赶紧刹车，停在那，所以选择insert if relist[j] > relist[i]: relist.insert(j, relist[i]) # 因为前面的insert操作，所以后面位数+1，这个位置的数已经insert到前面去了，所以pop弹出 relist.pop(i+1) break return relist ##直接插入排序，版本2，后移式插入 def insertSort2(relist): n = len(relist) for i in range(1,n): if relist[i] < relist[i-1]: tmp = relist[i] j = i-1 while j >= 0 and relist[j] > tmp: relist[j+1] = relist[j] j = j-1 relist[j+1] = tmp return relist ##直接插入排序，版本3，冒泡式插入 def insertSort3(relist): n = len(relist) for i in range(1, n): j = i-1 while j>=0 and relist[j+1]<relist[j]: tmp =relist[j+1] relist[j+1] = relist[j] relist[j] = tmp j-=1 """或者 for j in range(i-1,-1,-1): if relist[j+1] < relist[j]: tmp = relist[j+1] relist[j+1] = relist[j] relist[j] = tmp else: break """ return relist #测试用例 def main(): mylist = [3,1,7,5,2,4,9,6] print(insertSort1(copy.copy(mylist))) print(insertSort2(copy.copy(mylist))) print(insertSort3(copy.copy(mylist))) if __name__ == '__main__': main()
运行结果：
转载于:https://www.cnblogs.com/shujuxiong/p/9201748.html
