注：在测试堆排序时，堆排序需要设置堆顶元素位置为1，我这里采用直接在创建队列让第一个作废（即，第一个输入-1，接下来再输入队列中的元素）
//简单选择排序 void SelectSort(int* a,int n) { int i,j; for(i = 0;i<n-1;i++) { int min = i; for(j = i+1;j<n;j++) { if(a[min]>a[j]) { min = j; } } int temp = a[i]; a[i] = a[min]; a[min] = temp; } } //直接插入排序 void InsertSort(int* a,int n) { int i,j; for(i = 1;i<n;i++) { int k = a[i]; for(j = i-1;j>=0;j--) { if(k<a[j]) { a[j+1]=a[j]; } else break; } a[j+1] = k; } } //冒泡排序 (这种冒泡是先选出最先的，换一种i，j值就是选出最大的） void BubbleSort(int* a,int n) { int i,j; for(i = 0;i<n;i++) { for(j = n-1;j>i;j--) { if(a[j]<a[j-1]) { int temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; } } } } //快速排序 int Partition(int* a,int low,int high)//序列划分 { int i = low; int j = high+1; do{ do{ i++; } while(a[i]<a[low]); do{ j--; }while(a[j]>a[low]); if(i<j) { int temp1 = a[i]; a[i] = a[j]; a[j] = temp1; } }while(i<j); int temp2 = a[low]; a[low] = a[j]; a[j] = temp2; return j; } void QuickSort(int* a,int low,int high)//快排 { int k; if(low<high) { k = Partition(a,low,high); QuickSort(a,low,k-1); QuickSort(a,k+1,high); } } //两路合并排序(递归实现） void Merge(int* a,int *temp,int low,int mid,int high) { int i,j,k; for(k = low;k<=high;k++) temp[k] = a[k]; for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++) { if(temp[i]<temp[j]) a[k] = temp[i++]; else a[k] = temp[j++]; } while(i<=mid) a[k++]=temp[i++]; while(j<=high) a[k++] = temp[j++]; } void MergeSort(int* a,int low,int high) { int* temp = (int *)malloc(sizeof(int)*(high-low+1)); if(low<high) { int mid = (low+high)/2; MergeSort(a,low,mid); MergeSort(a,mid+1,high); Merge(a,temp,low,mid,high); } } //堆排序(记住使用的是数组从1开始的元素，len = n-1） void AdjustDown(int* a,int k,int len) { int flag = a[k]; int i; for(i = 2*k;i<=len;i*=2) { if(i<len&&a[i]<a[i+1]) i++; if(flag>=a[i]) break; else{ a[k] = a[i]; k = i; } } a[k] = flag; } void BuildMaxHeap(int* a,int len) { int i; for(i=len/2;i>0;i--) AdjustDown(a,i,len); } void HeapSort(int* a,int len) { BuildMaxHeap(a,len); // for(i = len;i>1;i--) // { // Swap(a[i],a[1]);//输出栈顶元素，并与栈底元素交换 // AdjustDown(a,1,i-1);//对删除后的堆进行重新排列 // } } int main() { int n; printf("请输入数组长度："); scanf("%d",&n); int* a = (int*)malloc(sizeof(int)*n); int i; for(i = 0;i < n;i++) { scanf("%d",&a[i]); } SelectSort(a,n); printf("SelectSort:"); for(i = 0;i < n;i++) printf("%d ",a[i]); printf("\n"); InsertSort(a,n); printf("InsertSort:"); for(i = 0;i < n;i++) printf("%d ",a[i]); printf("\n"); BubbleSort(a,n); printf("BubbleSort:"); for(i = 0;i < n;i++) printf("%d ",a[i]); printf("\n"); QuickSort(a,0,n-1); printf("QuickkSort:"); for(i = 0;i < n;i++) printf("%d ",a[i]); printf("\n"); MergeSort(a,0,n-1); printf("MergeeSort:"); for(i = 0;i < n;i++) printf("%d ",a[i]); printf("\n"); HeapSort(a,n-1); printf("MergeeSort:"); for(i = 0;i < n;i++)//这里打印的是第一次建堆后的结果 printf("%d ",a[i]); printf("\n"); return 0; }