C和C++程序员面试秘笈之⑨

程序员面试秘笈之⑨"/>

C和C++程序员面试秘笈之⑨

本系列博客基于董山海的<C和C++程序员面试秘笈>，旨在记录，欢迎交流，可联系 zywang@shu.edu !

---

第九章：排序

---

文章目录

• • 1、面试题1
  • 2、面试题2
  • 3、面试题3
  • 4、面试题4
  • 5、面试题5
  • 6、面试题6
  • 7、面试题7
  • 8、面试题8
  • 9、面试题9

1、面试题1

排序：
排序分为：

1. 插入排序；
2. 选择排序；
3. 交换排序；
4. 归并排序；
5. 分配排序；

直接插入排序：

插入排序类似于打扑克。摸来的第一张无需整理，此后每次从桌子上的牌（无序区）摸一张牌并插入左手的牌（有序区）中正确的位置上。为了找到这个位置，需自左向右将摸来的牌与已有的牌一一比较。

1. 如果 R[j] 的关键字大于 R[i] 的关键字，则将 R[j] 后移一个位置；
2. 如果 R[j] 的关键字小于或者等于 R[i]的关键字，则查找过程结束，j+1即为 R[i] 的插入位置；

#include <iostream>
using namespace std;
//直接插入排序
void insert_sort(int a[], int n) {int i, j, temp;//for (i = 1; i < n; i++) {	//需要选择n-1次//暂存下标为 i 的数。下标从 1 开始，因为开始时下标为 0 的数，前面没有任何数，此时认为它是排好顺序的temp = a[i];	//暂存，后面交换for (j = i - 1; j >= 0 && temp < a[j]; j--) {a[j + 1] = a[j];	//如果满足条件就往后挪，最坏的情况就是temp比a[0]小，要放到最前面}a[j + 1] = temp;	//找到下标为 i 的数的放置位置}
}
//循环打印数组
void print_array(int a[], int len) {for (int i = 0; i < len; i++) {cout << a[i] << " ";}cout << endl;
}
//
int main() {int a[] = { 7,3,5,8,9,1,2,4,6 };cout << "before insert sort: ";print_array(a, 9);	//循环打印数组insert_sort(a, 9);	//直接插入排序cout << "after insert sort: ";print_array(a, 9);system("pause");return 0;
}

---

2、面试题2

编程实现 shell (希尔) 排序：

先将要排序的一组数按某个增量 d 分成若干组，每组中记录的下标相差 d 对每组中的全部元素进行排序，然后用一个较小的增量对它再次进行分组，并对每个组重新进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。因此 shell 排序本质是一个分组插入的方法。

#include <iostream>
using namespace std;
//shell排序
void shell_sort(int a[], int len) {int h, i, j, temp;//初始时取序列的一半为增量，以后每次减半。直到增量为1for (h = len / 2; h > 0; h = h / 2) {	//控制增量for (i = h; i < len; i++) {temp = a[i];for (j = i - h; (j >= 0 && temp < a[j]); j = j - h) {a[j + h] = a[j];}a[j + h] = temp;}}
}
//循环打印数组
void print_array(int a[], int len) {for (int i = 0; i < len; i++) {cout << a[i] << " ";}cout << endl;
}
//
int main() {int a[] = { 7,3,5,8,9,1,2,4,6 };cout << "before insert sort: ";print_array(a, 9);	//循环打印数组shell_sort(a, 9);	//直接插入排序cout << "after insert sort: ";print_array(a, 9);system("pause");return 0;
}

---

3、面试题3

冒泡排序：
将被排序的记录数组 A[1…n]垂直排列，每个记录 A[i] 看作重量为 A[i] 气泡。轻的气泡在重的气泡之上，从下往上扫描数组 A；凡是违反这个轻在上重在下的原则，就会交换，使其上浮。如此反复，直到最后任何两个气泡都是轻在上，重在下。

#include <iostream>
using namespace std;void bubble_sort_1(int a[], int len);
//循环打印数组
void print_array(int a[], int len) {for (int i = 0; i < len; i++) {cout << a[i] << " ";}cout << endl;
}
//
int main() {int a[] = { 7,3,5,8,9,1,2,4,6 };cout << "before insert sort: ";print_array(a, 9);	//循环打印数组bubble_sort_1(a, 9);	//直接插入排序cout << "after insert sort: ";print_array(a, 9);system("pause");return 0;
}void bubble_sort_1(int a[], int len) {int i = 0, j = 0, temp = 0;//这里的temp用于交换for (i = 0; i < len - 1; i++) {		//进行n-1次交换for (j = len - 1; j >= i; j--) {	//从后往前扫描交换，这样最小值冒泡到开头部分if (a[j = 1] < a[j]) {temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
}

