做外贸生意是不是需要建网站,福州seo推广服务,外国人做外贸都会浏览哪些网站,企业网站的建设目的是什么排序算法汇总
常用十大排序算法_calm_G的博客-CSDN博客 以下动图参考 十大经典排序算法 Python 版实现#xff08;附动图演示#xff09; - 知乎
冒泡排序
排序过程如下图所示#xff1a; 比较相邻的元素。如果第一个比第二个大#xff0c;就交换他们两个。对每一对相邻… 排序算法汇总
常用十大排序算法_calm_G的博客-CSDN博客 以下动图参考 十大经典排序算法 Python 版实现附动图演示 - 知乎
冒泡排序
排序过程如下图所示 比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 // arr 需要排序的数组 length 数组长度
//注 int cnt sizeof(a) / sizeof(a[0]);获取数组长度
void BubbleSort(int arr[], int length)
{for (int i 0; i length; i){for (int j 0; j length - i - 1; j){if (arr[j] arr[j 1])swap(arr[j],arr[j1]);}}
}
选择排序
排序过程如下图所示 在未排序序列中找到最小大元素存放到排序序列的起始位置从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾以此类推直到所有元素均排序完毕时间负复杂度O(n^2)空间O1非稳定排序原地排序 void selectSort(vectorint nums) {int len nums.size();int minIndex 0;for (int i 0; i len; i) {minIndex i;for (int j i 1; j len; j) {if (nums[j] nums[minIndex]) minIndex j;}swap(nums[i], nums[minIndex]);}
}
插入排序
排序过程如下图所示 从第一个元素开始该元素可以认为已经被排序 取出下一个元素在已经排序的元素序列中从后向前扫描 如果该元素已排序大于新元素将该元素移到下一位置 重复步骤3直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~5 void insertionSort(vectorint a, int n) {//{ 9,1,5,6,2,3 }for (int i 1; i n; i) {if (a[i] a[i - 1]) { //若第i个元素大于i-1元素直接插入。小于的话移动有序表后插入int j i - 1;int x a[i]; //复制为哨兵即存储待排序元素//a[i] a[i - 1]; //先后移一个元素可以不要这一句跟循环里面的功能重复了while (j 0 x a[j]) { //查找在有序表的插入位置,还必须要保证j是0的 因为a[j]要合法a[j 1] a[j];j--; //元素后移}a[j 1] x; //插入到正确位置}}
}
快速排序 排序过程如下图所示 动图看起来有点复杂下面放一个分解图https://blog.csdn.net/qq_38082146/article/details/115453732
我们以[ 82507461 ]这组数字为例来进行演示
首先我们随机选择一个基准值虽然图中选择了随机元素但是一般上会以第一个元素为基准值 与其他元素依次比较大的放右边小的放左边 然后我们以同样的方式排左边的数据 继续排 0 和 1 由于只剩下一个数所以就不用排了现在的数组序列是下图这个样子 右边以同样的操作进行即可排序完成。 1、选取第一个数为基准 2、将比基准小的数交换到前面比基准大的数交换到后面 3、对左右区间重复第二步直到各区间只有一个数 void quickSort(vectorintnumbers, int low, int high) {// numbers {10,8,4,6,9,10,123,6,2,14,3,8,5};if (low high) return;int first low, last high, key numbers[low];cout low high key endl;for (int i 0; i numbers.size(); i) {cout numbers[i] ;}cout endl;while (first last) {//从后往前找比他小的放前面,从前往后找比他大的放在后面//以第一个数为基准必须先从后往前走再从前往后走while (first last numbers[last] key)last--;if (first last) numbers[first] numbers[last];while (first last numbers[first] key)first;if (first last) numbers[last--] numbers[first];}numbers[first] key;cout the index first value key endl;quickSort(numbers, low, first - 1);quickSort(numbers, first 1, high);
}希尔排序 排序过程如下图所示 希尔排序是插入排序的一种变种。无论是插入排序还是冒泡排序如果数组的最大值刚好是在第一位要将它挪到正确的位置就需要 n - 1 次移动。
也就是说原数组的一个元素如果距离它正确的位置很远的话则需要与相邻元素交换很多次才能到达正确的位置这样是相对比较花时间了。
希尔排序就是为了加快速度简单地改进了插入排序交换不相邻的元素以对数组的局部进行排序。
希尔排序的思想是采用插入排序的方法先让数组中任意间隔为 h 的元素有序刚开始 h 的大小可以是 h n / 2,接着让 h n / 4让 h 一直缩小当 h 1 时也就是此时数组中任意间隔为1的元素有序此时的数组就是有序的了。 void shellSortCore(vectorint nums, int gap, int i) {int inserted nums[i];int j;// 插入的时候按组进行插入for (j i - gap; j 0 inserted nums[j]; j - gap) {nums[j gap] nums[j];}nums[j gap] inserted;
}void shellSort(vectorint nums) {int len nums.size();//进行分组最开始的时候gap为数组长度一半for (int gap len / 2; gap 0; gap / 2) {//对各个分组进行插入分组for (int i gap; i len; i) {//将nums[i]插入到所在分组正确的位置上shellSortCore(nums,gap,i);}}}
归并排序 排序过程如下图所示 1、把长度为n的输入序列分成两个长度为n/2的子序列 2、对这两个子序列分别采用归并排序 3、 将两个排序好的子序列合并成一个最终的排序序列。 void mergeSortCore(vectorint data, vectorint dataTemp, int low, int high) {if (low high) return;int len high - low, mid low len / 2;int start1 low, end1 mid, start2 mid 1, end2 high;mergeSortCore(data, dataTemp, start1, end1);mergeSortCore(data, dataTemp, start2, end2);int index low;while (start1 end1 start2 end2) {dataTemp[index] data[start1] data[start2] ? data[start1] : data[start2];}while (start1 end1) {dataTemp[index] data[start1];}while (start2 end2) {dataTemp[index] data[start2];}for (index low; index high; index) {data[index] dataTemp[index];}
}void mergeSort(vectorint data) {int len data.size();vectorint dataTemp(len, 0);mergeSortCore(data, dataTemp, 0, len - 1);
}
堆排序
分为创建堆和堆排序两个部分
创建堆这里假定是大根堆时要保证每个父节点的值比左右子节点的值大
当每次堆排序完成后最顶端的即是当前堆的最大值随后可以将堆的最大值与堆的倒数第一个元素互换因为此时当前最大值已经完成排序将其赶出堆内堆的size减1剩下的元素进行堆重构。
堆重构的过程就是维持堆每个父节点的值大于左右子节点值的过程
#include iostream
#include algorithm
#include vectorusing namespace std;//i位置的数向上调整大根堆
void heapInsert(vectorint arr, int i)
{while (arr[i] arr[(i - 1) / 2]) //子节点比父节点大{swap(arr[i], arr[(i - 1) / 2]);i (i - 1) / 2;}}//i位置的数发生了变化又想维持住大根堆的结构
void heapify(vectorint arr, int i, int size)
{int l 2 * i 1; //左孩子while (l size){int best l 1 size arr[l 1] arr[l] ? l 1 : l;best arr[best] arr[i] ? best : i;if (best i)break;swap(arr[i], arr[best]);i best;l 2 * i 1;}}//从顶到底建立大根堆
//依次弹出堆内的最大值并重新排好序
void heapSort(vectorint arr)
{int size arr.size();for (int i 0; i size; i) //建立大根堆{heapInsert(arr, i);}while (size 1){swap(arr[0], arr[size - 1]); size--;cout arr[size] endl;heapify(arr, 0, size);}
}int main()
{vectorint arr { 3,2,1,5,6,4 };heapSort(arr);
}计数排序
计数排序用于元素大小范围有限的数值排序。
如果 k待排数组的最大值 过大则会引起较大的空间复杂度一般是用来排序 0 到 100 之间的数字的最好的算法但是它不适合按字母顺序排序人名。
统计小于等于该元素值的元素的个数i于是该元素就放在目标数组的索引i位i≥0 找出待排序的数组中最大和最小的元素统计数组中每个值为 i 的元素出现的次数存入数组 C 的第 i 项对所有的计数累加从 C 中的第一个元素开始每一项和前一项相加向填充目标数组将每个元素 i 放在新数组的第 C[i] 项每放一个元素就将 C[i] 减去 1 #include iostream
#include vector
#include algorithmusing namespace std;// 计数排序
void CountSort(vectorint vecRaw, vectorint vecObj)
{// 确保待排序容器非空if (vecRaw.size() 0)return;// 使用 vecRaw 的最大值 1 作为计数容器 countVec 的大小int vecCountLength (*max_element(begin(vecRaw), end(vecRaw))) 1;vectorint vecCount(vecCountLength, 0);// 统计每个键值出现的次数for (int i 0; i vecRaw.size(); i)vecCount[vecRaw[i]];// 后面的键值出现的位置为前面所有键值出现的次数之和for (int i 1; i vecCountLength; i)vecCount[i] vecCount[i - 1];// 将键值放到目标位置for (int i vecRaw.size(); i 0; i--) // 此处逆序是为了保持相同键值的稳定性vecObj[--vecCount[vecRaw[i - 1]]] vecRaw[i - 1];
}int main()
{vectorint vecRaw { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 };vectorint vecObj(vecRaw.size(), 0);CountSort(vecRaw, vecObj);for (int i 0; i vecObj.size(); i)cout vecObj[i] ;cout endl;return 0;
}
桶排序 排序过程如下图所示 设置一个定量的数组当作空桶子。寻访序列并且把项目一个一个放到对应的桶子去。对每个不是空的桶子进行排序。从不是空的桶子里把项目再放回原来的序列中。 #includestdio.h
int main() {int book[1001],i,j,t;//初始化桶数组for(i0;i1000;i) {book[i] 0;}//输入一个数n表示接下来有n个数scanf(%d,n);for(i 1;in;i) {//把每一个数读到变量中去scanf(%d,t);//计数 book[t];}//从大到小输出for(i 1000;i0;i--) {for(j1;jbook[i];j) {printf(%d,i);}}getchar();getchar();//getchar()用来暂停程序以便查看程序输出的内容//也可以用system(pause);来代替return 0;
}基数排序 取得数组中的最大数并取得位数arr为原始数组从最低位开始取每个位组成radix数组对radix进行计数排序利用计数排序适用于小范围数的特点 int maxbit(int data[], int n) //辅助函数求数据的最大位数
{int maxData data[0]; /// 最大数/// 先求出最大数再求其位数这样有原先依次每个数判断其位数稍微优化点。for (int i 1; i n; i){if (maxData data[i])maxData data[i];}int d 1;int p 10;while (maxData p){//p * 10; // Maybe overflowmaxData / 10;d;}return d;
}
void radixsort(int data[], int n) //基数排序
{int d maxbit(data, n);int *tmp new int[n];int *count new int[10]; //计数器int i, j, k;int radix 1;for(i 1; i d; i) //进行d次排序{for(j 0; j 10; j)count[j] 0; //每次分配前清空计数器for(j 0; j n; j){k (data[j] / radix) % 10; //统计每个桶中的记录数count[k];}for(j 1; j 10; j)count[j] count[j - 1] count[j]; //将tmp中的位置依次分配给每个桶for(j n - 1; j 0; j--) //将所有桶中记录依次收集到tmp中{k (data[j] / radix) % 10;tmp[count[k] - 1] data[j];count[k]--;}for(j 0; j n; j) //将临时数组的内容复制到data中data[j] tmp[j];radix radix * 10;}delete []tmp;delete []count;
}
