在数组中查找次大值，并与最后一个元素交换—C语言

1
/***************************************************
2
作业要求：
3
    在数组中查找次大值，并与最后一个元素交换
4
完成日期：
5
    2013年9月3日
6
***************************************************/
7
#include <stdio.h>
8

9
// 函数原型
10
int findSecondMaxValueInArray(int a[], int n);
11

12
// main函数
13
int main(void)
14
{
15
  int a[8] = {2, 5, 1, 3, 2, 3, 4, 6};  // 定义数组
16
  int index;  // 待求次大值元素下标
17
  int tmp;  // 临时变量，用来交换数组
18

19
  // 求数组中次大值元素下标
20
  index = findSecondMaxValueInArray(a, 8);
21
  // printf("%dn", index);
22

23
  // 次大值与数组最后一个元素交换
24
  tmp = a[index];
25
  a[index] = a[7];
26
  a[7] = tmp;
27

28
  // 输出数组……
29

30
  return 0;
31
}
32

33
/****************************************************
34
函数功能：
35
    在数组中查找次大值元素
36
算法思想：
37
    (1) 设置两个指针（下标）初始值均为0（指向数组第1个元素）；
38
    (2) 遍历数组，若当前元素大于最大值，修改最大值下标为当前元素；
39
      修改次大值下标为原来最大值下标；
40
    (3) 若当前元素不大于最大值，但大于次大值，则修改次大值下标为
41
      当前元素；
42
    (4) 数组遍历结束后，次大值下标即为所求。
43
函数参数：
44
    int    a[]    待查找元素的数组
45
    int    n    数组中元素个数
46
返回值：
47
    返回次大值元素在数组中的下标
48
时间复杂度：
49
    O(n)：其中n表示数组中元素个数
50
空间复杂度：
51
    O(1)：借助了三个辅助变量i、max1、max2实现
52
*****************************************************/
53
int findSecondMaxValueInArray(int a[], int n)
54
{
55
  int i;      // 数组元素索引（下标）
56
  int max1 = 0;  // 最大值元素下标
57
  int max2 = 0;  // 次大值元素下标
58

59
  for (i = 0; i < n; ++i)
60
  {
61
    if (a[max1] < a[i])
62
    {
63
      max2 = max1;  // 原来最大值为新的次大值
64
      max1 = i;    // 当前元素为新的最大值
65
    }
66
    else if (a[max2] < a[i])
67
    {
68
      // 若新的最大值没有出现，但是数组中元素大于次大值
69
      max2 = i;
70
    }
71
  }
72

73
  // 返回次大值下标
74
  return max2;
75
}