建设网站的费用怎么做账,上海设计网站大全,网页模板源代码之家,四川自贡彩灯制作公司各位CSDN的uu们你们好呀#xff0c;今天小雅兰的内容是数据结构与算法啦#xff0c;是排序#xff01;#xff01;#xff01;下面#xff0c;让我们进入七大排序的世界吧#xff01;#xff01;#xff01; 排序的概念及其运用
排序的概念 排序#xff1a;所谓排序… 各位CSDN的uu们你们好呀今天小雅兰的内容是数据结构与算法啦是排序下面让我们进入七大排序的世界吧 排序的概念及其运用
排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 排序运用 常见的排序算法 常见排序算法的实现
插入排序
基本思想 插入排序是一种简单的插入排序法 其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想 直接插入排序 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 //直接插入排序
void InsertSort(int* a, int n)
{int i 0;for (i 1; i n; i){//[0,end]有序插入tmp依旧有序int end i - 1;int tmp a[i];while (end 0){//插入的数据比原来的数据小if (a[end] tmp){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
} 直接插入排序的特性总结 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2) 空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 希尔排序( 缩小增量排序 ) 希尔排序法又称缩小增量法。 希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工 作。当到达1时所有记录在统一组内排好序。 gap越大大的数可以更快的到后面小的数可以更快的到前面越不接近有序gap越小大的小的挪动越慢但是它越接近有序gap1就是直接插入排序 void ShellSort(int* a, int n)
{//1.gap1,预排序//2.gap1,直接插入排序int gap n;while (gap 1){gap gap / 3 1;//1可以保证最后一次一定是1for (int i 0; i n - gap; i)//防止越界{int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end end - gap;}else{break;}}a[end gap] tmp;}}
} 希尔排序的特性总结 希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定 《数据结构(C语言版)》--- 严蔚敏 《数据结构-用面相对象方法与C描述》--- 殷人昆 稳定性不稳定 暂且认为希尔排序的时间复杂度是O(N^1.3) 测试一下直接插入排序和希尔排序
void TestInsertSort()
{int a[] { 2,1,4,3,6,5,7,9,8,10 };PrintArray(a, sizeof(a) / sizeof(a[0]));InsertSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}
void TestShellSort()
{int a[] { 2,1,4,3,6,5,7,9,8,10 };PrintArray(a, sizeof(a) / sizeof(a[0]));ShellSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
} 选择排序
基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 直接选择排序: 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素 若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换 在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素 void Swap(int* a1, int* a2)
{int tmp *a1;*a1 *a2;*a2 tmp;
}
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int maxi begin;int mini begin;for (int i begin; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);//如果maxi和begin重叠修正一下即可if (begin maxi){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
} 直接选择排序的特性总结 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2) 空间复杂度O(1) 稳定性不稳定 堆排序 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 //向下调整算法
void AdjustDown(int* a, int n, int parent)
{//默认左孩子小int child parent * 2 1;while (child n)//孩子在数组范围内{//选出左右孩子中大的那一个//有可能假设错了//左孩子不存在一定没有右孩子——完全二叉树//左孩子存在有可能没有右孩子if (child 1 n a[child 1] a[child])// 右孩子存在 右孩子左孩子//不能这么写 if (a[child 1] a[chid] child 1 n )//这样写会有越界的风险 因为是先访问了数组中的元素 再去比较右孩子是否存在{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)
{//建堆——向下调整建堆int i 0;for (i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//升序——建大堆int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
} 堆排序的特性总结 堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN) 空间复杂度O(1) 稳定性不稳定 测试一下直接选择排序和堆排序
void TestSelectSort()
{int a[] { 2,1,4,3,6,5,7,9,8,10 };PrintArray(a, sizeof(a) / sizeof(a[0]));SelectSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}
void TestHeapSort()
{int a[] { 2,1,4,3,6,5,7,9,8,10 };PrintArray(a, sizeof(a) / sizeof(a[0]));HeapSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
} 交换排序 基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 冒泡排序 void BubbleSort(int* a, int n)
{for (int j 0; j n; j){bool exchange false;for (int i 1; i n - j; i){if (a[i - 1] a[i]){int tmp a[i];a[i] a[i - 1];a[i - 1] tmp;exchange true;}}if (exchange false){break;}}
} 冒泡排序的特性总结 冒泡排序是一种非常容易理解的排序时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 总结
测试一下上述五大排序的性能
// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N 100000;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();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 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(BubbleSort:%d\n, end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}
测试性能最好使用Release版本 通过上面这幅图我们可以发现冒泡排序和直接选择排序的性能较差直接插入排序性能中等水平希尔排序和堆排序的性能较好。 上面所有排序的源代码
Sort.c的内容 #includeSort.h void PrintArray(int* a, int n) { int i 0; for (i 0; i n; i) { printf(%d , a[i]); } printf(\n); } void InsertSort(int* a, int n) { int i 0; for (i 1; i n; i) { int end i - 1; int tmp a[i]; while (end 0) { //插入的数据比原来的数据小 if (a[end] tmp) { a[end 1] a[end]; --end; } else { break; } } a[end 1] tmp; } } void ShellSort(int* a, int n) { //1.gap1,预排序 //2.gap1,直接插入排序 int gap n; while (gap 1) { gap gap / 3 1; //1可以保证最后一次一定是1 for (int i 0; i n - gap; i) { int end i; int tmp a[end gap]; while (end 0) { if (a[end] tmp) { a[end gap] a[end]; end end - gap; } else { break; } } a[end gap] tmp; } } } void BubbleSort(int* a, int n) { for (int j 0; j n; j) { bool exchange false; for (int i 1; i n - j; i) { if (a[i - 1] a[i]) { int tmp a[i]; a[i] a[i - 1]; a[i - 1] tmp; exchange true; } } if (exchange false) { break; } } } void Swap(int* a1, int* a2) { int tmp *a1; *a1 *a2; *a2 tmp; } void SelectSort(int* a, int n) { int begin 0; int end n - 1; while (begin end) { int maxi begin; int mini begin; for (int i begin; i end; i) { if (a[i] a[maxi]) { maxi i; } if (a[i] a[mini]) { mini i; } } Swap(a[begin], a[mini]); //如果maxi和begin重叠修正一下即可 if (begin maxi) { maxi mini; } Swap(a[end], a[maxi]); begin; --end; } } //向下调整算法 void AdjustDown(int* a, int n, int parent) { //默认左孩子小 int child parent * 2 1; while (child n)//孩子在数组范围内 { //选出左右孩子中大的那一个 //有可能假设错了 //左孩子不存在一定没有右孩子——完全二叉树 //左孩子存在有可能没有右孩子 if (child 1 n a[child 1] a[child]) // 右孩子存在 右孩子左孩子 //不能这么写 if (a[child 1] a[chid] child 1 n ) //这样写会有越界的风险 因为是先访问了数组中的元素 再去比较右孩子是否存在 { 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) { //建堆——向下调整建堆 int i 0; for (i (n - 1 - 1) / 2; i 0; i--) { AdjustDown(a, n, i); } //升序——建大堆 int end n - 1; while (end 0) { Swap(a[0], a[end]); AdjustDown(a, end, 0); --end; } } Sort.h的内容 #pragma once #includestdio.h #includestdlib.h #includetime.h #includestdbool.h void PrintArray(int* a, int n); // 直接插入排序 void InsertSort(int* a, int n); // 希尔排序 void ShellSort(int* a, int n); // 直接选择排序 void SelectSort(int* a, int n); // 堆排序 void AdjustDown(int* a, int n, int root); void HeapSort(int* a, int n); // 冒泡排序 void BubbleSort(int* a, int n); test.c的内容 #includeSort.h void TestInsertSort() { int a[] { 2,1,4,3,6,5,7,9,8,10 }; PrintArray(a, sizeof(a) / sizeof(a[0])); InsertSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } void TestShellSort() { int a[] { 2,1,4,3,6,5,7,9,8,10 }; PrintArray(a, sizeof(a) / sizeof(a[0])); ShellSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } void TestBubbleSort() { int a[] { 2,1,4,3,6,5,7,9,8,10 }; PrintArray(a, sizeof(a) / sizeof(a[0])); BubbleSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } void TestSelectSort() { int a[] { 2,1,4,3,6,5,7,9,8,10 }; PrintArray(a, sizeof(a) / sizeof(a[0])); SelectSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } void TestHeapSort() { int a[] { 2,1,4,3,6,5,7,9,8,10 }; PrintArray(a, sizeof(a) / sizeof(a[0])); HeapSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } // 测试排序的性能对比 void TestOP() { srand(time(0)); const int N 100000; 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(); 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 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(BubbleSort:%d\n, end7 - begin7); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); } int main() { //TestInsertSort(); //TestShellSort(); //TestBubbleSort(); //TestSelectSort(); //TestHeapSort(); TestOP(); return 0; } 好啦小雅兰今天的学习内容就到这里结束啦后续会继续更新快速排序和归并排序的知识点
