an interview question(2) - Koestler－IT工程師數位筆記本

文章出處

感覺現在好多面試題還是很注重基礎的，今天面試時就遇到這題，回來一查后才知道此題是國內某著名通信公司的一道機試題：）
給定一個數組input[ ]，如果數組長度n為奇數，則將數組中最大的元素放到

output[ ] 數組最中間的位置，如果數組長度n為偶數，則將數組中最大的元素放到 output[ ] 數組中間兩個位置偏右的那個位置上，然后再按從大到小的順序，依次在第一個位置的兩邊，按照一左一右的順序，依次存放剩下的數。
例如：input[] = {3, 6, 1, 9, 7}
          output[] = {3, 7, 9, 6, 1}
          input[] = {3, 6, 1, 9, 7, 8}
   output[] = {1, 6, 8, 9, 7, 3}
void sort (int input[ ],int n,int output[ ])
{

}
這題思路應該是怎樣的呢：其實應該不難，首先先做下從小到大的排序，然后把最大的放中間，然后依次從大到小的往兩邊放是不是就OK了呢？
have a try!

 1 #include <iostream>
 2 using namespace std;
 3 
 4 #define N 1000
 5 
 6 void bubbleSort(int a[],int len)
 7 {
 8     int i,j,temp;
 9     for(i = 0;i < len-1;i++)
10         for(j = i+1;j < len;j++)
11         {
12             if(a[i] > a[j])
13             {
14                 temp = a[i];
15                 a[i] = a[j];
16                 a[j] = temp;
17             }
18         }
19         //for(i = 0;i < len;i++)
20         //cout << a[i] << " ";
21 }
22 
23 void sort(int input[], int len, int output[])
24 {
25 
26     int mid = len/2;
27     int left =  mid - 1;
28     int right = mid + 1;
29    
30 
31     bubbleSort(input,len);//先數據冒泡排序
32 
33     int index = len - 1;
34     output[mid] = input[index--];
35     while(index >= 0)
36     {
37         output[left--] = input[index--];
38         //index--;
39         output[right++] = input[index--];
40         //index--;
41     }
42     for(index = 0;index < len;index++)
43         cout << output[index] << " ";
44 }
45 
46 int main()
47 {
48     int arr[] = {3,6,1,9,7,8};
49     int destArr[N];
50     sort(arr,6,destArr);
51     bubbleSort(arr,6);//輸入數據冒泡排序
52     cout << endl;
53 
54     int arr1[] = {31,6,15,9,72,8,99,5,6};
55     int destArr1[N];
56     sort(arr1,9,destArr1);
57    
58     return 0;
59 }