面试题：
把tv和radio节目排序，tv放前面，radio放后面。
节目类型相同的按频点又低到高排序
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> //排序算法实现由低到高排序 //同时广播Radio节目放后面，TV节目放前面 #define TV 0 #define Radio 1 typedef struct stb_service_s { long frequce;//频率 int servicetype;//TV 为0,Radio 为1 }stb_service_t; void stbdata_swap(stb_service_t *pstbdata1,stb_service_t *pstbdata2) { stb_service_t stbtmp = {0}; memcpy(&stbtmp,pstbdata1,sizeof(stb_service_t)); memcpy(pstbdata1,pstbdata2,sizeof(stb_service_t)); memcpy(pstbdata2,&stbtmp,sizeof(stb_service_t)); } int stb_data_partion(stb_service_t *pstbdata,int left, int right) { int EndIndex = right; int StartIndex = left; stb_service_t tmp = {0}; if(NULL == pstbdata) { return 0; } if(StartIndex > EndIndex) { return 0; } memcpy(&tmp,&pstbdata[StartIndex],sizeof(stb_service_t)); while(StartIndex < EndIndex) { while(StartIndex < EndIndex && pstbdata[EndIndex].frequce > tmp.frequce) { EndIndex--; } if(StartIndex < EndIndex ) { memcpy(&pstbdata[StartIndex++],&pstbdata[EndIndex],sizeof(stb_service_t)); } else { break; } while(StartIndex < EndIndex && pstbdata[StartIndex].frequce < tmp.frequce) { StartIndex++; } if(StartIndex < EndIndex ) { memcpy(&pstbdata[EndIndex--],&pstbdata[StartIndex],sizeof(stb_service_t)); } else { break; } } memcpy(&pstbdata[StartIndex],&tmp,sizeof(stb_service_t)); return StartIndex; } int stb_data_qsort(stb_service_t *pstbdata,int left, int right) { int l = 0; if(left < right) { l = stb_data_partion(pstbdata,left,right); stb_data_qsort(pstbdata,left,l-1); stb_data_qsort(pstbdata,l+1,right); } return 0; } int stb_data_tv_and_radio_partion(stb_service_t *pstbdata,int nStart, int Len) { int EndIndex = Len ; int StartIndex = nStart; stb_service_t tmp = {0}; if(NULL == pstbdata || Len <= 1) { return -1; } memcpy(&tmp,&pstbdata[StartIndex],sizeof(stb_service_t)); while(1) { if(StartIndex >= EndIndex) { break; } while(StartIndex < EndIndex && Radio == pstbdata[EndIndex].servicetype) { EndIndex--; } if(StartIndex < EndIndex ) { stbdata_swap(&pstbdata[StartIndex++],&pstbdata[EndIndex]); } while(StartIndex < EndIndex && TV == pstbdata[StartIndex].servicetype) { StartIndex++; } if(StartIndex < EndIndex ) { stbdata_swap(&pstbdata[StartIndex],&pstbdata[EndIndex--]); } } memcpy(&pstbdata[StartIndex],&tmp,sizeof(stb_service_t)); } void dumpStbData(const stb_service_t *pstbdata,int nStart,int len) { int i = 0; char *pch1 = "TV"; char *pch2 = "Radio"; if(NULL == pstbdata || len <= 0 || nStart < 0) { return ; } for(i = nStart; i < len; i++) { printf("i[%d] freq = %ld ,%s \n",i,pstbdata[i].frequce, pstbdata[i].servicetype ? pch2: pch1); } printf("\n--------------------------\n"); return ; } int main() { stb_service_t stbdata[20] ={0}; int Len = sizeof(stbdata)/sizeof(stbdata[0]); int i = 0; int RadioCount= 0; int TVCount = 0; memset(stbdata,0,sizeof(stbdata)); srand( time(NULL )); for(i = 1;i < Len ;i++) { stbdata[i].frequce = rand()000; stbdata[i].servicetype = rand()%2; } dumpStbData(stbdata,1,Len); printf("\n next stb_data_tv_and_radio_partion\n"); stb_data_tv_and_radio_partion(stbdata,1, Len-1); dumpStbData(stbdata,1,Len); printf("\n next stb_data_qsort\n"); for(i = 1;i< Len; i++) { if(stbdata[i].servicetype == Radio) { break; } } if(i == Len) { printf("\n Radio index = %d\n",-1); printf("\n TV index = %d ---- %d\n",1,Len -1); } else { printf("\n Radio index = %d -- %d\n",i,Len -1); printf("\n TV index = %d ---- %d\n",1,i-1); } stb_data_qsort(stbdata,1, i-1); stb_data_qsort(stbdata,i,Len-1); dumpStbData(stbdata,1,Len); return 0; }
运行结果：
gcc test.c[2P./a.out
i[1] freq = 5688 ,Radio
i[2] freq = 8574 ,Radio
i[3] freq = 1332 ,TV
i[4] freq = 7283 ,Radio
i[5] freq = 6399 ,TV
i[6] freq = 8226 ,TV
i[7] freq = 2543 ,TV
i[8] freq = 8373 ,Radio
i[9] freq = 4733 ,TV
i[10] freq = 8251 ,TV
i[11] freq = 5430 ,TV
i[12] freq = 3438 ,Radio
i[13] freq = 8870 ,Radio
i[14] freq = 2691 ,TV
i[15] freq = 1455 ,Radio
i[16] freq = 8818 ,Radio
i[17] freq = 7312 ,TV
i[18] freq = 7761 ,TV
i[19] freq = 6928 ,TV
--------------------------
next stb_data_tv_and_radio_partion
i[1] freq = 6928 ,TV
i[2] freq = 7761 ,TV
i[3] freq = 1332 ,TV
i[4] freq = 7312 ,TV
i[5] freq = 6399 ,TV
i[6] freq = 8226 ,TV
i[7] freq = 2543 ,TV
i[8] freq = 2691 ,TV
i[9] freq = 4733 ,TV
i[10] freq = 8251 ,TV
i[11] freq = 5430 ,TV
i[12] freq = 5688 ,Radio
i[13] freq = 8870 ,Radio
i[14] freq = 3438 ,Radio
i[15] freq = 1455 ,Radio
i[16] freq = 8818 ,Radio
i[17] freq = 8373 ,Radio
i[18] freq = 7283 ,Radio
i[19] freq = 8574 ,Radio
--------------------------
next stb_data_qsort
Radio index = 12 -- 19
TV index = 1 ---- 11
i[1] freq = 1332 ,TV
i[2] freq = 2543 ,TV
i[3] freq = 2691 ,TV
i[4] freq = 4733 ,TV
i[5] freq = 5430 ,TV
i[6] freq = 6399 ,TV
i[7] freq = 6928 ,TV
i[8] freq = 7312 ,TV
i[9] freq = 7761 ,TV
i[10] freq = 8226 ,TV
i[11] freq = 8251 ,TV
i[12] freq = 1455 ,Radio
i[13] freq = 3438 ,Radio
i[14] freq = 5688 ,Radio
i[15] freq = 7283 ,Radio
i[16] freq = 8373 ,Radio
i[17] freq = 8574 ,Radio
i[18] freq = 8818 ,Radio
i[19] freq = 8870 ,Radio
--------------------------
root@ubuntu:/share#
