C++进阶(七)-模板与群体数据8

选择排序

选择排序的基本思想

• 每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。

例9-12 简单选择排序函数模板

template <class T>
void mySwap(T &x, T &y) {
    T temp = x;
    x = y;
    y = temp;
}

template <class T>
void selectionSort(T a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int leastIndex = i; 
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[leastIndex])
                leastIndex = j;
        mySwap(a[i], a[leastIndex]);
    }
}

交换排序

交换排序的基本思想

• 两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。

最简单的交换排序方法——起泡排序

• 起泡排序举例：对整数序列 8 5 2 4 3 按升序排序

对具有n个元素的序列按升序进行起泡排序的步骤：

• 首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第n个位置。

• 对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。

• 如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。

例9-13 起泡排序函数模板

template <class T>
void mySwap(T &x, T &y) {
    T temp = x;
    x = y;
    y = temp;
}

template <class T>
void bubbleSort(T a[], int n) {
    int i = n – 1;
    while (i > 0) {
      int lastExchangeIndex = 0;
      for (int j = 0; j < i; j++)
        if (a[j + 1] < a[j]) {
         mySwap(a[j], a[j + 1]);
         lastExchangeIndex = j;
        }
       i = lastExchangeIndex;
    }
}

查找

顺序查找

• 顺序查找的基本思想：

从序列的首元素开始，逐个元素与待查找的关键字进行比较，直到找到相等的。若整个序列中没有与待查找关键字相等的元素，就是查找不成功。

例9-14顺序查找函数模板

template <class T>
int seqSearch(const T list[], int n, const T &key) {
    for(int i = 0; i < n; i++)
        if (list[i] == key)
            return i;            
    return -1;                 
}

折半查找（二分法查找）算法

• 对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。

折半查找算法示例

• 用折半查找法，在下列序列中查找值为21的元素：

• 用折半查找法，在下列序列中查找值为20的元素：

例9-15 折半查找函数模板

template <class T>
int binSearch(const T list[], int n, const T &key) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {   
        int mid = (low + high) / 2;
        if (key == list[mid])    
            return mid; 
        else if (key < list[mid])
            high = mid – 1;
        else
            low = mid + 1;
    }
    return -1;
}