公司免费网站域名注册,建立诊断的步骤,宜城网站建设网络推广,wordpress wmv这里写目录标题 排序插入排序直接插入排序希尔排序 选择排序直接选择排序堆排序向下调整堆排序 交换排序冒泡排序 排序
插入排序
直接插入排序
直接插入排序是O#xff08;N^2#xff09;的排序算法
从0下标开始往后排
void InsertSort(int* a,int n)//直接插入排序
{fo… 这里写目录标题 排序插入排序直接插入排序希尔排序 选择排序直接选择排序堆排序向下调整堆排序 交换排序冒泡排序 排序
插入排序
直接插入排序
直接插入排序是ON^2的排序算法
从0下标开始往后排
void InsertSort(int* a,int n)//直接插入排序
{for (int i 0; i n - 1; i)//n-1是因为不能数组越界{int emd i;int tmp a[emd1];//保存一下emd的下一个数据防止在循环过程中被覆盖while (emd 0)//如果emd大于等于0 那么会遍历一次数组 并且排序{//每次都排序一次if (tmp a[emd])//如果tmp比a[emd]小那么继续往前找{a[emd 1] a[emd];}else//如果tmp比a[emd]大那么跳出循环 //不直接赋值的原因是因为 有可能遍历完数组也没有tmp大的情况{break;}emd--;}a[emd 1] tmp;}
}希尔排序
希尔排序是ON^1.3的排序算法 希尔排序的方式是让数组进行预处理让数组接近有序 一般来说 预处理中 每个下标要要跟下标gap的数组进行对比 如果小于那么交 希尔排序中 进行次数越多 但也到了一定程度也是下降趋势
void ShellSort(int* a, int n)//希尔排序 时间复杂度O(N^1.3)
{//如果 gap 1 那么就是有序排序int gap n;//设置预排长度while (gap 1){gap / 2;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];//先换到 endgap的位置end - gap;//如果end为负跳出循环 }else{break;}}a[end gap] tmp;//因为end变成负数了或者 break了 位置不变}}
}选择排序
直接选择排序
直接选择排序的ON^2的排序算法 直接选择排序是让数据先选出当前一组中的 最小与最大的数 然 后存储起来 最后复赋值到当前一组总最前的位置与最后的位置 需要注意的是当 最小赋值到最前的位置可能 最大的位置在 最前面那个位置 那么就要进行 赋值到原来最小的位置
void SelectSort(int* a, int n)//直接选择排序 O(N^2)
{int begin 0, end n - 1;while (begin end){int min begin, max begin;for (size_t i begin1; i end; i)//每排一次就确定一次当前排序的最大最小{if (a[i] a[max]){max i;}if (a[i] a[min]){min i;}}Sawp(a[begin], a[min]);if (max begin)//如果 max begin的话 min会先跟 begin这个位置换 所以要 赋值到换后min的位置{max min;}Sawp(a[end], a[max]);begin;end--;}
}堆排序
堆排序是ON*logN的排序算法 堆排序是利用建堆大堆并且使用向下排序 为什么使用大堆 因为如果建小堆 那么堆顶的位置被交换之后 那么这个堆可能就不是个堆了 大堆即使堆顶变了也不影响 其他地方不是堆
向下调整
void AdjustDown(HPDataType* a, int n, int parent)//向下调整
{int child parent * 2 1;while (child n)//确保这个子树的下标 小于数组大小{if (child 1 na[child 1] a[child])//child1这个右子树不存在那么 则直接输出左子树//假设做孩子小 如果比右孩子小的话 换成右孩子{child;}if (a[child] a[parent])//小孩比父亲大那么交换大堆//小的孩子比 父亲小 那么交换小堆{Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}}堆排序
void HeapSort(HPDataType* a, int n)//堆排序
{int end n - 1;//向下调整的建大堆//o(n)for (int i (end-1)/2; i 0; i--)//i 父亲节点{AdjustDown(a, n, i);}//向下排序//o(n*log(n))while (end 0){Sawp(a[0], a[end]);AdjustDown( a, end, 0);end--;}
}交换排序
冒泡排序
冒泡排序是ON^2的排序算法 冒泡排序是用2次循环然后进行交换
void BubbleSort(int* a, int n)//冒泡排序
{for (int i 0; i n; i){int b 0;for (int j 1; j n-i; j){if(a[j-1]a[j]) {Sawp(a[j-1], a[j]);b 1;}}if (b 0){break;}}
}
