昌平区事业单位公共知识培训网站,网站建设优化保定,有没有可以直接看的,北京形势紧张C实现排序算法 代码地址
vectorunsigned int cVec;
int nSize cVec.size();1 冒泡排序
算法思路#xff1a; 每两两相邻的数值都会比较大小#xff0c;前面比后面大的时候就交换位置#xff0c;否则就不动。
代码#xff1a; void BubbleSort() {//优化#x…C实现排序算法 代码地址
vectorunsigned int cVec;
int nSize cVec.size();1 冒泡排序
算法思路 每两两相邻的数值都会比较大小前面比后面大的时候就交换位置否则就不动。
代码 void BubbleSort() {//优化//可以设置一个标记为表示前一轮是否移动过数字如果没有则表示后一位均比前一位大//即数组已经有序bool flag true;//每次j循环完成后表示数组的第i位是数组里最大的for (int i nSize - 1; i 0 flag; --i) {flag false;//从数组第一个值开始for (int j 0; j i; j) {//和后一个值比较如果大于就交换位置if (cVec[j] cVec[j 1]) {std::swap(cVec[j], cVec[j 1]);flag true;}}}
}每次i循环结束cVec[i] 就是前i个最大的就是每次循环结束最大的那个值就会到最后面。所以j只到i
2 插入排序
算法思路 假设前 i 个值有序不包括 i这时要排序i的时候就要将 i 和前面的值比较找到一个位置j的值比他大的这样就将这个位置后面的值 [j1,i-1] 全部后移将 i 位置的值覆盖。
void InsertSort() {for (int i 1; i nSize; i) {//这个是前i个数for (int j 0; j i; j) {if (cVec[i] cVec[j]) {//这个是移动循环unsigned int temp cVec[i];for (int k i - 1; k j; --k) {cVec[k 1] cVec[k];}cVec[j] temp;break;}}}
}3 希尔排序
算法思路 和插入算法类似首先确定分组长度即下标间隔为i的分为同一组 当i3时 第1组为0,3,6,9 第2组为1,4,7,10 第3组为2,5,8 然后分别对这些分组进行插入排序然后减少分组长度即 –i重新确定分组重新排序直到i0 第一个循环是确定分组长度一般是数组长度的一半 第二个循环是确定分组的起始下标即分组的第一个下标位置 第三个循环和第四个循环和插入排序相同
void ShellSort() {//分组距离for (int i nSize / 2; i 0; i/2) {//起始下标即将[j]插入到前面去for (int j 0; j i ; j) {//k循环表示列举每个分组的值 for (int k ji; k nSize; k i) {//l循环表示在前面的值中找到位置插入因为j是第一个值的位置所以要大于他for (int l k; l j; l - i) {//如果当前位置的值比前一个位置的小就交换位置否则就已经是有序了if (cVec[l] cVec[l - i]) {std::swap(cVec[l], cVec[l - i]);}else {break;}}}}}
}4 选择排序
算法思路 选择个最大/最小的值然后和数组的尾/头交换位置 这里是选择最小值的。
void sort::SelectSort() {//每次j循环结束表示找到一个最小的值了for (int i 0; i nSize; i) {//假设m为当前最小值的下标位置int m i;//在m后面的下标中找到比下标m还要小的值for (int j i1; j nSize; j) {if (cVec[m] cVec[j]) {m j;}}//发现这个m的值改变了就交换他们的位置if (m ! i) {std::swap(cVec[m], cVec[i]);}}
}5 快速排序
算法思路 设置两个变量b、e分别保存数组的头和尾的下标 设置两个变量bsite、esite保存刚开始时b、e的值 再随便找一个值flag这里就找数组的第一个值 flagcVec[b] 0、如果be表示数组里就只有1个数那就没必要排序了直接返回就好了 1、从数组后面开始找找到第一个比flag小的值即cVec[e]flag 2、交换他们的位置这时cVec[e]后面的值都是比flag要大。 3、从数组前面开始找找到第一个比flag大的值即cVec[b]flag 4、交换他们的位置这是**cVec[b]前面的值都是比cVec[b]**小的值 5、比较 b 是否等于 e: 如果是的话表示 cVec[b] 前面的值都比它小后面的值都比它大这样的话可以将数组以 cVec[b] 为界限分成两个数组分别是 cVec[bsite]-cVec[b-1]、cVec[b1]-cVec[esite] 如果不是的话回到第1步继续
void quickSort(int b,int e) {if (b e) {return;}unsigned int flag cVec[b];int bsite b, esite e;while (b e) {while (be flag cVec[e]) {--e;}if (flag cVec[e]) {std::swap(cVec[b], cVec[e]);b;}while (b e flag cVec[b]) {b;}if (flag cVec[b]) {std::swap(cVec[b], cVec[e]);--e;}}quickSort(e 1, esite);quickSort(bsite, b-1);}6 堆排序
算法思路 堆分为大顶堆/小顶堆表示双亲结点大于/小于子结点。 这里以大顶堆为例。 1、将数组构造成大顶堆这样cVec[0] 就是最大的值了 2、然后将cVec[0] 和 cVec[nSize-1]也就是最后一个值交换位置这样nSize的值就减1因为最后一个值已经是最大的 3、交换位置后数组就不是大顶堆了这时又要重新构造大顶堆 4、重复2、3步直到nSize为 0
现在问题是怎么构建大顶堆了 每个结点的子结点的下标分别是 左节点leftsite * 2 1 右结点rightsite * 2 2 这样的话可以从数组的中间位置nSize/2开始递减直到等于0 从下标nSize/2开始如果左右结点存在并且比父结点还大就交换它们的位置这样父结点就比子结点大了。
那剩下的是构造大顶堆后也交换值的位置怎么将交换后的数组恢复回大顶堆呢 1、首先看看左结点是否在数组的长度内即 site*21 nSize在的话就往下执行不在的话表示该结点没有子结点可以直接返回了。 2、比较cVec[site] 结点和 它的子结点cVec[site*21] 、cVec[site*22] 的大小如果子结点存在且比它大那就选最大的子结点就交换位置如果子结点不存在那就直接返回 3、交换位置后就要修改site的值保证site的子结点不会比它大回到第1步直到不存在子结点。
void buildHeapify(int site,int size) {int temp;int left site * 2 1;int right site * 2 2;temp left;while (left size) {//找到子结点中比较大的那个if (right size cVec[right] cVec[left]) {temp right;}//再和双亲结点比较大小如果小于等于就结束if (cVec[site] cVec[temp]) {break;}//如果大于双亲结点就交换位置并继续往下调整std::swap(cVec[temp], cVec[site]);site temp;left site * 2 1;right site * 2 2;temp left;}}void initHeapify() {int half nSize / 2;for (int j half; j 0; --j) {buildHeapify(j,nSize);}
}void HeapSort() {initHeapify();//initHeapify构造出大顶堆for (int i 0; i nSize; i) {std::swap(cVec[0], cVec[nSize - 1 - i]);//调整结点位置恢复大顶堆buildHeapify(0,nSize-1-i);}
}7 归并排序
算法思路 1、判断当前数组长度是否为1不是就往下是就结束 2、将当前数组以nSize/2为中心分成两段 3、对分成两段的数组进行排序
这样循环的话将1个数组分成两个数组分别对这两个数组进行排序然后再将这两个数组有序地合回1个数组
怎么将两个数组合成一个有序数组 1、比较两个数组的首项大小将比较小的值保存到一个临时数组移动首项的位置即 2、重复第1步直到其中一个数组将所有的数字都保存到临时数组里面 3、将另一个数组剩下的值全都保存到临时数组里面
这是整个临时数组已经是有序的了再将它存回到原始数组对应的位置就可以了
void mergeArray(int l,int r,int mid){std::vectorunsigned int tempArray;int left l;int right mid1;while (left midright r) {while (left mid cVec[left] cVec[right]) {tempArray.push_back(cVec[left]);}while (right r cVec[left] cVec[right]) {tempArray.push_back(cVec[right]);}}while (left mid) {tempArray.push_back(cVec[left]);}while (right r) {tempArray.push_back(cVec[right]);}for (int i 0; i tempArray.size(); i) {cVec[l i] tempArray[i];}
}
void mergeSort(int l,int r) {if (l r) {return;}int mid (l r) 1;mergeSort(l, mid);mergeSort(mid 1, r);mergeArray(l,r,mid);}
