Day3 简单选择&插入&计数&桶排序
//桶排序void BucketSort(int a[], int num) {int max = maxofArray(a, num);//元素最大值int Bnum = 0;//桶的数量int i, j, b, k;while (max > 0) {Bnum++;max -= 10;} //桶的个数//int Buck[Maxsize][Maxsize];//用二维数组来表示桶中的元素int(*Buck)[Maxsize] = new int[Maxsize][Maxsize];//动态分配二维数组防止堆栈溢出//在需要用到多个数组时，不妨考虑用二维数组来实现for (i = 0; i <= Bnum; i++)Buck[i][0] = 0;//每个桶的第一个元素表示该桶中的元素数量int t;for (i = 1; i <= num; i++) {//将元素放在桶里b = a[i] / 10 + 1;t = Buck[b][0] + 1;Buck[b][t] = a[i];//Buck[b][0]++;}for (i = 1; i <= Bnum; i++)SelectSort(Buck[i], Buck[i][0]);//对每个桶里的元素进行插入排序k = 1;for (i = 1; i <= Bnum; i++)for (j = 1; j <= Buck[i][0]; j++, k++)a[k] = Buck[i][j];for(i=0;i<Maxsize;++i)free(Buck[i]);// cout<<Bnum;}
-
在运用桶排序的过程中，由于本代码里运用了每个桶的第一个元素作为桶中元素计数，因此在选择其他排序的过程中，应避免对该元素修改。 -
在设置桶的二维数组时，为了避免数组过大造成堆栈溢出，可以采用动态分配的方式创建二维数组，同时也要记得释放掉内存空间。
int (*A)[maxsize]=new int [maxsize][maxsize];for(i=0;i<Maxsize;++i)free(A[i]);
简单选择排序：
//简单选择排序void SelectSort(int a[], int num) {int i, j;int min;int temp;for (i = 1; i <= num; i++) {min = i;for (j = i + 1; j <= num; j++) {if (a[min] > a[j])min = j;}// a[i]=a[i]+a[min];// a[min]=a[i]-a[min];// a[i]=a[i]-a[min];//这种交换手法，在i和min相同时会失效temp= a[min];a[min] = a[i];a[i] = temp;}}
插入排序
//插入排序void InsertSort(int a[], int num) {int i, j, k;for (i = 1; i <= num; i++) {a[0] = a[i];for (j = i - 1; j > 0 && a[j] > a[0]; j--) {}for (k = i - 1; k > j; k--)a[k + 1] = a[k];a[k + 1] = a[0];}}
计数排序
//计数排序void CountSort(int a[], int num) {int max = maxofArray(a, num);int i, j;int count[Maxsize] = { 0 };for (i = 1; i <= num; i++) {count[a[i] + 500]++;//避免由于待排序数组中的元素为负数从而排序失败}for (j = 1, i = 0; i <= max + 500; i++) {while ((count[i]--) > 0) a[j++] = i - 500;}}
在遇到使用数组下标的场景中，可以通过增加一个偏移量来达到满足负数使用的功能。
main函数
int main() {int num;cin >> num;int* a = new int[10];for (int i = 1; i <= num; i++)cin >> a[i];SelectSort(a,num);print(a,num);InsertSort(a,num);print(a,num);CountSort(a, num);print(a, num);BucketSort(a, num);print(a, num);return 0;}
maxofArray函数和printf函数
void print(int a[], int num) {for (int i = 1; i <= num; i++)cout << a[i] << ' ';cout << endl;}//求元素最大值int maxofArray(int a[], int num) {int max = a[1];int i;for (i = 1; i <= num; i++) {if (max < a[i]) max = a[i];}return max;}