上面的代码的效率不高：因为进行第 i 次扫描前，数组已经排序好了，但是它还会扫描，显然以后的扫描是没有意义的。

#include <iostream>
using namespace std;void bubble_sort_2(int a[], int len);
//循环打印数组
void print_array(int a[], int len) {for (int i = 0; i < len; i++) {cout << a[i] << " ";}cout << endl;
}
//
int main() {int a[] = { 7,3,5,8,9,1,2,4,6 };cout << "before insert sort: ";print_array(a, 9);	//循环打印数组bubble_sort_1(a, 9);	//直接插入排序cout << "after insert sort: ";print_array(a, 9);system("pause");return 0;
}void bubble_sort_2(int a[], int len) {int i = 0, j = 0, temp = 0, exchange = 0;//temp用于交换、exchange用于记录每次扫描时候是否发生交换for (i = 0; i < len - 1; i++) {		//进行n-1趟扫描exchange = 0;	//每趟扫描之前对exchange置0for (j = len - 1; j >= i; j--) {	//从后往前交换，这样最小值冒泡到开头部分if (a[j + 1] < a[j]) {	//如果a[j]小于a[j-1],交换两元素的值temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;exchange = 1;	//发生交换，标志位置1}}if (exchange != 1)	//如果没有发生过交换，说明已经排序了，不需要进行下次扫描return;}
}

---

4、面试题4

编程实现快速排序：
快速排序：分治法

1. 分解；A[low…high] 分为 A[low…pivotpos] 和 A[pivotpos+1…high]；
2. 对左右各区间分别求解；
3. 组合。对左右有序子区间，直接组合；

#include <iostream>
using namespace std;//循环打印数组
void print_array(int a[], int len) {for (int i = 0; i < len; i++) {cout << a[i] << " ";}cout << endl;
}
//
int main() {int a[] = { 7,3,5,8,9,1,2,4,6 };cout << "before insert sort: ";print_array(a, 9);	//循环打印数组quick_sort(a, 0, 8);	//直接插入排序cout << "after insert sort: ";print_array(a, 9);system("pause");return 0;
}void quick_sort(int a[], int low, int high) {//这边 i 和 j 分别代表 low 和 high 的位置。pivot代表基准值，初始值为 a[low]int i, j, pivot;if (low < high) {pivot = a[low];i = low;j = high;while (i < j) {while (i < j && a[j] >= pivot) j--;if (i < j)	//	这边隐含的就是a[j]<privota[i++] = a[j];	//将比pivot小的元素移到低端while (i < j && a[i] <= pivot)i++;if (i < j)a[j--] = a[i];	//将比pivot大的元素移到高端}a[i] = pivot;		//pivot 移到最终位置quick_sort(a, low, i - 1);	//对左区间递归排序quick_sort(a, i + 1, high);	 //对右区间递归排序}
}

• 把比 pivot 小的元素移到低端（low）;
• 把比 privot 大的元素移动到高端（high）;
• privot 移动到最终位置，此时这个位置的左边元素的值都比 pivot 小，而右边元素的值都比 pivot 大 ；
• 对左右区间分别进行递归排序。从而把前三部的粗排序逐渐细化 ，直至最终 low 和 high 交汇；

---

5、面试题5

编程实现选择排序：
直接选择排序：n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。
直接选择排序是不稳定的，shell 排序也是不稳定的。冒泡排序是稳定的。

• 初始状态：无序区为 A[1…n]，有序区为空；
• 第一趟排序：在无序区 A[1…n] 中选出最小的记录 A[k]，将它与无序区的第一个记录 A[1] 交换；
• 第 i 趟排序：当前有序区和无序区分别为：A[1…i-1] 和 A[i…n] 。该趟排序从当前无序区 A[i…n] 中选取关键字最小的记录 A[k]，将他与无序区的第1个 A[i] 进行交换，使有序区变为 A[1…i]。

