//冒泡排序voidbubleSort(intdata[],intn);
//快速排序voidquickSort(intdata[],intlow,inthigh);intfindPos(intdata[],intlow,inthigh);
//插入排序voidbInsertSort(intdata[],intn);
//希尔排序voidshellSort(intdata[],intn);
//选择排序voidselectSort(intdata[],intn);//堆排序voidheapSort(intdata[],intn);voidswap(intdata[],inti,intj);voidheapAdjust(intdata[],inti,intn);
//归并排序voidmergeSort(intdata[],intfirst,intlast);voidmerge(intdata[],intlow,intmid,inthigh);
//基数排序voidradixSort(intdata[],intn);intgetNumPos(intnum,intpos);intmain() {intdata[10] = {43,65,4,23,6,98,2,65,7,79};inti;printf("原先数组:");for(i=0;i<10;i++) {printf("%d ", data[i]); }printf("\n");
/*printf("冒泡排序:");
bubleSort(data, 10);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("快速排序:");
quickSort(data, 0, 9);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("插入排序:");
bInsertSort(data,10);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("希尔排序:");
shellSort(data, 10);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("选择排序:");
selectSort(data, 10);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");
int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79};
int i;
printf("原先数组:");
int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79};
for(i=1;i<11;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf(" 堆排序:");
heapSort(data, 10);
for(i=1;i<11;i++) {
printf("%d ", data[i]);
}
printf("\n");
printf("归并排序:");
mergeSort(data, 0, 9);
for(i=0;i<10;i++) {
printf("%d ", data[i]);
}
printf("\n");*/printf("基数排序:"); radixSort(data,10);for(i=0;i<10;i++) {printf("%d ", data[i]); }printf("\n");return0;}/*--------------------冒泡排序---------------------*/voidbubleSort(intdata[],intn) {inti,j,temp;//两个for循环，每次取出一个元素跟数组的其他元素比较//将最大的元素排到最后。for(j=0;jdata[i+1]) { temp = data[i]; data[i] = data[i+1]; data[i+1] = temp; } } } }/*--------------------快速排序---------------------*/intfindPos(intdata[],intlow,inthigh) {//将大于t的元素赶到t的左边，大于t的元素赶到t的右边intt = data[low];while(low < high) {while(low < high && data[high] >= t) { high--; } data[low] = data[high];while(low < high && data[low] <=t) { low++; } data[high] = data[low]; } data[low] = t;//返回此时t在数组中的位置returnlow;}//在数组中找一个元素，对大于该元素和小于该元素的两个数组进行再排序//再对两个数组分为4个数组，再排序，直到最后每组只剩下一个元素为止voidquickSort(intdata[],intlow,inthigh) {if(low > high) {return; }intpos = findPos(data, low, high); quickSort(data, low, pos-1); quickSort(data, pos+1, high); }/*--------------------插入排序---------------------*/voidbInsertSort(intdata[],intn) {intlow,high,mid;inttemp,i,j;for(i=1;i temp) { high = mid-1; }else{ low = mid+1; } }intj = i;//让data与已经排序好的数组的各个元素比较，小的放前面while((j > low) && data[j-1] > temp) { data[j] = data[j-1]; --j; } data[low] = temp; }}/*--------------------希尔排序---------------------*/voidshellSort(int* data,intn) {intstep,i,j,key;//将数组按照step分组，不断二分到每组只剩下一个元素for(step=n/2;step>0;step/=2) {//将每组中的元素排序，小的在前for(i=step;i=0&& key0;i--) { heapAdjust(data, i, n); }//循环每个结点，将大的结点交换到堆顶for(i=n;i>1;i--) { swap(data,1, i);//每次交换完都要调整二叉树，将剩下的最大的结点交换到堆顶heapAdjust(data,1, i-1); }}//交换函数voidswap(intdata[],inti,intj) {inttemp; temp = data[i]; data[i] = data[j]; data[j] = temp;}voidheapAdjust(intdata[],inti,intn) {intj, temp;//假设第一个结点的元素是最大的temp = data[i];//i结点：2*i是i结点的左结点，2*i+1是i结点的右结点//把结点元素大的交换到前面for(j=2*i;j<=n;j*=2) {if(j < n && data[j] < data[j+1]) { j++; }if(temp >= data[j]) {break; } data[i] = data[j]; i = j; } data[i] = temp;}/*--------------------归并排序---------------------*/voidmergeSort(intdata[],intfirst,intlast) {intmid =0;//将数组不停的二分分组再组合，直到每组只剩一个元素if(first < last) { mid = (first+last)/2; mergeSort(data, first, mid); mergeSort(data, mid+1, last); merge(data, first, mid, last); }return;}voidmerge(intdata[],intlow,intmid,inthigh) {inti, k;//定义一个临时数组存放传进来的无序数组排好序之后的数组int*temp = (int*)malloc((high-low+1)*sizeof(int));//将无序数组分成两个序列intleft_low = low;intleft_high = mid;intright_low = mid+1;intright_high = high;//将两个序列比较排序，小的排前for(k=0;left_low<=left_high && right_low<=right_high;k++) {if(data[left_low]<=data[right_low]) { temp[k] = data[left_low++]; }else{ temp[k] = data[right_low++]; } }//左序列如果有剩下元素未排序，加到临时数组的末尾if(left_low <= left_high) {for(i=left_low;i<=left_high;i++) { temp[k++] = data[i]; } }//右序列如果有剩下元素未排序，加到临时数组的末尾if(right_low <= right_high) {for(i=right_low;i<=right_high;i++) { temp[k++] = data[i]; } }//将排好序的小分组转移到原数组中for(i=0;i
网友评论