C++笔试编程常见题--排序

①.冒泡排序实现：
1       void bubble_sort_2(int a[], int len)
2       {
3                int i = 0;
4                int j = 0;
5                int temp = 0;            //用于交换
6                int exchange = 0;        //用于记录每次扫描时是否发生交换
7
8                for(i=0; i<len-1; i++)      //进行n-1趟扫描
9                {
10                       exchange = 0;      //每趟扫描之前对exchange置0
11                       for(j=len-1; j>=i; j--)        //从后往前交换，这样最小值冒泡到开头部分
12                       {
13                                if(a[j+1] < a[j])        //如果a[j]小于a[j-1],交换两元素值
14                                 {
15                                          temp = a[j];
16                                          a[j] = a[j+1];
17                                          a[j+1] = temp;
18                                          exchange = 1;   //发生交换，exchange置1
19                                 }
20                       }
21                       if (exchange != 1)         //此趟扫描没有发生过交换，说明已经是排序的
22                                return;              //不需要进行下次扫描
23              }
24     }

②.插入排序实现：
1         #include <iostream>
2       using namespace std;
3
4       //直接插入排序
5       void insert_sort(int a[], int n)
6       {
7                int i, j, temp;
8
9               for (i=1; i<n; i++) //需要选择n-1次
10              {
11                       //暂存下标为i的数。下标从1开始，因为开始时
12                  //下标为0的数，前面没有任何数，此时认为它是排好顺序的。
13                       temp = a[i];
14                       for (j=i-1; j>=0 && temp<a[j]; j--)
15                       {
16                                 //如果满足条件就往后挪。最坏的情况就是temp比a[0]小，它要放在最前面
17                                a[j+1] = a[j];
18                       }
19   
20                       a[j+1] = temp;         //找到下标为i的数的放置位置
21              }
22     }
23
24     void print_array(int a[], int len)
25     {
26              for(int i = 0; i < len; i++)   //循环打印数组的每个元素
27              {
28                       cout << a[i] << " ";
29              }
30              cout << endl;
31     }
32   
33     int main()
34     {
35              int a[] = {7, 3, 5, 8, 9, 1, 2, 4, 6};
36              cout << "before insert sort: ";
37              print_array(a, 9);
38              insert_sort(a, 9);        //进行直接插入排序
39              cout << "after insert sort: "
40              print_array(a, 9);
41              return 0;
42     }
insert_sort函数的插入次数是len-1，因为当数组只有一个a[0]时，我们认为a[0]就是已经排好序的了。局部变量i用于表示对哪一个元素进行插入操作，j表示插入到哪个目标元素的后面，temp保存需要插入的元素。这里最坏的情况就是temp比a[0]都小，此时j为-1，需要把temp作为新的a[0]。
测试结果如下：
1       before insert sort: 7 3 5 8 9 1 2 4 6
2       before insert sort: 1 2 3 4 5 6 7 8 9

③.快速排序实现：
1       void quick_sort(int a[], int low, int high)
2       {
3                int i, j, pivot;
4                if (low < high)
5                {
6                         pivot = a[low];
7                         i = low;
8                         j = high;
9                         while(i<j)
10                       {
11                                while (i<j && a[j]>=pivot)
12                                          j--;
13                                if(i<j)
14                                          a[i++]=a[j];     //将比pivot的元素移到低端
15
16                                while (i<j && a[i]<=pivot)
17                                          i++;
18                                if(i<j)
19                                          a[j--] = a[i];    //将比pivot大的元素移到高端
20                       }
21                       a[i] = pivot;             //pivot移到最终位置
22                       quick_sort(a, low, i-1);   //对左区间递归排序
23                       quick_sort(a, i+1, high);  //对右区间递归排序
24              }
25     }
这里pivot代码基准值，它的初始值为a[low]。局部变量i和j分别代表low和high的位置。接着按照下面的步骤进行一趟交换：
（1）把比pivot的元素移到低端（low）
（2）把比pivot大的元素移到高端（high）
（3）pivot移到最终位置，此时这个位置的左边元素的值都比pivot小，而其右边元素的值都比pivot大。
（4）对左、右区间分别进行递归排序。从而把前三步的粗排序逐渐的细化，直至最终low和high交汇。