#include <iostream>
using namespace std;
//
void select_sort(int a[], int len) {int i, j, x, l;for (i = 0; i < len; i++) {		//进行 n-1 次遍历x = a[i];	//每次遍历前 x和l的初值设定l = i;for (j = i; j < len; j++) {		//遍历从i位置向数组尾部进行if (a[j] < x) {x = a[j];		//x保存每次遍历搜索到的最小数l = j;		//l记录最小数的位置}}a[l] = a[i];		//把最小元素与 a[i] 进行交换a[i] = x;}
}
//
void main() {int data[9] = { 54,38,96,23,15,72,60,45,83 };select_sort(data, 9);//打印排序好的数组for (int i = 0; i < 9; i++) {cout << data[i] << " ";}
}

---

6、面试题6

编程实现堆排序：

1. 小根堆：所有子节点都大于其父节点；
2. 大根堆：所有子节点都小于其父节点；

#include <iostream>
using namespace std;int heapSize = 0;//返回左子节点索引
int Left(int index) {return ((index << 1) + 1);
}//返回右子节点索引
int Right(int index) {return ((index << 1) + 2);
}//交换a、b的值
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}//array[index]与其左、右子树进行递归对比
//用最大值替换 array[index] ，index表示堆顶索引
void maxHeapify(int array[], int index) {int largest = 0;	//最大数int left = Left(index);		//左子节点索引int right = Right(index);	//右子节点索引//把largest赋为对堆顶与其左子节点的较大者if ((left <= heapSize) && (array[left] > array[index])) {largest = left;}elselargest = index;//把largest与堆顶的右子节点比较，取较大者if ((right <= heapSize) && (array[right] > array[largest])) {largest = right;}//此时largest为堆顶、左子节点、右子节点中的最大者if (largest != index) {//如果堆顶不是最大者，则交换，并递归调整swap(&array[index], &array[largest]);maxHeapify(array, largest);}
}//初始化堆，将数组中的每一个元素置放到适当的位置，完成之后，堆顶的元素为数组的最大值
void buildMaxHeap(int array[], int length) {int i;heapSize = length;		//堆大小赋为数组长度for (i = (length >> 1); i >= 0; i--) {maxHeapify(array, i);}
}//
void heap_sort(int array[], int length) {int i;//初始化堆buildMaxHeap(array, (length - 1));//for (i = (length - 1); i >= 1; i--) {//堆顶元素array[0]（数组最大值）被置换到数组的尾部 array[i]swap(&array[0], &array[i]);heapSize--;		//从堆中移除该元素maxHeapify(array, 0);		//重建堆}
}//
int main(void) {int a[8] = { 48,68,20,39,88,97,46,59 };heap_sort(a, 8);for (int i = 0; i < 8; i++) {cout << a[i] << " ";}cout << endl;system("pause");return 0;
}

---

7、面试题7

实现归并排序：

归并排序：利用 归并技术 进行排序，归并技术指：将若干个已排序的子文件合并成一个有序的文件。

两路归并算法的基本思路：设两个有序的子文件（相当于输入堆）放在同一向量中相邻的位置上：A[low…m]，a[m+1…high]，先将他们合并到一个局部的暂存向量 Temp 中，待合并完成后将 Temp 复制回 A[low…high]中。

归并排序有两种实现方法：自底向上和自顶向下。

自底向上：

1. 第一趟归并排序时，将待排序的文件 A[1…n] 看作 n 个长度为 1 的有序子文件，将这些子文件两两合并。若 n 为偶数，则得到 n/2 个长度为2的有序子文件；若 n 为奇数，则最后一个子文件不参与合并。故本趟归并完成后，前 n/2 有序子文件长度为2，但最后一个子文件长度为1；
2. 第2趟排序归并则是将第1趟得到的 n/2 个有序子文件两两合并，如此反复，直到最后得到一个长度为n的有序文件；

自顶向下：

1. 分解：将当前区间一分为二，即求分裂点；
2. 求解：递归地对两个子区间 A[low…mid] 和 A[mid+1…high] 进行归并排序；
3. 组合：将已经排序的两个子区间 A[low…mid] 和 A[mid+1…high]归并成一个有序的区间 R[low…high]；
4. 递归的终结条件：子区间长度为1（一个记录自然有序）

