/* *@description:冒泡排序算法实现 *@author lintel */ void BubbleSort(ElemType A[], int n) {//冒泡将A中元素升序排 for (int i=0; i<n-1; ++i){ int flag = 0;//本趟交换标识 for (int j=n-1; j>i; --j){//一趟冒泡 if (A[j].key < A[j-1].key){ swap(A[j], A[j-1]); flag = 1; } } if (flag == 0)//本趟冒泡没有发生交换，表已有序 return ; } } /* *@description:快排算法实现 *快排基于分治法，取中枢值作划分，一趟partition后中枢值位置定 *表中元素被中枢值一分为二，递归划分两子表 *@author lintel */ void QuickSort(ElemType A[], int low, int high) { if (low < high){ int pivotpos = Partition(A, low, high);//划分 QuickSort(A, low, pivotpos-1); QuickSort(A, pivotpos+1, high); } } //快排算法关键在划分操作，以下给出两种划分 int Partition1(ElemType A[], int low, int high) { ElemType pivot = A[low]; while (low<high && A[high]>=pivot) --high; A[low] = A[high]; while (low<high && A[low]<pivot) ++low; A[high] = A[low]; A[low] = pivor; return low; } int Partition2(ElemType A[], int low, int high) { ElemType pivot = A[low]; int i = low; for (int j=low+1; j<=high; ++j){ if (A[j].key < pivot){ swap(A[++i], A[j]); } } swap(A[i], A[low]); return i; } /* *@description:插入排序算法实现：直接插，折半插（仅减少比较次数），希尔排 *@author lintel已排后挪，依次插入A[2]~A[n] */ void InsertSort(ElemType A[], int n) {//直接插排A[0]作复制哨兵 for (int i=2; i<=n; ++i) if (A[i].key < A[i-1].key){ A[0] = A[i]; int j = i-1; for (; A[0].key<A[j].key; --j) A[j+1] = A[j];//后移 A[j+1] = A[0]; }//if } void InsertSort(ElemType A[], int n) {//希尔排 分组插排。希尔增量序列每次减半 //和直接插排相比1，前后记录位置的增量是d不是1；2，A[0]是暂存单元 for (int d = len/2; len>=1; len /= 2)//步长变化 for (int i=d+1; i<=n; ++i) if(A[i].key < A[i-d].key){ A[0] = A[i]; int j=i-d; for (; j>0&&A[0]<A[j].key; j -= d) A[j+d] = A[j];//后移 A[j+d] = A[0]; }//if } /* *@description:选择排序算法实现 *第i趟选择最小元素后和第i元交换 *@author lintel */ void SelectSort(ElemType A[], int n) { for (i=0; i<n-1; ++i){ int min = i;//记录最小元位置 for (int j=i+1; j<n; ++j) if (A[j] < A[min]) min = j;//更新最小元位置 if (i!=min) swap(A[i], A[min]); } } //堆排见：。。。。。。。。。。 /* *@description:归并排序算法实现 归并指将两个或两个以上的有序表组合成一个新的有序表。 归并排递归基于分治法，一趟归并为O(n)，共需logn趟 *@author lintel */ void Merge(ElemType A[], int low, int mid, int high) {//Merge()将前后两个有序表归并为一个有序表 ElemType *temp = (ElemType*)malloc((n+1)*sizeof(ElemType)); for (int i=low; i<=high; ++i) temp[i] = A[i];//将待合并表复制到temp中 for (int i=low,j=mid+1,k=i; i<=mid && j<=high; ++k){ if (temp[i]<=temp[j]) A[k] = temp[i++]; else A[k] = temp[j++];//将两段中较小值赋值到A中 }//for while (i<=mid) A[k++] = temp[i++]; while (j<=high) A[k++] = temp[j++];//两while执行1个 } //递归形式的2-路归并 void MergeSort(ElemType A[], int low, int high) { if (low<high){ int mid = (low+high)/2; MergeSort(A, low, mid); MergeSort(A, mid+1, high); Merge(A, low, mid, high); }//if } /* *@description:基数排序算法实现 基数排序不是基于比较，而是根据构成关键字的d个分量的值 借助“分配”和‘“收集”两操作完成单分量的排序 分为最低位优先（LSD）和最高位优先（MSD） *@author lintel */ //r为基数，d为分量元数 void RadixSort(int A[], int n) { int d = getMaxBit(A);//获取待排数的最大位数 for (int i=1; i<=d; ++i){ vector<queue<int> > vecq(10,queue<int>); distribute(A, i, vecq);//分配 collecte(A, vecq);//收集 } } void distribute(int A[], int i, vector<queue<int> vecq) { //第i趟分配 vector<queue<int> > for (int j=0; j<n; ++j){ vecq[getIBit(A[j], i)].push(A[j]); } } void collecte(int A[], vector<queue<int> > vecq) { int k=0; for (int i=0; i<10; ++i){ while (!vecq[i].empty()){ A[k++] = vecq[i].front(); vecq[i].pop(); } } } /* 桶排序算法参考http://hxraid.iteye.com/blog/647759 桶排序1关键字桶映射函数f(k)，最好将N数据平分到M桶中，尽量增大桶数M 2各桶内快排 */
