#include <stdio.h>//说明：下面的所有排序，数组arr[n]按照默认：arr[0],arr[1],...,arr[n-1]存放数据，//不存在arr[0]不使用的情况。void bubble_sort(int arr[],int n){ int temp,i,j; for(j=0;j<n-1;j++) for(i=n-1;i>j;i--) { if(arr[i]<arr[i-1]) { temp=arr[i]; arr[i]=arr[i-1]; arr[i-1]=temp; } }}//improve the bubble_sort:void improve_bubble_sort(int arr[],int n){ int i,j,temp; bool exchange; for(i=0;i<n-1;i++) { exchange=false; for(j=n-1;j>i;j--){ if(arr[j]<arr[j-1]) { temp = arr[j]; arr[j]=arr[j-1]; arr[j-1]=temp; exchange=true; } } if(!exchange) return; }}//-------------quick sort ---------------//快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。//get the pivot's index.int Partition(int arr[],int low,int high){ int pivot = arr[low]; while(low<high){ while(low<high && arr[high]>=pivot) --high; arr[low]=arr[high]; while(low<high && arr[low]<=pivot)++low; arr[high]=arr[low]; } arr[low]=pivot; return low;}//quick sort by recursionvoid QuickSort(int arr[],int low,int high){ int pindex; if(low<high){ pindex=Partition(arr,low,high); QuickSort(arr,low,pindex-1); QuickSort(arr,pindex+1,high); } else return ;}//Insert sort bool ALessB(int a,int b){ if(a<=b)return true; else return false;}void DisplayArray(int arr[],int n){ int *p; for(p=arr;p<(arr+n);p++) printf("%d ",*p); printf("/n");}//Insert sort method：整个排序过程进行n-1趟插入，即先将序列中的第1个记录（下标为0）看成是一个有序的子序列，然后从第2个记录（下标为1）起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。void InsertSort(int arr[],int n){ int i,j,temp; for(i=1;i<n;++i){ if (ALessB(arr[i],arr[i-1])) { temp=arr[i];//把待插入的元素暂存起来。 //从i到0找到待插入元素的位置j，并同时把j以及j以后的元素(j<=i)依次后移，把位置j让出来。 for(j=i;j>0 && ALessB(temp,arr[j-1]);--j) arr[j]=arr[j-1]; arr[j]=temp;//把待插入的元素放到位置j上。 } }}//对insert sort 的改进，在查找待插入元素的位置时采用折半查找法。void InsertSortImprove(int arr[],int n){ int i,j,low,high,mid,temp; for(i=1;i<n;++i){ temp=arr[i];//把待插入的元素暂存起来。 low=0; high=i; while(low<high){//从i到0找到待插入元素的位置j mid=(low+high)/2; if(temp<=arr[mid]) high=mid-1; else low=mid+1; } for(j=i;j>high+1;--j)//把j以及j以后的元素(high+1<j<=i)依次后移，把位置j让出来。 arr[j]=arr[j-1]; arr[j]=temp; }}
//----------- shell sort-------------------//希尔排序的思想：先将整个待排序记录分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录//"基本有序"时,再对全体记录进行一次直接插入排序.void ShellInsertSort(int arr[],int n,int dk){ int i,j,temp; for(i=dk;i<n;++i){//前后记录位置的增量是dk. if(ALessB(arr[i],arr[i-dk])){ temp=arr[i]; for(j=i; j>=dk && ALessB(temp,arr[j-dk]);j-=dk) arr[j]=arr[j-dk]; arr[j]=temp; } }}void ShellSort(int arr[],int n,int dlt[],int t){ int k; for(k=0;k<t;++k) ShellInsertSort(arr,n,dlt[k]);}//---------------Heap sort-------------------//说明:在堆排序中,数组的下标从1开始.//把一个完全二叉树调整为一个大堆.//说明:堆是个完全二叉树,如果某节点的下标为i,则它的父节点下标为[i/2],它的左孩子节点为2i,右孩子节点为2i+1;//调整下标为begin大堆的过程://比较heap[begin]和它的孩子节点Max(heap[2*begin],heap[2*begin+1])//如果heap<Max(heap[2*begin],heap[2*begin+1])就和它的孩子节点替换,并接着把调整该孩子节点的孩子节点.止到调整为以heap[begin]为根节点的大堆.void HeapAjust(int *heap,int begin,int end){ int temp=heap[begin]; int finish=0; int j=2*begin; while (j<=end && finish==0) { if (j<end && heap[j]<heap[j+1]){ j++; } if (temp>=heap[j]){ finish =1; }else{ heap[j/2]=heap[j]; j=j*2; } } heap[j/2]=temp;}//首先逐步调整为一个大堆.void HeapSort(int *heap,int n){ for (int i = (n/2);i>=1;i--) { HeapAjust(heap,i,n); } int temp; for (i = n-1;i>=1;i--) { temp = heap[i+1]; heap[i+1] = heap[1]; heap[1] = temp; HeapAjust(heap,1,i);
printf("Sorting process:"); for (int j=1;j<=n;j++) { printf("%d ,",heap[j]); } printf("/n"); }}
