重庆自助建站网站/全国最新实时大数据

直接插入排序（Straight Insertion Sort）

是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。
排序过程如下:(参考自严蔚敏的数据结构(c语言版))

思想是第一次将第一个元素当作有序组,每次后面的元素插入到有序组中使其任然有序,不断的扩大有序组,当所有元素都插入完成后,那么整体数组就是有序的

直接插入排序的方法

void InsertSort_(DATA_TYPE* ar, int left, int right)
{for (int i = left; i <= right; ++i){for (int j = i - 1; j >= 0 && ar[j] > ar[j + 1]; --j) {Swap(ar+j, ar+j+1);}}
}

以上代码是插入排序的核心代码
DATA_TYPE是int

#define DATA_TYPE int 

功能是对数组ar,下标位置[lefe, right]中的元素运用直接排序的思想进行排序

直接插入排序的头文件,以下是对顺序表的直接插入排序方法及验证代码

//插入排序
void InsertSort_(DATA_TYPE* ar, int left, int right);
void InsertSort(Seqlist* sq)
{InsertSort_(sq->data, 0, sq->sz - 1);
}void InsertSort_(DATA_TYPE* ar, int left, int right)
{for (int i = left; i <= right; ++i){for (int j = i - 1; j >= 0 && ar[j] > ar[j + 1]; --j) {Swap(ar+j, ar+j+1);}}
}

数据结构顺序表的头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<memory.h>
#include<stdbool.h>
#include<time.h>#define DATA_TYPE int 
#define default_capacity 9typedef struct Seqlist
{DATA_TYPE* data;int capacity;int sz;
}Seqlist;//创建并初始化顺序表(对数器)
void CreatSequenceListWithLogaritmMachine(Seqlist* sq, int length) {srand((unsigned int)time(NULL));int numOfElements = rand() % length + 1;  //[0, length]sq->capacity = numOfElements > default_capacity ? numOfElements : default_capacity;DATA_TYPE* tmp = (DATA_TYPE*)malloc(sizeof(DATA_TYPE) * sq->capacity);assert(tmp != NULL);sq->data = tmp;sq->sz = 0;for (int i = 0; i < numOfElements; ++i) {sq->data[i] = (int)rand();++sq->sz;}
}//判断两个顺序表内容相同的方法
bool isEqual_(int* ar1, int sz1, int* ar2, int sz2);
bool isEqual(Seqlist* sq1, Seqlist* sq2)
{return isEqual_(sq1->data, sq1->sz, sq2->data, sq2->sz);
}bool isEqual_(int* ar1, int sz1, int* ar2, int sz2)
{if (ar1 == NULL && ar2 == NULL)return true;if ((ar1 != NULL && ar2 == NULL) || (ar1 == NULL && ar2 != NULL) || (sz1 != sz2))return false;for (int i = 0; i < sz1; ++i){if (ar1[i] != ar2[i])return false;}return true;}//顺序表拷贝的方法
void SeqlistCopy_(DATA_TYPE* ar1, int sz1, DATA_TYPE* ar2);
void SeqlistCopy(Seqlist* sq1, Seqlist* sq2)
{SeqlistCopy_(sq1->data, sq1->capacity, &(sq2->data));sq2->capacity = sq1->capacity;sq2->sz = sq1->sz;
}
void SeqlistCopy_(DATA_TYPE* ar1, int sz1, DATA_TYPE** ar2)
{DATA_TYPE* tmp = (DATA_TYPE*)malloc(sizeof(DATA_TYPE) * sz1);assert(tmp != NULL);*ar2 = tmp;for (int i = 0; i < sz1; ++i){(*ar2)[i] = ar1[i];}
}void Swap(DATA_TYPE* a, DATA_TYPE* b)
{DATA_TYPE tmp = *a;*a = *b;*b = tmp;
}int compare(const void* a, const void* b)
{return (*((DATA_TYPE*)a) > * ((DATA_TYPE*)b));
}//绝对正确的排序方法
void rightMethod_(DATA_TYPE* ar, int left, int right);
void rightMethod(Seqlist* sq)
{rightMethod_(sq->data, 0, sq->sz - 1);
}void rightMethod_(DATA_TYPE* ar, int left, int right)
{qsort((void*)ar, right - left + 1, sizeof(DATA_TYPE), compare);
}void _ShowSeqlist(DATA_TYPE* arr, int length);
void ShowSeqlist(const Seqlist* sq)
{_ShowSeqlist(sq->data, sq->sz);
}
void _ShowSeqlist(DATA_TYPE* arr, int length)
{for (int i = 0; i < length; ++i)printf("%d ", arr[i]);printf("\n");
}

主函数验证直接插入排序正确

#include "seqList.h"
#include "InsertSort.h"int main() {int testTime = 999999;  //测试次数int length = 10;  //对数器生成的数组长度范围[0, length]Seqlist sq1;Seqlist sq2;Seqlist sq3;bool succeed = true;for (int i = 0; i < testTime; ++i) {CreatSequenceListWithLogaritmMachine(&sq1, length);SeqlistCopy(&sq1, &sq2);  //从sq1 -拷贝到-> sq2SeqlistCopy(&sq1, &sq3);  //从sq1 -拷贝到-> sq2InsertSort(&sq2);  //验证直接插入排序方法rightMethod(&sq3);  //绝对正确的方法,调用库:qsort函数if (!isEqual(&sq2, &sq3)){succeed = false;break;}}if (!succeed) {printf("原数据:");ShowSeqlist(&sq1);printf("自己的方法:");ShowSeqlist(&sq2);printf("绝对正确的方法:库函数qsort:");ShowSeqlist(&sq3);printf("Failed, Fucking fucked!");printf("如果是绝对正确的方法qsort函数偶然出错,并且自己的方法正确,那么便证明自己的方法正确");}else {printf("succeed");}return 0;
}