C++面试题（只使用0与数组中其它数交换进行排序）

糖逗

题目描述：

1. 一个长度为n的数组，乱序存放着[0, n-1]，现在只允许0与其它数交换，将数组从小到大排序

复制代码

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. 
   
6. void print(int *array,int len) {
   
7.         for (int i = 0; i < len; i++) {
   
8.                 cout << array[i] << " ";
   
9.         }
   
10.         cout << endl;
    
11. }
    
12. 
    
13. 
    
14. void swap_with_zero(int* array, int len, int n){
    
15.         int pos0 = 0, posn = 0;
    
16.         int cnt = 0;
    
17.         for(int i = 0; i < len; i++){
    
18.                 if(array[i] == 0){
    
19.                         pos0 = i;
    
20.                         cnt++;
    
21.                 }
    
22.                 if(array[i] == n){
    
23.                         posn = i;
    
24.                         cnt++;
    
25.                 }
    
26.                 if(cnt == 2) break;
    
27.         }
    
28.         int temp = array[pos0];
    
29.         array[pos0] = array[posn];
    
30.         array[posn] = temp;
    
31.         return;
    
32. }
    
33. 
    
34. 
    
35. void sort(int* array, int len){
    
36.         if(array[0] != 0) swap_with_zero(array, len, array[0]);
    
37.         for(int i = 1; i < len; i++){
    
38.                 if(array[i] != 0){
    
39.                         if(array[i] == i) continue;
    
40.                         else{
    
41.                                 swap_with_zero(array, len, array[i]);
    
42.                                 swap_with_zero(array, len, i);
    
43.                         }
    
44.                 }
    
45.         }
    
46. }
    
47. 
    
48. 
    
49. 
    
50. int main(){
    
51.         int array[] = {5, 3, 2, 4, 1, 6, 7, 0};
    
52.         int len = sizeof(array) /sizeof(int);
    
53.         sort(array, len);
    
54.         print(array, len);
    
55.         system("pause");
    
56.         return 0;
    
57. }

复制代码

注意事项：
1.这里0更多像是一个复制的前置头。