6-1 插入排序
分数 25
全屏浏览题目
切换布局
作者 李廷元
单位 中国民用航空飞行学院
编程实现插入排序函数。void insertionSort(int arr[], int n);。其中arr存放待排序的数据，n为数组长度（1≤n≤1000）。
函数接口定义如下：
/* 对长度为n的数组arr执行插入排序 */ void insertionSort(int arr[], int n);
请实现insertionSort函数，使排序后的数据从小到大排列。
裁判测试程序样例：
#include <stdio.h> #define N 1000 int arr[N]; /* 对长度为n的数组arr执行插入排序 */ void insertionSort(int arr[], int n); /* 打印长度为n的数组arr */ void printArray(int arr[], int n); int main() { int n, i; scanf("%d", &n); for (i = 0; i < n; ++i) { scanf("%d", &arr[i]); } insertionSort(arr, n); printArray(arr, n); return 0; } /* 打印长度为n的数组arr */ void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) /* 下标0..n-2每个元素后面有个空格 */ printf(" ");/*下标n-1,也就是最后一个元素后面没有空格*/ } printf("\n");/* 一行打印完后换行 */ } /* 你的代码将嵌在这里 */
输入样例：
1. 10 2. 1 19 9 11 4 3 5 8 10 6
输出样例：
1 3 4 5 6 8 9 10 11 19
1. void insertionSort(int arr[], int n) 2. { 3. for(int i=1;i<n;i++) 4. { 5. int min=arr[i]; 6. int j=i-1; 7. for(j=i-1;j>=0;j--) 8. { 9. if(min<arr[j]) 10. { 11. arr[j+1]=arr[j]; 12. } 13. else 14. { 15. break; 16. } 17. } 18. arr[j+1]=min; 19. } 20. }
6-2 直接插入排序
分数 20
全屏浏览题目
切换布局
作者 DS课程组
单位 临沂大学
本题要求实现直接插入排序函数，待排序列的长度1<=n<=1000。
函数接口定义：
void InsertSort(SqList L);
其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：
typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList;
裁判测试程序样例：
#include<stdio.h> #include<stdlib.h> typedef int KeyType; typedef struct { KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/ int Length; }SqList; void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ void InsertSort(SqList L); int main() { SqList L; int i; CreatSqList(&L); InsertSort(L); for(i=1;i<=L.Length;i++) { printf("%d ",L.elem[i]); } return 0; } /*你的代码将被嵌在这里 */
输入样例：
第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：
1. 10 2. 5 2 4 1 8 9 10 12 3 6
输出样例：
输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。
1 2 3 4 5 6 8 9 10 12
1. void InsertSort(SqList L) 2. { 3. for(int i=1;i<=L.Length;i++) 4. { 5. int min=L.elem[i]; 6. int j=i-1; 7. for(j=i-1;j>=1;j--) 8. { 9. if(min<L.elem[j]) 10. { 11. L.elem[j+1]=L.elem[j]; 12. } 13. else 14. { 15. break; 16. } 17. } 18. L.elem[j+1]=min; 19. } 20. }
7-1 插入排序
分数 30
全屏浏览题目
切换布局
作者 魏峻
单位 陕西理工大学
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
输入格式:
输入在第1行中给出N（1<N≤100），在第2行中给出N个待排序的整数，数字间以空格分隔，并保证数字没有重复的出现。
输出格式:
给出插入排序每一遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。
输入样例:
1. 7 2. 4 5 7 6 3 2 1
输出样例:
1. 4 5 7 6 3 2 1 2. 4 5 7 6 3 2 1 3. 4 5 6 7 3 2 1 4. 3 4 5 6 7 2 1 5. 2 3 4 5 6 7 1 6. 1 2 3 4 5 6 7
1. #include<bits/stdc++.h> 2. using namespace std; 3. int main() 4. { 5. int n; 6. cin>>n; 7. int a[n]; 8. for(int i=0;i<n;i++) 9. { 10. cin>>a[i]; 11. } 12. for(int i=1;i<n;i++) 13. { 14. int min=a[i]; 15. int j=i-1; 16. for(j=i-1;j>=0;j--) 17. { 18. if(min<a[j]) 19. { 20. a[j+1]=a[j]; 21. } 22. else 23. { 24. break; 25. } 26. } 27. a[j+1]=min; 28. for(int k=0;k<n;k++) 29. { 30. cout<<a[k]; 31. if(k<n-1) 32. { 33. cout<<" "; 34. } 35. } 36. if(i<n-1) 37. { 38. cout<<endl; 39. } 40. } 41. return 0; 42. }
