直接插入排序Linux下C 达成
发布时间：2021-11-22 12:44:51 所属栏目：教程 来源：互联网
导读：直接插入排序把待排序序列分为两个序列：一个有序序列和一个无序序列。每次排序时，取无序序列的第一个元素，从有序序列尾部向前扫描，比较有序序列的元素，并把该元素插入到有序序列的合适位置，使有序序列继续保持有序并增长。下面给出关键代码： 1、插入
|
直接插入排序把待排序序列分为两个序列：一个有序序列和一个无序序列。每次排序时，取无序序列的第一个元素，从有序序列尾部向前扫描，比较有序序列的元素，并把该元素插入到有序序列的合适位置，使有序序列继续保持有序并增长。下面给出关键代码： 1、插入排序头文件：InsertSort.h #ifndef INSERTSORT_H #define INSERTSORT_H extern void InsertSort(int *pArr, int length); #endif 2、插入排序源文件：InsertSort.c #include "InsertSort.h" void InsertSort(int *pArr, int length) { int i,j,tmp; for(i=1; i<length; i++) { j=i-1; tmp=*(pArr+i); while(j>=0 && tmp < *(pArr+j)) { *(pArr+j+1)=*(pArr+j); j--; } if(j!=i-1) { *(pArr+j+1)=tmp; } } } 3、main头文件：main.h #ifndef MAIN_H #define MAIN_H #include "InsertSort.h" #include <stdio.h> void outputArr(const int *pArr, const int length); #endif 4、main 源文件：main.c #include "main.h" int main(void) { printf("input array length:n"); int length; scanf("%d", &length); if(length<=0) { printf("length must be larger 0n"); return 1; } int i; int arr[length]; for(i=0; i< length; i++) { printf("input arr[%d] value:n", i); scanf("%d", &arr[i]); } printf("arr orig:"); outputArr(arr, length); InsertSort(arr, length); printf("arr insert sort completed:"); outputArr(arr, length); } void outputArr(const int *pArr, const int length) { int i; for(i=0; i<length; i++) { printf(" %d", *(pArr+i)); } printf("n"); } 4、编译： [root@localhost insertSort]$ gcc -c InsertSort.c [root@localhost insertSort]$ gcc -c main.c [root@localhost insertSort]$ gcc -o main InsertSort.o main.o 如果运气不是非常坏，你将看到可执行文件main，执行main，大致如下： [root@localhost insertSort]$ ./main input array length: 5 input arr[0] value: 43 input arr[1] value: 65 input arr[2] value: 76 input arr[3] value: 1 input arr[4] value: 43 arr orig: 43 65 76 1 43 arr insert sort completed: 1 43 43 65 76 插入排序最佳效率o(n)，最糟效率O(n²)，适用于排序小列表。若列表基本有序，则插入排序比冒泡、选择排序更有效率。  （编辑：东莞站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