#include <iostream>
using namespace std;
//将分治的两端按大小次序填入临时数组，最后把临时数组拷贝到原始数组中
//lPos 到 rPos-1 为一端，rPos 到 rEnd 为另外一端
void Merge(int a[], int tmp[], int lPos, int rPos, int rEnd) {//其中 a 为数组地址首地址,tmp 为分配的数组地址，int i, lEnd, NnumElements, tmpPos;lEnd = rPos - 1;tmpPos = lPos;	//这边是较小的部分，从左边开始NnumElements = rEnd - lPos + 1;		//数组长度//while (lPos <= lEnd&&rPos <= rEnd) {if (a[lPos] <= a[rPos]) {		//比较两端的元素值tmp[tmpPos++] = a[lPos++];		//把较小的值先放入temp临时数组}else {tmp[tmpPos++] = a[rPos++];}}//到这里，左端或者右端可能某一端可能含有剩余元素while (lPos <= lEnd)tmp[tmpPos++] = a[lPos++];while (rPos <= rEnd) {tmp[tmpPos++] = a[rPos++];}//把临时数组拷贝给原始数组for (i = 0; i < NnumElements; i++, rEnd--) {a[rEnd] = tmp[rEnd];}
}
//
void msort(int a[], int tmp[], int low, int high) {if (low >= high)	//结束条件return;int middle = (low + high) / 2;	//计算分裂点msort(a, tmp, low, middle);		//对子区间 [low,middle] 递归做归并排序 msort(a, tmp, middle + 1, high);	//对子区间[midlle+1, high]递归做归并排序Merge(a,tmp, low, middle + 1, high);	//组合，把两个有序区合并为一个有序区
}
//归并的最外层调用
void merge_sort(int a[], int len) {	//数组地址和数组长度int *tmp = NULL;tmp = new int[len];	//分配数组临时空间if (tmp != NULL) {msort(a, tmp, 0, len - 1);	//排序delete []tmp;}
}
//
int main() {int a[8] = { 8, 6, 1, 3, 5, 2, 7, 4 };merge_sort(a, 8);system("pause");return 0;
}

---

8、面试题8

使用基数排序对整数进行排序：
基数排序：箱排序的推广。其基本思想为：设置若干个箱子，依次扫描待排序的记录 R[0]，R[1]，…R[n-1]。把关键字等于 k 的记录全部装入第 K 个箱子里（分配），然后按序号依次将各非空的箱子首尾连接起来。

#include <iostream>
#include <math.h>
using namespace std;
//查找长度为len的数组的最大元素
int find_max(int a[], int len) {int max = a[0];		//max从a[0]开始for (int i = 1; i < len; i++) {if (max < a[i]) {	//如果发现元素比 max 到max = a[i];		//就给 max 重新赋值}}return max;
}
//计算number有多少位
int digit_number(int number) {int digit = 0;do {number /= 10;digit++;} while (number != 0);return digit;
}
//
int kth_digit(int number, int kth) {number /= pow(10, kth);return number % 10;
}
//对长度为len的数组进行基数排序
//数组的地址  数组的长度
void radix_sort(int a[], int len) {int *temp[10];	//指针数组，每一个指针表示一个箱子int count[10] = { 0,0,0,0,0,0,0,0,0,0 };	//用于存储每个箱子里面装有多少个元素int max = find_max(a, len);	//取得序列中最大的整数int maxDigit = digit_number(max);		//得到最大整数的位数int i, j, k;//for (i = 0; i < 10; i++) {temp[i] = new int[len];	 //使每一个箱子能装下 len 个元素memset(temp[i], 0,sizeof(int)*len);		//初始化为0}//for (i = 0; i < maxDigit; i++) {memset(count, 0, sizeof(int) * 10);	  //每次装箱前把count清空for (j = 0; j < len; j++) {int xx = kth_digit(a[j], i);	//将数据安装位数放入暂存数组中temp[xx][count[xx]] = a[j];count[xx]++;		//此箱子的计数递增}//int index = 0;for (j = 0; j < 10; j++) {		//将数据从暂存数组中取回，放入原始数组中for (k = 0; k < count[j]; k++) {	//把箱子里所有元素都取回到原始数组中a[index++] = temp[j][k];}}}
}
//
int main() {int a[] = { 22,32,19,53,47,29 };radix_sort(a, 6);system("pause");return 0;
}

---

9、面试题9

各排序算法的性能比较：

1. 冒泡排序： O ( n 2 ) O(n^2) O(n2)
2. 选择排序： O ( n 2 ) O(n^2) O(n2)
3. 插入排序： O ( n 2 ) O(n^2) O(n2)
4. 快速排序：不稳定，最理想为 O ( n l o g 2 n ) O(nlog2n) O(nlog2n)，最坏为 O ( n 2 ) O(n^2) O(n2)
5. 堆排序： O ( n l o g n ) O(nlogn) O(nlogn)
6. 归并排序： O ( n l o g 2 n ) O(nlog2n) O(nlog2n)

---