h5可以用什么网站做,推广方案的推广内容怎么写,网站建设的商业目的,pinterest设计网1.排序的概念及其运用
2.插入排序的概念及实现
3.希尔排序的概念及实现
4.选择排序概念及实现
总代码#xff08;对比各个排序在大量的数据情况排序所化的时间#xff09;#xff1a; 1.排序的概念及其运用
1.1排序的概念 排序#xff1a;所谓排序#xff0c;就是使…1.排序的概念及其运用
2.插入排序的概念及实现
3.希尔排序的概念及实现
4.选择排序概念及实现
总代码对比各个排序在大量的数据情况排序所化的时间 1.排序的概念及其运用
1.1排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不断地在内外存之间移动数据的排序。
1.2排序的运用
在网上购物时会出现综合销量及评论数等会以此为参考来排序选出综合最高销量最高的产品以及院校排名这些都使用了排序。
以下图片仅参考 1.3 常见的排序算法 2.插入排序的概念及实现
2.1插入排序的概念
就像扑克牌一样每拿到一张牌都要放进已经排好序的牌里面用这张牌跟里面的比较再把这张牌放到合适的位置插入排序的原理就是把数插入已经排好序的数里面比较排好数的里面的每一个数找到位置就插入。 代码
#includestdio.h
void InsertSort(int* a,int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end1];while (end 0){if (tmp a[end]){a[end1] a[end];end--;}else{break;}}a[end 1] tmp;}
}
int main()
{int a[10] { 3,4,5,1,2,6,7,8,2 };int size sizeof(a) / sizeof(a[0]);InsertSort(a,size);for (int i 0; i 9; i){printf(%d , a[i]);}return 0;
}
代码分析
while循环出去有俩种情况1是触发break二是while循环的条件不满足在循环外把tmp赋给数组下标为end1的位置 是因为如果是while循环结束的话刚好也可以赋值但是在里面的话因为while结束的就无法把数据加回去移动带来覆盖会有一位重复需要赋值来填回去。
动态图关于插入排序24年-05月27日--排序/动图/插入排序.gif · 比特杭哥/113期 - Gitee.com
2.2冒牌排序的时间复杂度
冒泡排序的最坏情况
假设if条件每次都会执行那么时间复杂度就为O(N^2).
最好的情况
上面冒泡代码不能做到O(N),需要对其优化才能使冒泡排序达到最好情况
设置一个flag去判断是否触发了if条件如果触发了就置为0后面再去检验值是否为一开始的初始值是就说明没有触发if条件没触发就说明顺序是排好的只执行了里面的if判断所以时间复杂度是O(N)。
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){int flag 1;for (int j 0; j n-i-1; j){if (a[j] a[j 1]){int tmp a[j];a[j] a[j 1];a[j 1] tmp;flag 0;}}if (flag 1){break;}}
}
2.3插入排序的时间复杂度
按照最坏打算
既逆序情况 最好的情况
当数据是以升序排序时里面的循环不执行会从break跳出则只有for循环执行所以时间复杂度就为O(N)。
插入排序与冒泡排序的时间复杂度虽然是一样的但插入排序是比冒泡排序好因为插入排序最坏的情况很难达到只有是逆序或者接近这个情况的情况下插入排序才会慢下来而冒泡排序一般都是O(N^2),因为冒泡每次遍历选出其中最大的放最后if的条件任意触发。
void BubbleSort(int* a, int n)//冒泡排序
{for (int i 0; i n; i){for (int j 0; j n-i-1; j){if (a[j] a[j 1]){int tmp a[j];a[j] a[j 1];a[j 1] tmp;}}}
} 3.希尔排序的概念及实现
3.1希尔排序概念
希尔排序与插入排序密不可分基于插入排序来实现希尔排序的。
希尔排序首先会对数据进行预排序让数组接近有序再进行插入排序因为插入排序怕的是数组是逆序情况。
预排序把数组在逻辑上分成gap组gap是间隔的距离然后对每个gap组进行插入排序这样可以使大的数据跑到比较后面的位置小的数据会跑到比较前面的位置gap设置的越大大的数据越快到后面小的数据越快到前面越不接近有序gap设置的越小数据跳的慢但是会越接近有序的情况gap为1的时候就是插入排序了希尔排序就是慢慢把gap的值调小设置gap是为了最后一次gap为一做铺垫为了插入排序能更快的完成最后gap为一时执行插入排序。 3.2希尔排序的代码实现
代码实现1
void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
void ShellSort1(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){swap(a[end], a[end gap]);end--;}elsebreak;}a[end gap] tmp;}}
}
代码实现二
void ShellSort2(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){swap(a[end], a[end gap]);end - gap;}elsebreak;}a[end gap] tmp;}}}
} 代码分析上面俩个代码的样子不一样但是效率是一样的俩种都可以使用
n是数组的个数一般gap的值都为个数的三分之一1加一是为了最后gap的值能达到一进行插入排序gap/2的效率不如gap/3大量数据实验得出的代码一是多个gap组同时进行预排序每次i加一但是比的是gap距离的数据gap第一组的第一个跟其gap距离的比完后第二个gap组的第一个跟其gap距离的比再到第三个gap组的第一个与其gap距离的数据比较再到第二个等等代码二则是第一个gap组会一直比完才到第二个gap组比。还需要注意的是循环终止条件是n-gap是因为循环里面有endgapngap-gap刚好是为n也就是数组最后一个数据下标的下一个有效数据的下一个是不能访问的会造成越界访问数组最多能访问到n-1的位置如果是in则a[endgap]就会越界了。 3.3希尔排序的时间复杂度简单分析
希尔排序的时间复杂度为O(N^1.3)。 4.选择排序概念及实现
选择排序就是遍历数组找到最小的数据并把它放在最前面可以对它进行优化就是在遍历的同时把最大和最小的数据找出来并放在俩边 代码实现
void SelectSort(int* a, int n)
{int begin, end;begin 0;end n - 1;while (begin end){int mini, max;mini max begin;for (int i begin1; i end; i){if (a[mini] a[i]){mini i;}if (a[max] a[i]){max i;}}swap(a[mini], a[begin]);swap(a[max], a[end]);end--;begin;}
}
代码分析
因为是找最大和最小并放在俩边所以begin和end会慢慢往中间靠近在定义最小值和最大值去和数组的每一个数比较比定义的最大值大就交换一下下标比最小值小就交换 下标遍历完后在交换值并且把begin和end--因为begin和end都放好了对应的值要放其它位置的值。
总代码对比各个排序在大量的数据情况排序所化的时间
test.c文件
#includeSort.hvoid TestInsertSort()
{int a[] { 2,4,1,7,8,3,9,2 };InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestShellSort()
{int a[] { 9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5 };//InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestSelectSort()
{//int a[] { 9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5 };//InsertSort(a, sizeof(a) / sizeof(int));//int a[] { 2,4,1,7,8,3,9,2 };int a[] { 9,1,2,5,7,4,6,3 };PrintArray(a, sizeof(a) / sizeof(int));SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestOP()
{srand(time(0));const int N 1000000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);int* a3 (int*)malloc(sizeof(int) * N);int* a4 (int*)malloc(sizeof(int) * N);int* a5 (int*)malloc(sizeof(int) * N);int* a6 (int*)malloc(sizeof(int) * N);int* a7 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand()i;a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];}int begin1 clock();//InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();int begin3 clock();//SelectSort(a3, N);int end3 clock();int begin4 clock();HeapSort(a4, N);int end4 clock();int begin5 clock();//QuickSort(a5, 0, N - 1);int end5 clock();int begin6 clock();//MergeSort(a6, N);int end6 clock();int begin7 clock();//BubbleSort(a7, N);int end7 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(SelectSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);printf(QuickSort:%d\n, end5 - begin5);printf(MergeSort:%d\n, end6 - begin6);printf(BubbleSort:%d\n, end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{//TestInsertSort();//TestShellSort();TestSelectSort();//TestOP();return 0;
}
Sort.h文件
#pragma once
#includestdio.h
#includestdlib.h
#includetime.hvoid PrintArray(int* a, int n);// 有实践意义
void InsertSort(int* a, int n);void ShellSort(int* a, int n);void ShellSort(int* a, int n);void HeapSort(int* a, int n);// 适合教学实践中没啥价值
void BubbleSort(int* a, int n);void SelectSort(int* a, int n)
Sort.c文件
#includeSort.hvoid PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}// 时间复杂度O(N^2) 什么情况最坏逆序
// 最好顺序有序O(N)
// 插入排序
void InsertSort(int* a, int n)
{// [0, n-1]for (int i 0; i n - 1; i){// [0, n-2]是最后一组// [0,end]有序 end1位置的值插入[0,end]保持有序int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
}// O(N^1.3)
//void ShellSort(int* a, int n)
//{
// /*int gap 3;
// for (int j 0; j gap; j)
// {
// for (size_t i j; i n - gap; i gap)
// {
// int end i;
// int tmp a[end gap];
// while (end 0)
// {
// if (tmp a[end])
// {
// a[end gap] a[end];
// end - gap;
// }
// else
// {
// break;
// }
// }
// a[end gap] tmp;
// }
// }*/
//
// int gap n;
// while (gap 1)
// {
// // 1保证最后一个gap一定是1
// // gap 1时是预排序
// // gap 1时是插入排序
// gap gap / 3 1;
//
// for (size_t i 0; i n - gap; i)
// {
// int end i;
// int tmp a[end gap];
// while (end 0)
// {
// if (tmp a[end])
// {
// a[end gap] a[end];
// end - gap;
// }
// else
// {
// break;
// }
// }
// a[end gap] tmp;
// }
// //printf(gap:%2d-, gap);
// //PrintArray(a, n);
// }
//}// O(N ^ 1.3)
void ShellSort(int* a, int n)
{int gap n;while (gap 1){// 1保证最后一个gap一定是1// gap 1时是预排序// gap 1时是插入排序gap gap / 3 1;for (size_t i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}void AdjustDown(int* a, int n, int parent)
{// 先假设左孩子小int child parent * 2 1;while (child n) // child n说明孩子不存在调整到叶子了{// 找出小的那个孩子if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向下调整建堆 O(N)for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}// O(N^2) 最坏
// O(N) 最好
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){// 单趟int flag 0;for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);flag 1;}}if (flag 0){break;}}
}void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);Swap(a[end], a[maxi]);begin;--end;}
}
