排序算法。

快速排序：QuickSort

选标准值，将比标准值小的放在其左侧，将比标准值大的放在其右侧，左右两部分分别重复以上操作

1.挖坑填补法

拆东墙补西墙

先把第一个数拿出来用temp储存 然后从最后面遍历 找到比temp小的放到第一个位置 然后再从前面第二个开始遍历找比temp大的放在后面的空位上 重复操作 直到end和begin在一块 然后再在temp两边分别重复操作

 

#include<stdio.h>int Find(int arr[],int nBegin,int nEnd)
{int temp = arr[nBegin];while(nBegin < nEnd){//从后向前找比标准值小的while(nEnd > nBegin){if(arr[nEnd] < temp){arr[nBegin] = arr[nEnd];nBegin++;break;}nEnd--;			 }//从前往后找比标准值大的while(nBegin < nEnd){if(arr[nBegin] > temp){arr[nEnd] = arr[nBegin];nEnd--;break;}nBegin++;} }//标准值放入arr[nBegin] = temp;return nBegin; 
}void QuickSort(int arr[],int nBegin,int nEnd)
{if(arr == NULL || nBegin >= nEnd)return;//确定标准值最终位置int nStandard;nStandard = Find(arr,nBegin,nEnd);//将数据分成两部分 分别重复以上操作QuickSort(arr,nBegin,nStandard-1);QuickSort(arr,nStandard+1,nEnd);
}void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {2,4,7,1,5,14,89,13,2};QuickSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
}

 2.区间分割法

small指向begin-1 begin从前向后遍历 遇见比end小的 就交换small+1与begin 最终将小于10的全放在一边

若 a = i++; 则等价于 a=i;i=i+1; 而 a = ++i; 则等价于 i=i+1;a=i;

#include<stdio.h>int Find(int arr[],int nBegin,int nEnd)
{int nSmall = nBegin-1;for(nBegin;nBegin < nEnd;nBegin++){if(arr[nBegin] < arr[nEnd]){if(++nSmall != nBegin){arr[nSmall] = arr[nSmall]^arr[nBegin];arr[nBegin] = arr[nSmall]^arr[nBegin];arr[nSmall] = arr[nSmall]^arr[nBegin];}}}//将标准值放入if(++nSmall != nEnd){arr[nSmall] = arr[nSmall]^arr[nEnd];arr[nEnd] = arr[nSmall]^arr[nEnd];arr[nSmall] = arr[nSmall]^arr[nEnd];}return nSmall; 
}void QuickSort(int arr[],int nBegin,int nEnd)
{if(arr == NULL || nBegin >= nEnd)return;//确定标准值最终位置int nStandard;nStandard = Find(arr,nBegin,nEnd);//将数据分成两部分 分别重复以上操作QuickSort(arr,nBegin,nStandard-1);QuickSort(arr,nStandard+1,nEnd);
}void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {2,4,7,1,5,14,89,13,2};QuickSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
} 

MergeSort: 归并排序

将多个有序数组进行合并

 

#include<stdio.h>
#include<stdlib.h>void Merge(int arr[],int nBegin,int nEnd)
{int nBegin1 = nBegin;int nEnd1 = nBegin+(nEnd-nBegin)/2;int nBegin2 = nEnd1+1;int nEnd2 = nEnd;int *pTemp =NULL;pTemp = (int*)malloc(sizeof(int)*(nEnd-nBegin+1));int i=0;//遍历两个数组while(nBegin1 <= nEnd1 && nBegin2 <= nEnd2){if(arr[nBegin2] < arr[nBegin1]){pTemp[i++] = arr[nBegin2++];}else{pTemp[i++] = arr[nBegin1++];}}//将有剩余的数组元素放置while(nBegin1 <= nEnd1){pTemp[i++] = arr[nBegin1++];}while(nBegin2 <= nEnd2){pTemp[i++] = arr[nBegin2++];}//放回for(int i=0;i<nEnd-nBegin+1;i++){arr[nBegin+i] = pTemp[i];} free(pTemp);pTemp = NULL; 	
} void MergeSort(int arr[],int nBegin,int nEnd)
{if(arr == NULL || nBegin >= nEnd)return;//分割 int nMid = nBegin + (nEnd-nBegin)/2;MergeSort(arr,nBegin,nMid);MergeSort(arr,nMid+1,nEnd);//合并Merge(arr,nBegin,nEnd); 
} void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {2,4,7,1,5,14,89,13,2};MergeSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
} 

冒泡排序：BubbleSort

相邻两个元素进行大小比较，如果前一个比后一个大，则二者发生交换

第一横：8和6比 8比6大 交换 8和3比 8比3大 交换 8和12比 没12大 不动 12和1比 比12大交换 12和7比 比12大交换 12没15大 不动

第二横；6和3比。。。。。。。

