source_c.zip_linux 链表_嵌入式C面试

#include <stdio.h> #include <stdlib.h> /*1.Bubble sort*/ void BubbleSort(int* pData,int Count) { int iTemp=0; int i=0,j=0; for(i=1;i<Count;i++) { for(j=Count-1;j>=i;j--) { if(pData[j]<pData[j-1]) { iTemp = pData[j-1]; pData[j-1] = pData[j]; pData[j] = iTemp; } } } } /*2. Exchange Sort*/ void ExchangeSort(int* pData,int Count) { int iTemp=0; int i=0,j=0; for(i=0;i<Count-1;i++) { for(j=i+1;j<Count;j++) { if(pData[j] < pData[i]) { iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; } } } } /*3. Select Sort*/ void SelectSort(int* pData,int Count) { int iTemp=0; int iPos=0; int i=0,j=0; for(i=0;i<Count-1;i++) { iTemp = pData[i]; iPos = i; for(j=i+1;j<Count;j++) { if(pData[j] < iTemp) { iTemp = pData[j]; iPos = j; } } if(i!=j) { pData[iPos] = pData[i]; pData[i] = iTemp; } } } /*4. Insert Sort*/ void InsertSort(int* pData,int Count) { int iTemp=0; int iPos=0; int i=0; for(i=1;i<Count;i++) { iTemp = pData[i]; iPos = i-1; while((iPos>=0)&&(iTemp<pData[iPos])) { pData[iPos+1] = pData[iPos]; iPos--; } pData[iPos+1] = iTemp; } } /*5.Bin Insert Sort*/ void BinSort(int* pData,int Count) { int iTemp=0; int i=0,j=0; int low=0,mid=0,high=0; for(i=1;i<Count;i++) { low = 0; high = i-1; iTemp = pData[i]; while(low <= high) { mid = (low+high)/2; if(iTemp<pData[mid]) high = mid-1; else low = mid+1; } for(j=i-1;j>=low;j--) pData[j+1]=pData[j]; pData[low]=iTemp; } } /*6. Quick Sort*/ void Run(int* pData,int left,int right) { int i=left,j=right; int middle=0,iTemp=0; middle = pData[(left+right)/2]; do { while((pData[i]<middle)&&(i<right)) i++; while((pData[j]>middle)&&(j>left)) j--; if(i<=j) { iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j); if(left<j) { Run(pData,left,j); } if(i<right) { Run(pData,i,right); } } void QuickSort(int* pData,int Count) { Run(pData,0,Count-1); } /*7. Double Bubble Sort*/ void Bubble2Sort(int* pData,int Count) { int iTemp=0; int left = 0; int right = Count-1; int t=0; int i=0,j=0; do { for(i=right;i>left;i--) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } left = t+1; for(j=left;j<right;j++) { if(pData[j]>pData[j+1]) { iTemp = pData[j]; pData[j] = pData[j+1]; pData[j+1] = iTemp; t = j; } } right = t-1; }while(left<right); } /*8. Shell Sort*/ void ShellSort(int* pData,int Count) { int step=0; int i=0; int temp=0,iPos=0; for(step=Count/2;step>=1;step/=2) { for(i=step;i<Count;i++) { temp = pData[i]; iPos = i-step; while((iPos>=0)&&(temp<pData[iPos])) { pData[iPos+step] = pData[iPos]; iPos -= step; } pData[iPos+step] = temp; } } } /*9. Merge Sort*/ void Merge(int* pData,int low,int mid,int high) { int i=low,j=mid+1,p=0; int *R=NULL; R=(int*)malloc((high-low+1)*sizeof(int)); if(!R) return; while((i<=mid)&&(j<=high)) R[p++]=(pData[i]<=pData[j])?pData[i++]:pData[j++]; while(i<=mid) R[p++]=pData[i++]; while(j<=high) R[p++]=pData[j++]; for(p=0,i=low;i<=high;p++,i++) pData[i]=R[p]; free(R); R=NULL; } void MergeSort(int *pData,int low,int high) { int mid; if(low<high) { mid=(low+high)/2; MergeSort(pData,low,mid); MergeSort(pData,mid+1,high); Merge(pData,low,mid,high); } } /*10. Heap Sort*/ void AdjustHeap(int *pData,int k,int n) { int iTemp=pData[k]; int ch; while(2*k+1<n) { ch=2*k+1; if((ch!=n-1)&&(pData[ch]<pData[ch+1])) { ch=ch+1; } if(iTemp<pData[ch]) { pData[k]=pData[ch]; } else { break; } k=ch; } pData[k]=iTemp; } void HeapSort(int *pData,int len) { int i,iTemp; /*Creat Init Heap*/ for(i=len/2-1;i>=0;i--) AdjustHeap(pData,i,len); for(i=len-1;i>0;i--) { iTemp=pData[0]; pData[0]=pData[i]; pData[i]=iTemp; AdjustHeap(pData,0,i); } } /*Main function*/ void main() { int k; /*1.Bubble Sort*/ { int data[] = {10,1,2,-2,6,5,-3,3,2,1,0}; int len = sizeof(data)/sizeof(data[0]); printf("Bubble init: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); BubbleSort(data,len); printf("Bubble Sort: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); } /*2.Exchange Sort*/ { int data[] = {10,1,2,-2,6,5,-3,3,2,1,0}; int len = sizeof(data)/sizeof(data[0]); printf("Exchange init: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); ExchangeSort(data,len); printf("Exchange Sort: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); } /*3.Select Sort*/ { int data[] = {10,1,2,-2,6,5,-3,3,2,1,0}; int len = sizeof(data)/sizeof(data[0]); printf("Select init: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); SelectSort(data,len); printf("Select Sort: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); } /*4.Insert Sort*/ { int data[] = {10,1,2,-2,6,5,-3,3,2,1,0}; int len = sizeof(data)/sizeof(data[0]); printf("Insert init: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); InsertSort(data,len); printf("Insert Sort: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); } /*4.Bin Sort*/ { int data[] = {10,1,2,-2,6,5,-3,3,2,1,0}; int len = sizeof(data)/sizeof(data[0]); printf("Bin init: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); BinSort(data,len); printf("Bin Sort: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); } /*4.Quick Sort*/ { int data[] = {10,1,2,-2,6,5,-3,3,2,1,0}; int len = sizeof(data)/sizeof(data[0]); printf("Quick init: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); QuickSort(data,len); printf("Quick Sort: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); } /*4.Bubble2 Sort*/ { int data[] = {10,1,2,-2,6,5,-3,3,2,1,0}; int len = sizeof(data)/sizeof(data[0]); printf("Bubble2 init: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); Bubble2Sort(data,len); printf("Bubble2 Sort: "); for(k=0;k<len;k++) { printf(" %d ",data[k]); } printf("\n"); } /*4.Shell Sort*/ { int data[] = {10,1,2,-2,6,5,-3,3,2,1,0}; int len = sizeof(data)/sizeof(data[0]); printf("Shell init: ")