- #include<stdio.h>
- #include<stdlib.h>
- #include<time.h>
- #define NUMBERSIZE 100
- #define ERROR 0
- #define OK 1
- int DataGeneration(int *); //随机数组产生函数
- int PrintNumber(int *); //打印数组函数
- int NumberCopy(int *, int *);//数组值拷贝函数
- int InertSort(int*); //直接插入排序
- int BInsertSort(int *); //折半插入
- int BubSort(int *);
- int QuickSort(int *); //快速排序,以下是两个子函数
- int Qsort(int *, int, int, int*, int* );
- int Partition(int*, int, int, int*,int*);
- int SelectSort(int *); //选择排序
- int HeapSort(int *); //堆排序
- int HeapAdjust(int *,int , int*, int*);
- void main()
- {
- int number[NUMBERSIZE+1];
- if( !DataGeneration(number) ){
- printf("随机数组产生失败!");
- exit(ERROR);
- }
- printf("原始数据如下:\\n");
- PrintNumber( number );
- printf("**********下面进行排序**********\\n\\n");
- InertSort(number);
- BInsertSort(number);
- BubSort(number);
- QuickSort(number);
- SelectSort (number);
- HeapSort (number);
- system ("PAUSE");
- }
- int DataGeneration(int *number)
- {
- int i;
- srand((unsigned)time(NULL));
- for( i = 1; i <= NUMBERSIZE ; i++){
- number[i] = rand()%(1000-1); //产生0~1000之内的随机数
- }
- return OK;
- }
- int PrintNumber (int * number)
- {
- int i;
- for( i = 1; i <= NUMBERSIZE; i++){
- printf(" %4d ", number[i]);
- if( i%10 == 0)
- printf("\\n");
- }
- return OK ;
- }
- int NumberCopy(int *num1, int * num2 )
- {
- int i;
- for( i = 0; i <= NUMBERSIZE ; i++){
- num1[i] = num2[i];
- }
- return OK;
- }
- int InertSort(int *number)
- {
- int i, j, num[NUMBERSIZE +1];
- int comnum = 0, excnum = 0; //定义比较次数,交换次数
- NumberCopy(num,number);
- for( i = 2; i <= NUMBERSIZE ; i++){
- if(num[i]<num[i-1]){
- comnum++;
- num[0] = num[i];
- num[i] = num[i-1];
- excnum = excnum + 2;
- for(j = i-2; num[j] > num[0]; j--){
- comnum ++;
- num[j+1] = num[j];
- excnum ++;
- }
- num[j+1] = num[0];
- excnum ++;
- }
- }
- printf("************插入排序***********\\n");
- PrintNumber (num);
- printf("比较了 %d 次,交换了 %d 次\\n", comnum, excnum );
- return OK;
- }
- int BInsertSort (int * number)
- {
- int i, j, m, low, high,num[NUMBERSIZE+1];
- int comnum = 0, excnum = 0;
- NumberCopy (num,number);
- for( i = 2; i <= NUMBERSIZE ; i++){
- num[0] = num[i];
- excnum ++;
- low =1;
- high = i-1;
- while (low <= high ){
- m = (high + low)/2;
- if( num[m] > num[0] ){
- comnum ++;
- high = m-1;
- }
- else{
- comnum ++;
- low = m+1;
- }
- }
- for( j = i -1; j > high ; j--){
- num[j+1] = num[j];
- excnum ++;
- }
- num[j+1] = num[0];
- }
- printf("**********折半插入排序*********\\n");
- PrintNumber (num);
- printf("比较了 %d 次,交换了 %d 次\\n", comnum , excnum);
- return OK;
- }
- int BubSort(int *number)
- {
- int i, j, num[NUMBERSIZE +1];
- int comnum = 0, excnum = 0;
- NumberCopy (num,number);
- for( i = NUMBERSIZE ; i > 1 ; i--){
- for( j = 1; j < i; j++ ){
- if( num[j] > num[j+1]){
- num[0] = num[j+1];
- num[j+1] = num[j];
- num[j] = num[0];
- excnum = excnum + 3;
- }
- comnum ++;
- }
- }
- printf("**********冒泡排序**********\\n");
- PrintNumber (num);
- printf("比较了 %d 次,交换了 %d 次\\n", comnum , excnum );
- return OK;
- }
- int QuickSort(int *number)
- {
- int num[NUMBERSIZE +1];
- int comnum = 0, excnum = 0;
- NumberCopy (num, number);
- Qsort(num, 1, NUMBERSIZE, &comnum, &excnum );
- printf("**********快速排序**********\\n");
- PrintNumber (num);
- printf("\\n比较了 %d 次,交换了 %d 次\\n",comnum , excnum );
- return OK;
- }
- int Qsort(int *num, int low, int high, int *comp, int *excp)
- {
- int pivotloc;
- if(low < high ){
- //PrintNumber (num);
- pivotloc = Partition(num,low,high, comp, excp);
- Qsort(num, low, pivotloc-1,comp, excp);
- Qsort(num, pivotloc+1, high,comp, excp );
- }
- return OK;
- }
- int Partition(int *num, int low, int high, int *comp, int *excp)
- {
- num[0] = num[low];
- (*excp)++;
- while(low < high){
- while(low < high && num[high] >= num[0]){
- (*comp)++;
- high --;
- }
- num[low] = num[high];
- (*excp)++;
- //low++;
- while(low < high && num[low] <= num[0]){
- (*comp)++;
- low++;
- }
- num[high] = num[low];
- (*excp)++;
- //high--;
- }
- num[low] = num[0];
- return low;
- }
- int SelectSort(int *number)
- {
- int i, j, k, num[NUMBERSIZE +1];
- int comnum = 0, excnum = 0;
- NumberCopy (num, number);
- for(i = 1; i < NUMBERSIZE ; i++ ){
- k = i;
- for( j = i; j <= NUMBERSIZE; j++ ){
- if(num[j] < num[k])
- k = j;
- comnum ++;
- }
- if( i != k){
- num[0] = num[k];
- num[k] = num[i];
- num[i] = num[0];
- excnum = excnum + 3;
- }
- }
- printf("***********选择排序**********\\n");
- PrintNumber (num);
- printf("\\n比较了 %d 次,交换了 %d 次\\n",comnum, excnum );
- return OK;
- }
- int HeapSort(int *number)
- {
- int i,num[NUMBERSIZE +1];
- int comnum = 0, excnum = 0;
- NumberCopy(num, number);
- for( i =(int) (NUMBERSIZE/2); i > 0; i--){
- HeapAdjust(num,i,NUMBERSIZE, &comnum , &excnum);
- }
- for( i = NUMBERSIZE ; i > 1; i--){
- num[0] = num[i];
- num[i] = num[1];
- num[1] = num[0];
- excnum = excnum + 3;
- HeapAdjust(num, 1, i -1 , &comnum, &excnum );
- }
- printf("************堆排序***********\\n");
- PrintNumber (num);
- printf("\\n比较了 %d 次, 交换了 %d 次\\n", comnum ,excnum );
- return OK;
- }
- int HeapAdjust(int* num, int i,int m, int *comp, int *excp)
- {
- int j;
- num[0] = num[i];
- (*excp)++;
- for( j = i*2; j <= m ; j=j*2){
- if(j< m && num[j+1] > num[j])
- j++;
- (*comp)++;
- if( num[0] >= num[j]){
- (*comp)++;
- break;
- }
- (*comp)++;
- num[i] = num[j];
- (*excp)++;
- i = j;
- }
- num[i] = num[0];
- return OK;
- }
- //该片段来自于http://www.codesnippet.cn/detail/2511201514083.html
来源: http://www.codesnippet.cn/detail/2511201514083.html