#include<stdio.h>void BubbleSort(int arr[],int length)
{if(arr == NULL || length<=0)return;int i;int j;for(int i=0;i<length-1;i++)              //总排n-1回 {for(int j=0;j<length-i-1;j++)        //每次固定一个大的，然后俩俩比较再-1 {if(arr[j] > arr[j+1]){arr[j] = arr[j]^arr[j+1];arr[j+1] = arr[j]^arr[j+1];arr[j] = arr[j]^arr[j+1];}}}
}void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {2,4,7,1,5,14,89,13,2};BubbleSort(arr,sizeof(arr)/sizeof(arr[0]));Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
}

堆排序：HeapSort

先创建一个初始堆，从下到上调节父亲节点，使得每个父亲节点的值比两个孩子大，最大值就窜到最上面了，接着交换第一和最后，拿掉最后面的最大值，重复调整堆顶，拿出每个最大值

调整操作 先把两个孩子比一下取最大值跟爹比 要比爹大就交换 然后交换下来的爹也得看看他的儿子比不比他大

#include<stdio.h>#define LEFT (2*nRootID+1)
#define RIGHT (2*nRootID+2)void Adjust(int arr[],int length,int nRootID)
{int MAX;for(MAX = LEFT;MAX < length;MAX = LEFT){//两个孩子if(RIGHT < length){if(arr[MAX] < arr[RIGHT]){MAX = RIGHT;}}//比较大小if(arr[nRootID] < arr[MAX]){//交换arr[nRootID] = arr[nRootID]^arr[MAX];arr[MAX] = arr[nRootID]^arr[MAX];arr[nRootID] = arr[nRootID]^arr[MAX];nRootID = MAX;}else{break;} }
}void HeapSort(int arr[],int length)
{if(arr == NULL || length <=0)return;//建初始堆int i;for(i = length/2-1;i>=0;i--){Adjust(arr,length,i);}//排序for(i = length-1;i>0;i--){//交换arr[0] = arr[i]^arr[0];arr[i] = arr[i]^arr[0];arr[0] = arr[i]^arr[0];//调整堆顶Adjust(arr,i,0);} 
}void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {2,4,7,1,5,14,89,13,2};HeapSort(arr,sizeof(arr)/sizeof(arr[0]));Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
} 

桶排序：BucketSort

数据分组，各组之内进行排序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>typedef struct node
{int value;struct node *pNext;
}Bucket;void Sort(Bucket *pHead)
{if(pHead == NULL || pHead->pNext == NULL)return;Bucket *pi = NULL;Bucket *pj = NULL;pi = pHead;while(pi->pNext != NULL)          // n-1趟 {pj = pHead;                   // 每次遍历从表头开始  while(pj->pNext != NULL)      // j和j的下一个进行比较 保证下一个有东西 {if(pj->value > pj->pNext->value){pj->value = pj->value^ pj->pNext->value;pj->pNext->value = pj->value^ pj->pNext->value;pj->value = pj->value^ pj->pNext->value;}pj = pj->pNext;           // j++ }pi = pi->pNext;               // i++ 减少趟数 }	
}void BucketSort(int arr[],int length)
{if(arr == NULL || length <=0)return;//1.最大值 最小值int nMin = arr[0];int nMax = arr[0];int i;for(int i=1;i<length;i++){if(arr[i] < nMin){nMin = arr[i];}if(arr[i] > nMax){nMax = arr[i];}}//2.位数int nCount = 1;int nNum = nMax;while(nNum){nNum/=10;nCount*=10;}nCount/=10;              //863变100  23变10 //3.表头int nMinIndex = nMin/nCount;int nMaxIndex = nMax/nCount;Bucket **pBucket = NULL;pBucket = (Bucket**)malloc(sizeof(Bucket*)*(nMaxIndex-nMinIndex+1));memset(pBucket,0,sizeof(Bucket*)*(nMaxIndex-nMinIndex+1));//4.元素入桶Bucket *pTemp = NULL;for(int i=0;i<length;i++){nNum = arr[i]/nCount-nMinIndex;pTemp = (Bucket*)malloc(sizeof(Bucket));pTemp->value = arr[i];pTemp->pNext = pBucket[nNum];pBucket[nNum] = pTemp; }//5.各桶之间元素排序for(int i=0;i<nMaxIndex-nMinIndex+1;i++){Sort(pBucket[i]);}//6.放回nNum=0;for(int i=0;i<nMaxIndex-nMinIndex+1;i++){pTemp = pBucket[i];while(pTemp){arr[nNum] = pTemp->value;nNum++;pTemp = pTemp->pNext;} }//7.释放Bucket *pDel = NULL;for(int i=0;i<nMaxIndex-nMinIndex+1;i++){pTemp = pBucket[i];while(pTemp){pDel = pTemp;pTemp = pTemp->pNext;free(pDel);pDel = NULL;}}free(pBucket);pBucket = NULL; 
}void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {201,405,743,165,589,140,989,193,288};BucketSort(arr,sizeof(arr)/sizeof(arr[0]));Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
} 

