网站建设的安全技术,一个好网站设计,icp备案通过了 怎么修改我的网站,网站对企业的作用void*类型的实现#xff1a;排序#xff08;void*类型#xff09;-CSDN博客
一、插入排序
1、直接插入排序
思想#xff1a;把待排序的数据逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为止#xff0c;得到一个新的有序序列 。
单趟#x… void*类型的实现排序void*类型-CSDN博客
一、插入排序
1、直接插入排序
思想把待排序的数据逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
单趟 整体 实现
void InsertSort(int* arr, int sz) {assert(arr);int i 0;for (i 0; i sz - 1; i) {// 单趟int end i; // 有序序列的最后一个值int tmp arr[end 1];// 把end后面的第一个数据 往 0~end这个有序区间中插入while (end 0) {if (tmp arr[end]) {arr[end 1] arr[end];end--;} else {break;}}arr[end 1] tmp;}
} 2、希尔排序
希尔排序本质上是对直接插入排序的优化。 代码实现
void ShellSort(int* arr, int n) {// 1.gap1相当于预排序,让数组接近有序// 2.gap1相当于直接排序,保证有序int gap n;int i 0;while (gap 1) {gap gap / 3 1; // 1保证了最后一次gap一定是1// gap1 最后一次就相当于直接插入排序// gap / 2:效果没有/3好for (i 0; i n - gap; i) {int end i;int tmp arr[end gap];while (end 0) {if (tmp arr[end]) {arr[end gap] arr[end];end - gap;} else {break;}arr[end gap] tmp;}}}
}
对希尔排序多组并排的一个理解 希尔排序的时间复杂度在O(N^1.3~N^2)之间。当且仅当待排数据有序的情况下希尔排序的时间复杂度劣于直接插入排序。
二、选择排序 1、直接选择排序
思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。每次选一个数放到放到新的位置。
直接选择排序是很基础的一个排序实现
// 选择排序
// 优化一次选两个数最大和最小放在合适位置
void SelectSort(int* arr, int n) {assert(arr);int begin 0;int end n - 1;while (begin end) {// 在begin和end之间找出最大的数和最小的数的下标int maxi begin;int mini begin;int i 0;for (i begin 1; i end; i) {if (arr[maxi] arr[i]) {maxi i;}if (arr[mini] arr[i]) {mini i;}}Swap(arr[begin], arr[mini]);// 如果maxi和begin重叠则maxi的值需要修正。if (begin maxi) {maxi mini;}Swap(arr[end], arr[maxi]);begin;end--;}
}
时间复杂度
T(N)N*(N/2)1/2*N^2优化后是N*N/2优化前是N*N。即O(N^2) 。
2、堆排序
思路堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建小堆排降序建大堆。
直接实现在堆中有过讲解
// 向下调整算法
void AdjustDown(int* arr, int n, int root) {int parent root;int child 2 * parent 1;while (child n) {if (child 1 n arr[child] arr[child 1]) {child;}if (arr[parent] arr[child]) {Swap(arr[parent], arr[child]);parent child;child parent * 2 1;} else {break;}}
}
void HeapSort(int* arr, int n) {// 排升序,建大堆int i 0;for (i (n - 1 - 1) / 2; i 0; i--) {AdjustDown(arr, n, i); // 把arr调整为大堆}for (i n - 1; i 0; i--) {Swap(arr[i], arr[0]);AdjustDown(arr, i, 0); // 排序}
}三、交换排序
基本思想交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
1、冒泡排序
实现
void BubbleSort(int* arr, int n) {int end n;while (end 0) {int exchange 0;// 一趟for (int i 1; i end; i) {if (arr[i - 1] arr[i]) {Swap(arr[i - 1], arr[i]);exchange 1;}}//优化// 如果一趟冒泡的过程中没有发生交换则前部分已经有序不需要在冒泡if (exchange 0) {break;}end--;}
}
2、快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。找到一个key左边必key小右边比key大升序。 a.递归
实现
// 三数取中找到不大不小的数让排有序时变为最优
int GetMidIndex(int* a, int begin, int end) {int mid (begin end) / 2;if (a[begin] a[mid]) {if (a[mid] a[end]) {return mid;} else if (a[begin] a[end]) {return begin;} else {return end;}} else {if (a[mid] a[end]) {return mid;} else if (a[begin] a[end]) {return begin;} else {return end;}}
}int PartSort1(int* a, int begin, int end){//单趟快排1 左右指针法// 三数取中的优化int midIndex GetMidIndex(a, begin, end);Swap(a[midIndex], a[end]);int key a[end];int keyindex end;// 如果是右边做key那么一定让左边先走这样保证它们相遇的位置会比key大while (begin end) {while (begin end a[begin] key) {begin;}while (begin end a[end] key) {end--;}Swap(a[begin], a[end]);}Swap(a[begin], a[keyindex]);return end;
}void QuickSort(int* a, int left, int right) {assert(a);if (left right) {int div PartSort(a, left, right);// PrintArray(a, right - left 1);// printf([%d,%d]%d[%d,%d]\n, left, div - 1, div, div 1,right);//[left,div-1]QuickSort(a, left, div - 1);//[div1,right]QuickSort(a, div 1, right);}
} 对于单趟快排的其他办法
法2挖坑法直接覆盖数据不在调用Swap函数性能比左右指针快一点。
// 挖坑法
int PartSort2(int* a, int begin, int end) {// 三数取中的优化int midIndex GetMidIndex(a, begin, end);Swap(a[midIndex], a[end]);int key a[end];// 挖出一个坑可以直接把数据填入到相应位置对左右指针法的一点修改while (begin end) {while (begin end a[begin] key) {begin;}// 左边找到比key大的填到右边的坑begin的位置形成新的坑a[end] a[begin];while (begin end a[end] key) {end--;}// 右边找到比key小的填到左边的坑end的位置形成新的坑a[begin] a[end];}// 把key填入到begin和end相遇的位置上最后一个坑a[end] key;return end;
}法3前后指针法 // 前后指针法
int PartSort3(int* a, int begin, int end) {int prev begin - 1;int cur begin;int key a[end];int keyIndex end;while (cur end) {if (a[cur] key prev ! cur) {Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyIndex]);return prev;
} b.小区间优化
小区间使用插入排序可以减少递归层数提升快排的效率小区间优化
当数据分割到小于等于10个数据时候利用插入排序提升效率。 Q为什么使用插入排序而不是时间复杂度的更低的希尔排序或者堆排序 A1快速排序不断分割后子序列趋近于有序。 前文中讲过当待排数据趋近有序时直接插入排序的时间复杂度趋近于O(N)因此使用直接插入排序的性能要优于希尔排序和堆排序。 A2希尔排序、堆排序、快速排序都是对大量数据的排序。 对于较少数据的排序特别是趋近于有序的数据使用插入排序的综合性能会更高一点。插入排序对于小数据的排序性能不一定优于或者差于其他三种排序。 void QuickSort(int* a, int left, int right) {assert(a);if (right - left 1 10) {// 小区间使用插入排序InsertSort(a left, right - left 1);} else {// 大区间使用快速排序if (left right) {int div PartSort1(a, left, right);// PrintArray(a, right - left 1);// printf([%d,%d]%d[%d,%d]\n, left, div - 1, div, div 1,right);//[left,div-1]QuickSort(a, left, div - 1);//[div1,right]QuickSort(a, div 1, right);}}
}
c.非递归栈
大区间单趟排分割的两个小区间不在递归而是保存在栈里面。 Q为什么这里要用非递归实现呢 A递归实现的快排是由风险的当待排的数据量特别大的时候不断的递归会产生大量的栈帧而计算机的栈帧仅有8M左右的大小会发生栈溢出。 实现
void QuickSortNoR(int* a, int left, int right) {// 栈模拟实现Stack st;StackInit(st); // 一定要记得初始化StackPush(st, right);StackPush(st, left);while (!StackEmpty(st)) {int begin StackTop(st);StackPop(st);int end StackTop(st);StackPop(st);// 返回区间分割的keyIndexint div PartSort1(a, begin, end);// 先对左区间分割,栈中先入右区间if (div 1 end) {// 入右区间右值StackPush(st, end);// 入右区间左值StackPush(st, div 1);}if (div - 1 begin) {// 入左区间右值StackPush(st, div - 1);// 入左区间左值StackPush(st, begin);}}StackDestory(st);
}//非递归同样可以使用小区间优化快排的时间复杂度分析 快排的时间复杂度O(N*logN)。
快排的空间复杂度O(logN)。即栈帧的深度 四、归并排序
基本思想归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。不断地拆分让子序列有序归并一个序列时保持有序。
二路归并将两个有序表合并成一个有序表。 分解:递归图 归并: 递归实现
时间复杂度是O(N*logN)
空间复杂度是O(N)
// 归并函数
void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp) {int left begin1, right end2;int index begin1;while (begin1 end1 begin2 end2) {if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}while (begin1 end1)tmp[index] a[begin1];while (begin2 end2)tmp[index] a[begin2];for (int i left; i right; i)a[i] tmp[i];
}
// 归并的子函数
void _MergeSort(int* a, int left, int right, int* tmp) {if (left right)return;int mid (left right) / 2;//[left,mid] [mid1,right]// 有序则可以合并,现在他们没有序,子问题解决_MergeSort(a, left, mid, tmp);_MergeSort(a, mid 1, right, tmp);// 归并[left,mid] [mid1,right]MergeArr(a, left, mid, mid 1, right, tmp);
}// 递归实现归并排序
void MergeSort(int* a, int n) {assert(a);int* tmp (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
非递归实现
非递归需要修正边界
非递归的时间复杂度从while循环入手O(N*logN)
非递归的空间复杂度O(N)
void MergeSortNoR(int* a, int n) {assert(a);int* tmp (int*)malloc(sizeof(int) * n);// 迭代实现int gap 1;int i 0;while (gap n) {for (i 0; i n; i 2 * gap) {//[i,igap-1] [igap,i2*gap-1]int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;// 1、合并时只有第一组第二组不存在就不需要合并if (begin2 n) {break;}// 2、合并时第二组只有部分数据需要修正end2边界if (end2 n) {end2 n - 1;}MergeArr(a, begin1, end1, begin2, end2, tmp);PrintArray(a, n);}gap * 2;}/*free(tmp);tmp NULL;*/
}
五、内外排序
内外排序并不是特指某一种排序算法而是针对不同存储的空间的排序方法。
内排序指的是在内存中进行排序。
外排序指的是在外存文件、磁盘中进行排序。 外排序实现需要利用C对文件的操作
//合并两个有序数据的文件
void _MergeFile(const char* file1, const char* file2, const char* mFile) {FILE* pf1 fopen(file1, r);if (pf1 NULL) {printf(2:%s\n, strerror(errno));exit(-1);}FILE* pf2 fopen(file2, r);if (pf2 NULL) {printf(3:%s\n, strerror(errno));exit(-1);}FILE* fin fopen(mFile, w);if (fin NULL) {printf(4:%s\n, strerror(errno));exit(-1);}int num1 0;int num2 0;int ret1 fscanf(pf1, %d\n, num1) ! EOF;int ret2 fscanf(pf2, %d\n, num2) ! EOF;while (ret1 ! EOF ret2 ! EOF) { // 文件指针是自动的都往后移动if (num1 num2) {fprintf(fin, %d\n, num1);ret1 fscanf(pf1, %d\n, num1);// fseek(pf2, SEEK_CUR, -1);} else {fprintf(fin, %d\n, num2);ret2 fscanf(pf2, %d\n, num2);// fseek(pf1, SEEK_CUR, -1);}}while (ret1 ! EOF) {fprintf(fin, %d\n, num1);ret1 fscanf(pf1, %d\n, num1);}while (ret2 ! EOF) {fprintf(fin, %d\n, num2);ret2 fscanf(pf2, %d\n, num2);}fclose(pf1);fclose(pf2);fclose(fin);
}void MergeSortFile(const char* file) {FILE* pf fopen(file, r);if (pf NULL) {printf(1:%s\n, strerror(errno));exit(-1);}// 分割成小文件,内存排序后写到小文件中int n 10;int a[10] {0};int num 0;int i 0;// char* subfile (char *)malloc(sizeof(char));char subfile[20];int filei 0;while (fscanf(pf, %d\n, num) ! EOF) {if (i n - 1) {a[i] num;} else {a[i] num;QuickSort(a, 0, n - 1);sprintf(subfile, %d, filei);FILE* fin fopen(subfile, w);for (i 0; i n; i) {fprintf(fin, %d\n, a[i]);}fclose(fin);i 0;memset(a, 0, sizeof(int) * n);}}// 文件两两合并char mFile[100] 12;char file1[100] 1;char file2[100];for (i 1; i n; i) {sprintf(file2, %d, i);// 读取file1和file2归并出mfile_MergeFile(file1, file2, mFile);strcpy(file1, mFile);sprintf(mFile, %s%d, mFile, i 1);}fclose(pf);
}六、非比较排序 非比较排序是很“小众”的排序因为这两种排序只适用于整数类型的排序。不能排序浮点数和字符串型的数据对于这些类型的数据要用比较排序法来排序。
1、计数排序
思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。是一种非比较排序。
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 实现
void CountSort(int* a, int n) {int min a[0];int max a[0];int i 0;for (i 0; i n; i) {if (min a[i]) {min a[i];}if (max a[i]) {max a[i];}}int range max - min 1;int* countArr (int*)calloc(range, sizeof(int));if (countArr NULL) {return;}// memset(countArr, 0, sizeof(int) * range);for (i 0; i n; i) {countArr[a[i] - min]; // 偏移量映射}int index 0;for (i 0; i range; i) {int j 0;for (j 0; j countArr[i]; j) {a[index] i min;}}free(countArr);
}
2、基数排序 基数排序即桶排序。可以参考【算法】桶排序Bucket Sort详解-CSDN博客桶排序不是很重要了解即可。 总结
1、几种排序的时间复杂度比较 2、排序的稳定性 稳定性由某一算法完成的排序后数组中相同元素的相对位置保持不变。即表示该算法是稳定的否则表示该算法不稳定。
3、归并外部文件的排序了解即可
