首页 > 代码库 > 快速排序——一次快排的应用（笔试&面试）
快速排序——一次快排的应用（笔试&面试）
将数组中的大写字母与小写字母分开
一：一个数组总存储有且in有大写和小写字母，编写一个函数对数组内的字母重新排列，让小写字母在所有大写字母之前。（相对顺序没有要求）【2012·中兴、2013·腾讯】
使用快排的一次排列即可实现，代码如下：
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 using namespace std; 5 6 bool isUpper( char ch ) //equal isupper() 7 { 8 if( ch >=‘A‘ && ch <= ‘Z‘) 9 return true;10 return false;11 }12 13 bool isLower( char ch )//equal islower()14 {15 if( ch >= ‘a‘ && ch <= ‘z‘)16 return true;17 return false;18 }19 20 void Partition(string &arr, int len) //快排的一次排序过程21 {22 if( len <= 1)23 return;24 25 int low = 0;26 int high = len-1;27 28 while( low < high)29 {30 while( low < high && isUpper(arr[high]) ) --high; //如果是大写字母，位置向前移动31 while( low < high && isLower(arr[low]) ) ++low; //如果是小写字母,位置向后移动32 char tmp = arr[low]; //交换33 arr[low] = arr[high];34 arr[high] = tmp;35 }36 }37 38 int main(int argc, char const *argv[])39 {40 string str= "HElloWorlDThanKYOU";41 cout <<"Before: "<< str << endl;;42 43 Partition( str, str.size() );44 cout <<"After : "<< str << endl;45 return 0;46 }
二：给定含有 n 个元素的整形数组 arr， 其中包括 0 元素和非 0 元素，对数组进行排列，要求：【2012·人民搜索】
1、排序后所有 0 元素在前，所有非零元素在后，且非零元素排序前后相对位置不变。
2、不能使用额外存储空间；
例如：
输入 0、 3 、0、 2、1、 0、 0
输出 0、 0、 0、 0、 3、 2、1
思路：此处要求非零元素排序前后相对位置不变，因此可以利用快苏排序一次排序的第二种情况（两个指针索引一前一后移动），代码如下：
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 using namespace std; 5 6 const int N = 7; 7 void ZeroPatition( int *arr, int len) 8 { 9 int slow =len-1; //最末尾一个元素10 11 for(int fast = slow; fast>=0; --fast)12 {13 if( arr[fast] != 0)14 {15 if( slow != fast) //位置不同时交换16 {17 arr[slow] = arr[fast];18 arr[fast] =0;19 }20 slow--;//向前移动21 }22 }23 }24 25 void print(int *arr, int len)26 {27 for(int i= 0; i < len; ++i)28 cout << arr[i]<<" ";29 cout << endl;30 }31 32 int main(int argc, char const *argv[])33 {34 //int arr[N] = {0, 3, 0, 2, 1, 0, 0};35 int arr[N] = {0, 3, 0, 0, 2, 0, 1};36 print(arr, N);37 38 ZeroPatition(arr, N);39 print(arr, N);40 return 0;41 }
三：荷兰国旗问题
将乱序的红白蓝三色小球排列成同颜色在一起的小球组（按照红白蓝排序），这个问题称为荷兰国旗问题。
这是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。如下图所示：其中 0代表红球，2为篮球，1为白球。
解答：这个问题类似于快排中的partition过程。不过，要用三个指针，一前begin、一中current、一后end。begin与current同时初始化为数组首部，end初始化指向数组尾部
1、current遍历整个数组序列，current指1时，不交换，current++;2、current指0时，与begin交换，而后current++，begin++;3、current指2时，与end交换，而后current不动，end--。
主体代码如下：
1 //荷兰国旗问题 2 void Flag_Netherland(int *arr, int len) 3 { 4 int current =0, begin =0, end = len-1; 5 6 while(current <= end) 7 { 8 if(arr[current] == 0) 9 {10 swap(&arr[begin], &arr[current]);11 current ++;12 begin++;13 }14 else if( arr[current] == 1)15 {16 current ++;17 }18 else // arr[current]==219 {20 swap( &arr[current], &arr[end]);21 end--;22 }23 }24 }
完整代码如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <time.h> 5 #define N 10 6 7 void print_Arr(int *arr, int len) 8 { 9 int i;10 for (i = 0; i < len; ++i)11 {12 printf("%2d", arr[i]);13 }14 printf("\n");15 }16 17 void init_Arr(int *arr, int len)18 {19 int i = 0;20 while( i < len)21 {22 arr[i] = rand()%3;23 ++i;24 }25 }26 27 void swap(int* left, int *right)28 {29 int tmp = *left;30 *left = *right;31 *right = tmp;32 }33 34 //荷兰国旗问题35 void Flag_Netherland(int *arr, int len)36 {37 int current =0, begin =0, end = len-1;38 39 while(current <= end)40 {41 if(arr[current] == 0)42 {43 swap(&arr[begin], &arr[current]);44 current ++;45 begin++;46 }47 else if( arr[current] == 1)48 {49 current ++;50 }51 else // arr[current]==252 {53 swap( &arr[current], &arr[end]);54 end--;55 }56 }57 }58 59 int main(int argc, char const *argv[])60 {61 srand(time(NULL));62 63 int arr[N];64 init_Arr(arr, N);65 printf("Before:\n");66 print_Arr(arr, N);67 68 Flag_Netherland(arr, N);69 printf("After\n");70 print_Arr(arr, N);71 return 0;72 }
完毕。
快速排序——一次快排的应用（笔试&面试）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。