选择排序：SelectSort

找最大值放到最后/最小值放在最前面

6和3比3大 6和9比没九大 max=9的下标 9和1比 然后一顿比 最大放在最后

#include<stdio.h>void SelectSort(int arr[],int length)
{if(arr == NULL || length<=0)return;int i;int j;int min;for(int i=0;i<length-1;i++){min=i;for(int j=i+1;j<length;j++){if(arr[j]<arr[min]){min=j;}}//最小值放入最前面if(min!= i){arr[i]=arr[i]^arr[min];arr[min]=arr[i]^arr[min];arr[i]=arr[i]^arr[min];} }
}void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {2,4,7,1,5,14,89,13,2};SelectSort(arr,sizeof(arr)/sizeof(arr[0]));Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
}

插入排序：InsertSort

将待排序数据分成两部分，一部分有序，一部分无序，将无序元素依次插入到有序中去完成排序

#include<stdio.h>void InsertSort(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;    //无序的第一个int j;    //有序的最后一个int temp;for(int i=1;i<length;i++){j=i-1;temp=arr[i];  //无序的第一个元素while(j>=0 && temp<arr[j]){arr[j+1] = arr[j];j--;}arr[j+1]=temp; } 
}void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {2,4,7,1,5,14,89,13,2};InsertSort(arr,sizeof(arr)/sizeof(arr[0]));Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
}

希尔排序：ShellSort

将数据分组，各组之内插入排序，比原有插入排序更快，适合大量数据，不常用。

 

计数排序：CountingSort

核心思想：基于非比较的排序

1.找最大值和最小值

2.计数

3.排序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>   //memsetvoid CountingSort(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;int min = arr[0];int max = arr[0];//最大值最小值查找for(int i=1;i<length;i++){if(arr[i]<min){min=arr[i];}if(arr[i]>max){max=arr[i];} }//计数空间int *pCount=NULL;pCount=(int*)malloc(sizeof(int)*(max-min+1));memset(pCount,0,sizeof(int)*(max-min+1));//计数for(i=0;i<length;i++){pCount[arr[i]-min]++;}//名次for(int i=1;i<max-min+1;i++){pCount[i]=pCount[i]+pCount[i-1];}//排序int *pNew = (int*)malloc(sizeof(int)*length);for(i=length-1;i>=0;i--){pNew[pCount[arr[i]-min]-1]=arr[i];pCount[arr[i]-min]--;}//放回原数组for(int i=0;i<length;i++){arr[i]=pNew[i];}free(pNew);pNew=NULL;free(pCount);pCount=NULL; 
}
void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {2,4,7,1,5,14,89,13,2};CountingSort(arr,sizeof(arr)/sizeof(arr[0]));Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
}

基数排序：RadixSort

LSD：低位优先

MSD：高位优先

#include<stdio.h>
#include<stdlib.h>
#include<string.h>typedef struct node
{int value;struct node *pNext;
}Radix;void RadixSort(int arr[],int length)
{if(arr == NULL || length <= 0)return;//找最大值int nMax = arr[0];int i;for(int i=1;i<length;i++) {if(arr[i] > nMax){nMax = arr[i];}}//计算最大值位数int nCount = 0;while(nMax){nMax/=10;nCount++;}//按位处理int nLoopTimes;int nbase = 1;//表头 Radix **pRadix = NULL;pRadix = (Radix**)malloc(sizeof(Radix*)*10);memset(pRadix,0,sizeof(Radix*)*10);for(nLoopTimes = 1;nLoopTimes<=nCount;nLoopTimes++){i = nLoopTimes;while(i>1){nbase*=10;i--;}//数据入组Radix *pTemp = NULL;for(i = 0;i<length;i++){pTemp = (Radix*)malloc(sizeof(Radix));pTemp->value = arr[i];pTemp->pNext = NULL;//尾添加if(pRadix[arr[i]/nbase%10] == NULL){pRadix[arr[i]/nbase%10] = pTemp;}else{Radix *pNode = pRadix[arr[i]/nbase%10];while(pNode->pNext){pNode = pNode->pNext;}pNode->pNext = pTemp;}}//放回 int j=0;for(i=0;i<10;i++){pTemp = pRadix[i];while(pTemp){arr[j]=pTemp->value;pTemp = pTemp->pNext;j++;}} //释放Radix *pDel = NULL;for(int i=0;i<10;i++){pTemp = pRadix[i];while(pTemp){pDel = pTemp;pTemp = pTemp->pNext;free(pDel);pDel = NULL;}}//清空memset(pRadix,0,sizeof(Radix*)*10); 	 } free(pRadix);pRadix = NULL;
}void Print(int arr[],int length)
{if(arr == NULL || length <=0)return;int i;for(int i=0;i<length;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {53, 3, 542, 748, 14, 214, 154, 63, 616};RadixSort(arr,sizeof(arr)/sizeof(arr[0]));Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
}