mySort.h

#ifndefMYSORT_H_INCLUDED#defineMYSORT_H_INCLUDED/*交换排序：冒泡排序，快速排序*/voidbubbleSort(intarr[],intarrLen);intslipForQuickSort(intarr[],intarrLeft,intarrRight);voidquickSort(intarr[],intarrLeft,intarrRight);/*选择排序：直接选择排序，堆排序*/voiddirectSelectSort(intarr[],intarrLen);voidheapAdjust(intarr[],intparent,intarrLen);voidheapSort(intarr[],intarrLen);/*插入排序：直接插入排序，希尔排序*/voiddirectInsertSort(intarr[],intarrLen);voidshellSort(intarr[],intarrLen);/*合并排序：归并排序*/voidmergeSort(intarr[],inttemparr[],intleft,intright);voidmerge(intarray[],inttemparray[],intleft,intmiddle,intright);#endif//MYSORT_H_INCLUDED

mySort.c

#include"mysort.h"#include"stdio.h"voidplayArr(intarr[],intlen){inti=0;for(i=0;i<len-1;i++){printf("%d\t",arr[i]);}printf("\n");return;}voidswapNum(int*a,int*b){inttmp;tmp=*a;*a=*b;*b=tmp;return;}/*冒泡排序是交换排序，O(N^2)*/voidbubbleSort(intarr[],intarrLen){inti;intj;for(i=0;i<arrLen;i++){for(j=arrLen-1;j>i;j--){if(arr[j]<arr[i]){swapNum(&arr[i],&arr[j]);}}}return;}/*快速排序是交换排序，O(N^2),平均复杂度：N(logN)intarrLeft,intarrRight是数组下标*/voidquickSort(intarr[],intarrLeft,intarrRight){inti;if(arrLeft<arrRight){i=slipForQuickSort(arr,arrLeft,arrRight);quickSort(arr,arrLeft,i-1);quickSort(arr,i+1,arrRight);}return;}intslipForQuickSort(intarr[],intarrLeft,intarrRight){intbaseNum=arr[arrLeft];while(arrLeft<arrRight){//从右到左查询比baseNum小的数字while((arrLeft<arrRight)&&(arr[arrRight]>=baseNum)){arrRight--;}arr[arrLeft]=arr[arrRight];//在右边找到之后将比baseNum小的数字移动到数组的左边//从左到右查询比baseNum大的数字while((arrLeft<arrRight)&&(arr[arrLeft]<=baseNum)){arrLeft++;}arr[arrRight]=arr[arrLeft];//在左边找到之后将比baseNum大的数字移动到数组的右边}arr[arrLeft]=baseNum;//把基准数字放到arrLeft位置上，此时arrLeft左边都是比baseNum小的数字，右边都是比它大的数字returnarrLeft;}/*直接插入排序：O(n^2)*/voiddirectSelectSort(intarr[],intarrLen){inti;intj;intbaseNum;for(i=0;i<arrLen;i++){baseNum=i;//在i的右侧找到最下的一个数字，记录下标for(j=i+1;j<arrLen;j++){if(arr[j]<arr[baseNum]){baseNum=j;}}//将最小的数字移动到当前位置swapNum(&arr[i],&arr[baseNum]);}return;}/*堆排序：O(NlogN)*/voidheapSort(intarr[],intarrLen){inti;//二叉树父节点的下标为i时，左右孩子接到为2i+1，2i+2。for(i=arrLen/2-1;i>=0;i--){heapAdjust(arr,i,arrLen);}for(i=arrLen-1;i>=0/*arrLen-top*/;i--){swapNum(&arr[0],&arr[i]);//将大数放到数组最右边heapAdjust(arr,0,i-1);//将剩余的数字从新构建大根堆}return;}voidheapAdjust(intarr[],intparent,intarrLen){inttmp;intleftChild;tmp=arr[parent];//取出父节点的值并保持leftChild=2*parent+1;//找到父节点的左孩子while(leftChild<arrLen){if((leftChild+1<arrLen)&&(arr[leftChild]<arr[leftChild+1])){leftChild++;}if(tmp>=arr[leftChild]){break;}arr[parent]=arr[leftChild];parent=leftChild;leftChild=2*parent+1;}arr[parent]=tmp;return;}/*直接插入排序：O(N^2)将N-M个无序数字，插入前面M个有序数字中*/voiddirectInsertSort(intarr[],intarrLen){inti;intj;inttmp;for(i=1;i<arrLen;i++){tmp=arr[i];for(j=i-1;((j>=0)&&(arr[j]>tmp));j--){arr[j+1]=arr[j];}arr[j+1]=tmp;}}/*希尔排序：平均为：O(N^3/2)最坏：O(N^2)*/voidshellSort(intarr[],intarrLen){inti;intj;inttmp;intaddNum;addNum=arrLen/2;//增量while(addNum>=1){for(i=addNum;i<arrLen;i++){tmp=arr[i];for(j=i-addNum;((j>=0)&&(tmp<arr[j]));j=j-addNum){arr[j+addNum]=arr[j];}arr[j+addNum]=tmp;}addNum/=2;}return;}/*归并排序：时间：O(NlogN)空间：O(N)intleft,intright为数组下标*/voidmergeSort(intarr[],inttemparr[],intleft,intright){intmiddle;if(left<right){middle=(left+right)/2;//拆分位置mergeSort(arr,temparr,left,middle);mergeSort(arr,temparr,middle+1,right);merge(arr,temparr,left,middle+1,right);}return;}voidmerge(intarray[],inttemparray[],intleft,intmiddle,intright){inti;//左指针尾intleftEnd=middle-1;//右指针头intrightStart=middle;//临时数组的下标inttempIndex=left;//数组合并后的length长度inttempLength=right-left+1;//先循环两个区间段都没有结束的情况while((left<=leftEnd)&&(rightStart<=right)){//如果发现有序列大，则将此数放入临时数组if(array[left]<array[rightStart])temparray[tempIndex++]=array[left++];elsetemparray[tempIndex++]=array[rightStart++];}//判断左序列是否结束while(left<=leftEnd)temparray[tempIndex++]=array[left++];//判断右序列是否结束while(rightStart<=right)temparray[tempIndex++]=array[rightStart++];//交换数据for(i=0;i<tempLength;i++){array[right]=temparray[right];right--;}return;}