- 技术人生
- 内部排序
#include <stdlib.h> #include <stdio.h> #include <time.h> #define MAXSIZE 10 #define SUCCESS 1 #define FAILUE 0 #define LEN 5000 void swap(int *p1,int *p2);int BubbleSort(int sqlist[],int listLength);void InsertSort(int sqlist[],int listLength); int SelectSort(int sqlist[],int listLength);int QuickSort(int sqlist[],int listLength); /*快排主函数*/ void ShellSort(int sqlist[],int listLength);void adjust_heap(int sqlist[],int root,int listLength); void HeapSort(int sqlist[],int listLength); int PartSort(int sqlist[],int low,int high);void QSort(int sqlist[],int low,int high);void main() { int i; int num[MAXSIZE]; /* 待排序的数组 */ char ch; srand((unsigned)time(NULL)); /* 以当前时间作为随机数产生的种子 */ loop: system("cls"); for(i=0;i<MAXSIZE;i++) num[i]=rand(); /* 用随机数初始化排序数组 */ printf("生成的随机数如下:/n"); for(i=0;i<MAXSIZE;i++) printf("[%d]/t",num[i]); printf("/n/n"); printf("/t/t请输入您要选择的排序方式:/n/n"); printf("/t/t/t1.冒泡排序./n"); printf("/t/t/t2.直接插入排序./n"); printf("/t/t/t3.简单选择排序./n"); printf("/t/t/t4.快速排序./n"); printf("/t/t/t5.希尔排序./n"); printf("/t/t/t6.堆排序./n"); printf("/t/t/tx.退出./n"); printf("/n/t/t您的选择是:"); ch=getchar(); switch (ch) { case '1':BubbleSort(num,MAXSIZE); printf("冒泡排序后结果为:/n"); for(i=0;i<MAXSIZE;i++) printf("[%d]/t",num[i]);break; case '2':InsertSort(num,MAXSIZE); printf("直接插入排序后结果为:/n"); for(i=0;i<MAXSIZE;i++) printf("[%d]/t",num[i]);break; case '3':SelectSort(num,MAXSIZE); printf("简单选择排序后结果为:/n"); for(i=0;i<MAXSIZE;i++) printf("[%d]/t",num[i]);break; case '4':QuickSort(num,MAXSIZE); printf("快速排序后结果为:/n"); for(i=0;i<MAXSIZE;i++) printf("[%d]/t",num[i]);break; case '5':ShellSort(num,MAXSIZE); printf("希尔排序后结果为:/n"); for(i=0;i<MAXSIZE;i++) printf("[%d]/t",num[i]);break; case '6': printf("二叉树的内容:/n"); for(i = 1;i<MAXSIZE;i++) /*输出二叉树内容*/ printf("[%d]/t",num[i]); HeapSort(num,MAXSIZE-1); /*堆排序法*/ printf("/n/n输出排序结果:/n"); for(i = 1;i < MAXSIZE;i++) /*输出最后内容*/ printf("[%d]/t",num[i]); printf("/n");break; case 'x':exit(0);break; default: goto loop; } getchar(); printf("按任意键..."); getchar(); goto loop; }/*================================== 交换函数：交换两个地址中的值 ===================================*/ void swap(int *p1,int *p2) { int temp; temp = *p1; *p1 = *p2; *p2 = temp; } /*===========交换函数===============*/ /*================================== 冒泡排序： 首先将第一个记录的关键字和第二记录的关键字比较， 若为逆序，则将两个记录交换， 而后比较第二个记录和第三个记录的关键字， 依次类推，直到n-1个记录和第n个记录的关键字进行过比较为止 ===================================*/ int BubbleSort(int sqlist[],int listLength) { int i,j; if(listLength <= 0) { return FAILUE; } if(listLength == 1) { return SUCCESS; } else { for(i=0;i<listLength-1;i++) { for(j=0;j<listLength-i-1;j++) { if(sqlist[j]>sqlist[j+1]) swap(sqlist+j,sqlist+j+1); } } return SUCCESS; } } /*==========冒泡排序===============*/ /*================================== 直接插入排序： 将一个记录插入到已经排好序的有序表中， 得到一个新的记录数增1的有序表 ===================================*/ void InsertSort(int sqlist[],int listLength) { int i,j,k,temp; for(i=1;i<listLength;i++) { for(j=0;j<i;j++) { if(sqlist[i] < sqlist[j]) { temp = sqlist[i]; for(k = i-1;k>=j;k--) { sqlist[k+1] = sqlist[k]; } sqlist[j] = temp; } } } } /*===========直接插入排序========*//*================================== 简单选择排序： 首先将第一个记录的关键字和第二记录的关键字比较， 若为逆序，则将两个记录交换， 而后比较第一个记录和第三个记录的关键字， 依次类推，直到n-1个记录和第n个记录的关键字进行过比较为止 ===================================*/ int SelectSort(int sqlist[],int listLength) { int i,j; if(listLength <= 0) { return FAILUE; } if(listLength == 1) { return SUCCESS; } else { for(i=0;i<listLength-1;i++) { for(j=i;j<listLength;j++) { if(sqlist[i]>sqlist[j]) swap(sqlist+i,sqlist+j); } } return SUCCESS; } } /*==========简单选择排序===============*/ /*================================== 快速排序： 通过一趟排序将待排记录分割成独立的两部分， 其中一部分记录的关键字均比另一部分的小， 则可分别对这两部分记录继续进行排序，直到整个序列有序 ===================================*/ int QuickSort(int sqlist[],int listLength) /*快排主函数*/ { if(listLength <= 0) { return FAILUE; } if(listLength == 1) { return SUCCESS; } else { QSort(sqlist,0,listLength-1); return SUCCESS; } } void QSort(int sqlist[],int low,int high) /*快排副函数*/ { int pivotolic; if(low < high) { pivotolic = PartSort(sqlist,low,high); QSort(sqlist,low,pivotolic-1); /*对低端递归排序*/ QSort(sqlist,pivotolic+1,high); /*对高端递归排序*/ } } int PartSort(int sqlist[],int low,int high) { int pivotolic; pivotolic = sqlist[low]; /*通常将第一个元素作为枢轴*/ while(low<high) { while((low < high)&&(sqlist[high] >= pivotolic)) high--; /*high指针下移，*/ swap(sqlist+low,sqlist+high); /*直到找到比枢轴小的元素和枢轴交换*/ while((low < high)&&(sqlist[low] <= pivotolic)) low++; /*low指针上移，*/ swap(sqlist+low,sqlist+high); /*直到找到比枢轴大的元素和枢轴交换*/ } return low;} /*============快速排序=============*/ /*================================== 希尔排序===================================*/ void ShellSort(int sqlist[],int listLength) { int d=listLength; while(d>1) { int i,j,key; d=d/3+1; for(i=d;i<listLength;i++) { if(sqlist[i]<sqlist[i-d]) { key=sqlist[i]; j=i-d; while(j>=0&&key<sqlist[j]) { sqlist[j+d]=sqlist[j]; j-=d; } sqlist[j+d]=key; } } } } /*=============希尔排序==============*/ /*===================================<br />堆排序=====================================*/void adjust_heap(int sqlist[],int root,int listLength) { int done; /*是否可结束的变量*/ int j; int temp; j = 2 * root; /*子结点指针*/ temp = sqlist[root]; /*堆的根值*/ done = 0; /*建立变量*/ while(j <= listLength&&!done) /*主循环*/ { if(j < listLength) /*找最大的子结点*/ if(sqlist[j] < sqlist[j+1]) j++; /*下一结点*/ if(temp >= sqlist[j]) /*比较树根值*/ done = 1; /*结束*/ else { sqlist[j/2] = sqlist[j];/*父结点是目前结点*/ j = 2 * j; /*其子结点*/ } } sqlist[j/2] = temp; /*父结点为根值*/ } void HeapSort(int sqlist[],int listLength) { int i,j,temp; for(i = (listLength/2);i >= 1;i--) /*将二叉树转成堆*/ adjust_heap(sqlist,i,listLength); printf("/n堆中数据: "); for(j = 1; j < 10;j++) /*输出堆的内容*/ printf("[%d]",sqlist[j]); printf("/n"); /*换行*/ for(i = listLength - 1;i >= 1;i-- ) /*堆排序主循环*/ { temp = sqlist[i+1]; /*交换最后元素*/ sqlist[i+1] = sqlist[1]; sqlist[1] = temp; adjust_heap(sqlist,1,i); /*重建堆*/ printf("/n处理内容: "); for(j = 1;j < 10;j++) /*输出处理内容*/ printf("[%d]",sqlist[j]); } } /*===========堆排序==============*/
