C++面试题（七）

2019-11-08 02:49:50

字体：大中小

来源：转载

供稿：网友

在C++中，排序也是一个很重要的东西，下面就对常见的排序算法进行一个总结 1.交换函数

void swap(int *a, int i, int j) //交换两个数 { if(i==j) return; int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }

（1）冒泡排序依次比较相邻的数据，将小数据放在前，大数据放在后；即第一趟先比较第1个和第2个数，大数在后，小数在前，再比较第2个数与第3个数，大数在后，小数在前，以此类推则将最大的数”滚动”到最后一个位置；第二趟则将次大的数滚动到倒数第二个位置……第n-1(n为无序数据的个数)趟即能完成排序。以下面5个无序的数据为例： 40 8 15 18 12 （文中仅细化了第一趟的比较过程）第1趟: 8 15 18 12 40 第2趟: 8 15 12 18 40 第3趟: 8 12 15 18 40 第4趟: 8 12 15 18 40

void bubblesort(int *arr,int nsize) { //排序，从i开始排，总是在[i+1,nsize]去寻找比当前元素小的，并且交换，使得当前位置的值总是其后面最小的。 for (int i = 0; i < nsize; i++) for (int j = i + 1; j < nsize; j++) if (arr[i] > arr[j]) swap(arr, i,j); }

（2）选择排序以升序为例，比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换…… 第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。以下面5个无序的数据为例： 56 12 80 91 20（文中仅细化了第一趟的选择过程）第1趟：12 56 80 91 20 第2趟：12 20 80 91 56 第3趟：12 20 56 91 80 第4趟：12 20 56 80 91

void selectsort(int *arr, int nsize) { for (int i = 0; i < nsize; i++) { //arr[i+1....nsize-1]中找到当前最小值及其位置（准备与当前a[i]调换） int min = arr[i]; int minpos = i; for (int j = i + 1; j < nsize; j++) { if (arr[j] < min) { min = arr[j]; //当前最小值 minpos = j;//记录当前最小值的位置 } } swap(arr, i, minpos);//交换最小值位置，a[0....i]已经有序 } }

（3）插入排序像扑克摸牌一样，插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中……第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。以下面5个无序的数据为例： 65 27 59 64 58 （文中仅细化了第四次插入过程）第1次插入: 27 65 59 64 58 第2次插入: 27 59 65 64 58 第3次插入: 27 59 64 65 58 第4次插入: 27 58 59 64 65

void insertsort(int *arr, int nsize) { int i, j, key; for (i = 1; i<nsize; i++)//控制需要插入的元素 { key = arr[i]; //key为当前要插入的元素，将其插入到有序段arr[0,i-1] j = i - 1; while (j >= 0 && arr[j] > key) //查找要插入的位置,循环结束时则找到插入位置j { arr[j+1] = arr[j]; //移动元素的位置.供要插入元素使用 j--; } arr[j+1] = key; //插入指定元素到指定位置 } }

（4）快速排序快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，该方法的基本思想是： 1．先从数列末尾取出一个数作为基准元。 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。

//手动快速默写快排：先划界，再分治.... int quickPartion(int *arr, int low, int high) { int pos = rand() % (high - low + 1) + low; swap(arr, pos, high);//将末尾的元素随机化,防止极端情况 int key = arr[high];//总是将末尾元素选为关键化界元 int i = low - 1;//总是记录比key小的元素最前面的位置 for (int j = low; j <= high - 1; j++) { if (arr[j] <= key) swap(arr, ++i, j); } swap(arr, ++i, high); return i;//返回“中间位置” } void QuickSort(int *arr, int low, int high) { if (low < high) { int mid = quickPartion(arr, low, high); QuickSort(arr, low, mid - 1); QuickSort(arr, mid + 1, high); } }

上一篇：[C++ primer] 第13章_拷贝、赋值、销毁知识总结+代码实现

下一篇：GeekBand C++面向对象下第二周笔记