网站开发关联下拉列表,外贸人才网招聘,十大网络舆情案例,量子秘密网站怎么做文章目录 排序排序方法的分类插入排序直接插入排序折半插入排序希尔插入排序 排序
将一组杂乱无章的数据按照一定规律排列起来。将无序序列排成一个有序序列。
排序方法的分类
储存介质#xff1a;
内部排序#xff1a;数据量不大#xff0c;数据在内存#xff0c;无需… 文章目录 排序排序方法的分类插入排序直接插入排序折半插入排序希尔插入排序 排序
将一组杂乱无章的数据按照一定规律排列起来。将无序序列排成一个有序序列。
排序方法的分类
储存介质
内部排序数据量不大数据在内存无需内外存交换数据。外部排序数据量较大数据在外存文件排序。
比较器个数
串行排序单处理机同一时刻比较一对元素。并行排序多处理机同一时刻比较多对元素。
主要操作
比较排序用比较的方法。 插入排序交换排序选择排序归并排序基数排序不比较元素的大小仅仅根据元素本身的取值确定其有序位置。
辅助空间
原地排序辅助空间用量为O1的排序方法。非原地排序辅助空间用量超过O1的排序方法。
稳定
稳定排序非稳定排序
插入排序
直接插入排序
前提是数组中的元素是有序的。
#includestdio.hvoid PrintArr(int arr[],int l);
void InsertSort(int arr[], int l);//#define MAXSIZE 20 //设记录的值不超过20个
//#define KeyType int//设关键字为整型量
//#define InfoType int //定义InfoType的其他数据项
//
//
//typedef struct {
// KeyType key;//定义每个记录(数据元素)的结构
// InfoType otherinfo;//其他数据项
//}RedType;
//
//typedef struct SqList {
// RedType r[MAXSIZE 1];//存储顺序表的结构
// //r[0]一般做哨兵或者缓冲区
// int length;//顺序表的长度
//}SqList;
//
//void InsertSort(SqList S) {
// int i, j;
// for (i 2; i S.length; i) {
// if (arr[i] arr[i - 1] ) {
// arr[i] arr[0] ;
//
// for (j i - 1; arr[j] arr[0] ; j--) {
// arr[j 1] arr[j];//j的值都要依次向后移进行插入
// }
// arr[j1] arr[0] ;//这里直接将哨兵的值赋值给当前查出来正确的位置
// }
// }
//}void InsertSort(int arr[], int l) {int i 0, j;int temp;printf(请输入要插入的数);scanf_s(%d, temp);arr[i] temp;for (i 2; i l; i) {if (arr[i] arr[i - 1]) {arr[i] arr[0] ;for (j i - 1; arr[j] arr[0] ; j--) {arr[j 1] arr[j];//j的值都要依次向后移进行插入}arr[j1] arr[0] ;//这里直接将哨兵的值赋值给当前查出来正确的位置}}PrintArr(arr, l);
}void PrintArr(int arr[],int l) {int i;for (i 1; i l; i) {printf(%d , arr[i]);}
}int main() {int arr[10] { 1,2,3,4,5,6,7,14, 12};InsertSort(arr,10);return 0;
}折半插入排序
查找插入位置时采用折半查找法。
void BInsert(SqList S) {int i, j,low,high,mid;for (int i 2; i S.length; i) {if (S.r[i].key S.r[i - 1].key) {S.r[i] S.r[0];low 1, high i - 1;while (low high) {mid (low high) / 2;if (S.r[0].key S.r[mid].key) {high mid - 1;}else {high mid 1;}}for (j i - 1; j high 1; j--) {S.r[j - 1] S.r[j];S.r[high 1] S.r[0];}}}
}希尔插入排序
