数据结构（7）常见算法稳定性和时间复杂度

1.重点掌握一下算法顺序表数组*单向链表*双向链表*队列*栈哈希表二叉树程序设计 数据结构 算法算法对数据操作的流程步骤2.算法的设计2.1.正确性语法正确合法的输入能得到合理的结果。对非法的输入给出满足要求的规格说明对精心选择甚至刁难的测试都能正常运行结果正确2.2. 可读性便于交流阅读理解 高内聚 低耦合函数命名以动宾形式命名内核命名get_max_num();驼峰命名getMaxNum();2.3. 健壮性输入非法数据能进行相应的处理而不是产生异常2.4. 高效率(时间复杂度)2.5. 低存储空间复杂度3. 算法时间复杂度执行这个算法所花时间的度量3.1. 定义将数据量增长和时间增长用函数表示出来这个函数就叫做时间复杂度。一般用大O表示法On-----?时间复杂度是关于数据n的一个函数随着n的增加时间复杂度增长较慢的算法时间复杂度低3.2.时间复杂度的计算规则用常数1 取代运行时间中的所有加法常数。在修改后的运行函数中只保留最高阶项。如果最高阶存在且系数不是1则去除这个项相乘的常数。Fun(int a,int b)O(1){Int tmp a;A b;B tmp;}for(i0;in; i 2)O(n){Int tmp a;A b;B tmp;}for (i 1; i n; i * 2)O(logn)1*2*2*2*2*2...n{2 ^x no(logn)}for(i0;in;i)O(nlogn){for (i 0; i n; i * 2)o(logn){}}for(i0;in;i )O(n^2)0 1 2 n-1{for(ji;jn;j) n n-1 n-2 ... 1 (n1)*n/2 n^2{Int tmp a;A b;B tmp;}}O(1)O(logn)O(n)O(nlogn)O(n^2)O(n^3)O(2^n)O(n!)O(n^n)常见函数的时间复杂度和稳定性4.排序和查找算法1. 冒泡排序2. 选择排序3. 插入排序4. 快速排序5. 二分查找排序算法1. 排序思想2. 时间复杂度3. 排序算法稳定性在待排序列中出现了两个相同数据经过排序这两个相同数据的相对位置没有发生变化该排序算法就是一个稳定的排序算法。1.冒泡排序//冒泡 void maopao(int *a, int size) { for (int i size - 1; i 0; i--) { for (int j 0; j i; j) { if (a[j] a[j 1]) { int t a[j]; a[j] a[j 1]; a[j 1] t; } } } }1. 排序思想 相邻两两元素进行比较将较大值向后移一趟完成将最大值存储在最后位置。2. 时间复杂度O(n^2)3. 排序算法稳定性稳定2. 选择排序//选择 void xuanze(int *a, int size) { for (int j 0; j size - 1; j) { for (int i j 1; i size; i) { if (a[j] a[i]) { int t a[j]; a[j] a[i]; a[i] t; } } } }1. 排序思想 选择排序将待排位置的数据和后面的数据依次进行比较将较小的数据存入到待排位置经过一趟排序待排位置存储最小值。2. 时间复杂度O(n^2)3. 排序算法稳定性不稳定3. 插入排序//插入排序 void charu(int a[], int size) { int j 0; int tmp 0; for (int i 1; i size; i) { j i; tmp a[i]; while (j 0 tmp a[j - 1]) // j0必须在前面防止数组越界 { a[j] a[j - 1]; j--; } a[j] tmp; } }1. 排序思想 将待排的数据插入到一个已有序的序列中确保每次插入后该序列任然有序。2. 时间复杂度O(n^2)3. 排序算法稳定性稳定4. 希尔排序//希尔排序 void shell_sort(int *a, int len) { int inc 0; int j 0; int tmp 0; for (inc len / 2; inc 0; inc / 2) { for (int i inc; i len; i) { j i; tmp a[i]; while (j inc tmp a[j - inc]) // jinc必须在前面防止数组越界 { a[j] a[j - inc]; j j - inc; } a[j] tmp; } } }1. 排序思想 将待排序列分成若干个子序列分别对这若干个子序列进行插入排序。增量序列2. 时间复杂度O(nlogn)~O(n^2)3. 排序算法稳定性不稳定5. 快速排序//快速排序 void quick_sort(int *a,int begin,int end) { if(beginend) { return; } int ibegin; int jend; int keya[i]; while (ij) { while(ija[j]key) { j--; } a[i]a[j]; while(ija[ikey]) { i; } a[j]a[i]; } a[i]key; quick_sort(a,begin,j-1); quick_sort(a,j1,end); }1. 排序思想 选取一个基准值从两头向中间依次和基准值比较将比基准值大的存在后面的序列比基准值小的存在前面的序列经过一趟排序将基准值存入合适的位置。并且以基准值为界划分左右序列继续按照以上方式排序。2. 时间复杂度O(nlogn)3. 排序算法稳定性不稳定6.二分查找/折半查找前提条件必须是一个有序的序列//二分法查找 int bin_find(int *a,int len,int data) { int begin 0; int end len-1; int cnt 0; while(beginend) { cnt; int mid (begin end)/2; if(dataa[mid]) { printf(find %d\n,a[mid]); printf(cnt %d\n,cnt); printf(NO.%d\n,mid1); return 0; } else if(dataa[mid]) { beginmid1; } else if(dataa[mid]) { end mid-1; } } printf(cnt %d\n, cnt); printf(Not find\n); return -1; }1. 查找思想 算法从序列的中间元素开始比较目标值如果中间元素等于目标值则查找成功。如果中间元素大于目标值则目标值在左半部分将搜索范围缩小到左半区。如果中间元素小于目标值则目标值在右半部分将搜索范围缩小到右半区。重复上述步骤直到找到目标元素或搜索范围为空查找失败2. 时间复杂度O(logn)