c++常见的几种排序算法总结 |
您所在的位置：网站首页 › c各种排序的方法实现 › c++常见的几种排序算法总结 |
c++常见的几种排序算法总结
|
常见的几种排序:冒泡排序、鸡尾酒排序、直接插入排序、折半插入排序、快速排序、桶排序、鸽巢排序、选择排序、奇偶排序、计数排序。 #include "stdafx.h" #include #include #include using namespace std; void swap(int &a,int &b) { int temp = a; a = b; b = temp; } //快速排序 //通过一趟扫描将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小, //然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列 void QuickSort(int a[],int low,int high) { if(low >= high) return; int i = low; int j = high; int key = a[i]; while( i < j )//key自动覆盖数组的第一个数据 { //从右向左搜索,直到搜索到的数大于等于开始记录的数,交换其位置 while(i= key) j--; if(i= 0 && a[j-1] >temp;j--) { a[j] = a[j-1]; a[j-1] = temp; } } } } //折半插入排序(二分插入排序) //在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right， //然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。 void BinaryInsertionSort(int a[],int n) { int i,j,left,right,middle,num; for(i = 1;i= left;j--) a[j] = a[j-1]; a[left] = num;//右移后left位置上为空,把num放置left位置 } } //桶排序 1,桶排序是稳定的 2,桶排序是常见排序里最快的一种,比快排还要快…大多数情况下 3,桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法 void BucketSort(int a[],int n) { int maxVal = a[0]; //假设最大为arr[0] for(int x = 1; x < n; x++) //遍历比较，找到大的就赋值给maxVal { if(a[x] > maxVal) maxVal = a[x]; } int tmpArrLen = maxVal + 1; int *tmpArr = new int[tmpArrLen]; //获得空桶大小 int i, j; for( i = 0; i < tmpArrLen; i++) //空桶初始化 tmpArr[i] = 0; for(i = 0; i < n; i++) //寻访序列，并且把项目一个一个放到对应的桶子去。 tmpArr[ a[i] ]++; for(i = 0, j = 0; i < tmpArrLen; i++) { while( tmpArr[ i ] != 0) //对每个不是空的桶子进行排序。 { a[j ] = i; //从不是空的桶子里把项目再放回原来的序列中。i为索引,数组的索引位置就表示值 j++; tmpArr[i]--; } } } //鸽巢排序 --- 是一种时间复杂度为(Θ(n))且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法. 但它只有在差值（或者可被映射在差值）很小的范围内的数值排序的情况下实用 //原理类似桶排序,同样需要一个很大的鸽巢[桶排序里管这个叫桶,名字无所谓了] //鸽巢其实就是数组啦,数组的索引位置就表示值,该索引位置的值表示出现次数,如果全部为1次或0次那就是桶排序 void PogeonSort(int a[],int n) { int max = getMaxValue(a,n); int *count = (int*)malloc(sizeof(int) *(max+1)); int i,x,y; for(i = 0;i |
【本文地址】