④.选择排序实现：
1         #include <iostream>
2       using namespace std;
3
4       void select_sort(int a[], int len)
5       {
6                int i,j,x,l;
7
8                for(i=0; i<len; i++)       //进行n-1次遍历
9                {       
10                       x = a[i];            //每次遍历前x和l的初值设置
11                       l = i;
12                       for(j=i; j<len; j++)   //遍历从i位置向数组尾部进行
13                       {
14                                if(a[j] < x)
15                                 {
16                                          x = a[j];   //x保存每次遍历搜索到的最小数
17                                          l = j;      //l记录最小数的位置
18                                 }
19                       }
20                       a[l] = a[i];           //把最小元素与a[i]进行交换
21                       a[i] = x; 
22              }
23}
24   
25     void main()
26     {
27              int data[9] = {54,38,96,23,15,72,60,45,83};
28              select_sort(data, 9);      //快速排序
29              for(int i = 0; i<9; i++)
30                       cout << data[i] << " "; //打印排序后的数组
31     }
select_sort函数进行了n-1趟排序。局部变量x和l分别记录每次遍历时所得的最小元素值及所在位置，代码20~21行利用他们进行与a[i]的交换。以main函数中的data数组为例，说明其具体步骤：
（1）第1次排序：数组各元素为54,38,96,23,15,72,60,45,83，此时i为0，遍历整个数组得到最小元素15，然后与a[0]进行交换，结果为：15,38,96,23,54,72,60,45,83。
（2）第2次排序：此时i为1，遍历从a[1]开始到数组末尾得到最小元素23，然后与a[1]进行交换，结果为：15,23,96,38,54,72,60,45,83。
（3）第3次排序：此时i为2，遍历从a[2]开始到数组末尾得到最小元素38，然后与a[2]进行交换，结果为：15,23,38,96,54,72,60,45,83。
显然，每次排序都选出了一个最小的元素与遍历起始位置的元素进行交换。通过n-1次这样的排序，最终把整个数组进行了排序。
执行结果为：
1       15 23 38 45 54 60 72 83 96

⑤.堆排序实现：
1         #include <iostream>
2       using namespace std;
3     
4       int heapSize = 0;
5     
6       //返回左子节点索引
7       int Left(int index) { return ((index << 1) + 1);}
8     
9       //返回右子节点索引
10     int Right(int index) {return ((index << 1) + 2);}
11   
12     //交换a、b的值
13     void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;}
14   
15         //array[index]与其左右子树进行递归对比
16     //用最大值替换array[index],index表示堆顶索引
17     void maxHeapify(int array[], int index)
18     {
19              int largest = 0;            //最大数
20              int left = Left(index);       //左子节点索引
21              int right = Right(index);     //右子节点索引
22   
23              //把largest赋为堆顶与其左子节点的较大者
24              if ((left <= heapSize) && (array[left] > array[index]))
25                       largest = left;
26              else
27                       largest = index;
28   
29              //把largest与堆顶的右子节点比较，取较大者
30              if ((right <= heapSize) && (array[right] > array[largest]))
31                       largest = right;
32   
33              //此时largest为堆顶,左子节点,右子节点最大者
34              if (largest != index)
35              {
36                       //如果堆顶不是最大者,则交换,并递归调整堆
37                       swap(&array[index], &array[largest]);
38                       maxHeapify(array, largest);
39              }
40     }
41   
42     //初始化堆，将数组中的每一个元素置放到适当的位置
43     //完成之后，堆顶的元素为数组的最大值
44     void buildMaxHeap(int array[], int length)
45     {
46              int i;
47              heapSize = length;            //堆大小赋为数组长度
48              for (i = (length >> 1); i >= 0; i--)
49                       maxHeapify(array, i);
50     }
51 
52     void heap_sort (int array[], int length)
53     {
54              int i;
55   
56              //初始化堆
57              buildMaxHeap(array, (length - 1)); 
58            
59              for (i = (length - 1); i >= 1; i--)
60              {
61                       //堆顶元素array[0]（即数组的最大值）被置换到数组的尾部array[i]
62                       swap(&array[0], &array[i]);
63                       heapSize--;             //从堆中移除该元素
64                       maxHeapify(array, 0);    //重建堆
65              }
66     }
67   
68     int main(void)
69     {
70              int a[8] = {45, 68, 20, 39, 88, 97, 46, 59};
71              heap_sort ( a, 8 );
72              for(int i=0; i<8; i++)
73              {
74                       cout << a[i] << " ";
75              }
76              cout << endl;
77              return 0;
78     }
heap_sort函数分成下面步骤进行：
（1）调用buildMaxHeap对数组进行堆的初始化（代码57行）
（2）由于堆顶元素（即array[0]）的值是最大的（大根堆），因此把它与数组尾部进行交换。并把heapSize递减1，即从堆中移除数组尾部元素。
（3）由于只有剩下的堆顶元素（array[0]）不满足堆，因此调用maxHeapify重建堆。
（4）对前面两步进行循环调用，直到堆中只含有堆顶，此时heapSize变为1（即i为0）。
其中buildMaxHeap函数初始化堆时也调用了maxHeapify函数，而maxHeapify使用递归的方法把堆调整为大根堆。
测试结果为：
1       20 39 45 46 59 68 88 97