企业网站打不开了,网站建设有几种工具,源码屋整站源码,自贡网站开发公司十种排序算法#xff1a;选择排序插入排序冒泡排序希尔排序快速排序的三种实现方法归并排序堆排序#xff08;大顶堆#xff09;计数排序基数排序#xff08;待实现#xff09;桶排序#xff08;待实现#xff09;#include bits/stdc.h
using namespace std;
vo…十种排序算法选择排序插入排序冒泡排序希尔排序快速排序的三种实现方法归并排序堆排序大顶堆计数排序基数排序待实现桶排序待实现#include bits/stdc.h
using namespace std;
void MergeSubQ(int a[], int n, int p, int middle, int r);
int Partition01(int a[], int p, int r);
int Partition02(int a[], int p, int r);
int* Partition03(int a[], int p, int r);
void InitializeHeap(int a[], int n, int i);//选择排序 O(n^2)
void SelectSort(int a[], int n){for(int i0; in-1; i){int mmina[i];int indexi;for(int ji1; jn; j){if(a[j]mmin){mmina[j];indexj;}}int temp a[i];a[i] a[index];a[index] temp;}
}//冒泡排序 On^2
void BubbleSort(int a[], int n){for(int i0; in-1; i)for(int j0; jn-i-1; j){if(a[j]a[j1]){int temp a[j];a[j] a[j1];a[j1] temp;}}}
//插入排序 O(n^2)
void InsertSort(int a[], int n){for(int i0; in; i){int num a[i];int index i-1;while(index-1 numa[index]){a[index1] a[index];index--;}a[index1] num;}
}//希尔排序 O(n^1.3)
void ShellSort(int a[], int n){for(int intervaln/2; interval1; interval/2){for(int iinterval; in; i){int num a[i];int index i-interval;while(index-1 numa[index]){a[indexinterval] a[index];index-interval;}a[indexinterval] num;}}
}//归并排序
void MergeSort(int a[], int n, int p, int r){if(pr){int middle p((r-p)1);//递归求解子问题MergeSort(a, n, p, middle);MergeSort(a, n, middle1, r);//合并MergeSubQ(a, n, p, middle, r);}
}
void MergeSubQ(int a[], int n, int p, int middle, int r){int help[n];//辅助数组for(int i0; in; i)help[i] a[i];int left p;//左指针int right middle1;//右指针int indexp;//当前要放入的位置while(leftmiddle rightr){if(help[left]help[right]){ //左指针指向的元素较小插入到a中a[index] help[left];left;}if(help[left]help[right]){ //右指针指向的元素较小插入到a中a[index] help[right];right;}}while(leftmiddle){ //左部分还有剩余直接插入a的末尾a[index]help[left];left;}
}
//快速排序
void QuickSort(int a[], int p, int r){if(pr){//找到主元应在的位置int* b Partition03(a, p, r);//递归求解主元的左部分和右部分QuickSort(a, p, b[0]-1);QuickSort(a, b[1]1, r);}
}
int Partition01(int a[], int p, int r){ //单向扫描法int point a[p]; //主元int scan p1; //扫描指针指向主元后int bigger r; //指向末尾while(scanbigger1){if(a[scan]point){ //扫描到了比主元大的元素int temp a[scan]; //与bigger指向的后面的元素进行交换a[scan] a[bigger];a[bigger] temp;bigger--;}else //小于等于主元情况scan;}a[p] a[bigger]; //将主元放到正确位置a[bigger] point;return bigger;
}
int Partition02(int a[], int p, int r){ //双指针int point a[p];int left p1; //从左扫描int right r; //从右扫描while(leftright){while(leftr a[left]point){left;}while(rightp1 a[right]point){right--;}if(leftright){int temp a[left];a[left] a[right];a[right] temp;}}a[p] a[right];a[right] point;return right;
}
int* Partition03(int a[], int p, int r){ //重复元素过多时int point a[p];int scan p1;int eq p1; //找重复int bigger r;int flagfalse;while(scanbigger){if(a[scan]point){if(flag){int temp a[scan];a[scan] a[eq];a[eq] temp;eq;}scan;}else if(a[scan]point){ //相当时将eq指向第一个相等的元素if(!flag){eq scan;flagtrue;}scan;}else{int temp a[scan];a[scan] a[bigger];a[bigger] temp;bigger--;}}if(!flag)eqbigger;a[p] a[bigger]; //bigger最后指向的是主元的位置a[bigger] point;int b[2] {eq, bigger}; //返回两个值return b;
}
//堆排序
void HeapSort(int a[], int n){//初始化堆for(int xn/2; x0; x--)InitializeHeap(a, n, x);//进行排序for(int xn-1; x0; x--){int temp a[0];a[0] a[x];a[x] temp;InitializeHeap(a, x, 0);}}
void InitializeHeap(int a[], int n, int i){int left 2*i1;int right 2*i2;int maxIndex left;if(leftn)return ;if(rightn){maxIndex left;}else{if(a[right]a[left])maxIndexright;}if(a[i]a[maxIndex])return ;int temp a[i];a[i] a[maxIndex];a[maxIndex] temp;InitializeHeap(a, n, maxIndex);
}
//基数排序
void BaseSort(int a[], int n){}//计数排序
void CountSort(int a[], int n){int mmax a[0];for(int i1; in; i){ //找出数组中的最大值if(a[i]mmax)mmax a[i];}int help[mmax1];memset(help, 0, sizeof(help));for(int i0; in; i){ //计数help[a[i]];}int index 0;for(int i1; immax1; i){ //根据数的个数排序while(help[i]0){a[index] i;help[i]--;}}
}//桶排序int main(){int a[10];srand((int)time(0));for(int i0; i10; i)a[i] rand() % 100;SelectSort(a, 10);BubbleSort(a, 10);InsertSort(a, 10);ShellSort(a, 10);MergeSort(a, 10, 0, 9);QuickSort(a, 0, 9);HeapSort(a, 10);CountSort(a, 10);for(int i0; i10; i)couta[i] ;return 0;
}
