插入排序 c++ 习题

插入排序是一种简单直观的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。C++中实现插入排序的代码如下所示：

引用中的代码实现了一个简单的插入排序，其中使用了一个无类型的函数i来进行排序。该函数的参数n表示数组a的长度，函数内部使用了一个for循环来遍历数组a，将无序区间插入到有序区间中。

引用中的题目要求对给定的十个数进行排序，可以使用插入排序来实现。具体实现方法可以参考引用中的代码。

引用中的代码实现了一个将数组中的奇数和偶数分别放在数组的前半部分和后半部分的函数Partition4。该函数使用了模板来实现通用性，可以对不同类型的数组进行操作。

相关问题

插入排序 C++ 习题

插入排序是一种简单直观的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。C++中实现插入排序的代码如下所示：

引用中的代码实现了一个简单的插入排序，其中使用了一个无类型的函数i来进行排序。该函数的参数n表示数组a的长度，函数内部使用了一个for循环来遍历数组a，将无序区间插入到有序区间中。

引用中的题目要求对给定的十个数进行排序，可以使用插入排序来实现。具体实现方法可以参考引用中的代码。

引用中的代码实现了一个将数组中的奇数和偶数分别放在数组的前半部分和后半部分的函数Partition4。该函数使用了模板来实现通用性，可以对不同类型的数组进行操作。

练习习题9-4，利用DNode.h，编写使用双向链表的程序，其中实现左插入、右插入，删除，显示等链表的功能。 2. 练习习题9-10，直接插入排序。 3. 练习习题9-12，选择排序。 4. 练习习题9-14，起泡排序。 5. 练习习题9-19，折半查找。

以下是对应的代码实现：

1. 双向链表的实现：

DNode.h:

#ifndef DNODE_H
#define DNODE_H

template<typename T>
struct DNode{
    T data;
    DNode<T> *prior, *next;
    DNode(const T &d, DNode<T> *p = nullptr, DNode<T> *n = nullptr):data(d), prior(p), next(n){}
};

#endif //DNODE_H

双向链表的实现：

#include <iostream>
#include "DNode.h"

template<typename T>
class DList{
public:
    DList() : head(new DNode<T>(T())), size(0){}
    ~DList(){
        DNode<T> *p = head, *q;
        while(p){
            q = p->next;
            delete p;
            p = q;
        }
    }
    void insert(const T &d); // 右插入
    void leftInsert(const T &d); // 左插入
    bool remove(const T &d); // 删除
    bool empty() const { return size == 0; }
    void display() const;
private:
    DNode<T> *head;
    int size;
};

template<typename T>
void DList<T>::insert(const T &d){
    DNode<T> *p = head;
    while(p->next) p = p->next;
    DNode<T> *q = new DNode<T>(d, p, nullptr);
    p->next = q;
    ++size;
}

template<typename T>
void DList<T>::leftInsert(const T &d){
    DNode<T> *p = head->next;
    DNode<T> *q = new DNode<T>(d, head, p);
    head->next = q;
    if(p) p->prior = q;
    ++size;
}

template<typename T>
bool DList<T>::remove(const T &d){
    DNode<T> *p = head->next;
    while(p && p->data != d) p = p->next;
    if(!p) return false;
    p->prior->next = p->next;
    if(p->next) p->next->prior = p->prior;
    delete p;
    --size;
    return true;
}

template<typename T>
void DList<T>::display() const{
    DNode<T> *p = head->next;
    while(p){
        std::cout << p->data << " ";
        p = p->next;
    }
    std::cout << std::endl;
}

2. 直接插入排序：

#include <iostream>
#include <vector>

template<typename T>
void insertSort(std::vector<T> &arr){
    int n = arr.size();
    for(int i = 1; i < n; ++i){
        T tmp = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > tmp){
            arr[j+1] = arr[j];
            --j;
        }
        arr[j+1] = tmp;
    }
}

int main(){
    std::vector<int> arr{3, 5, 1, 4, 2};
    insertSort(arr);
    for(auto x : arr) std::cout << x << " ";
    std::cout << std::endl;
    return 0;
}

3. 选择排序：

#include <iostream>
#include <vector>

template<typename T>
void selectSort(std::vector<T> &arr){
    int n = arr.size();
    for(int i = 0; i < n-1; ++i){
        int k = i;
        for(int j = i+1; j < n; ++j){
            if(arr[j] < arr[k]) k = j;
        }
        if(k != i) std::swap(arr[i], arr[k]);
    }
}

int main(){
    std::vector<int> arr{3, 5, 1, 4, 2};
    selectSort(arr);
    for(auto x : arr) std::cout << x << " ";
    std::cout << std::endl;
    return 0;
}

4. 起泡排序：

#include <iostream>
#include <vector>

template<typename T>
void bubbleSort(std::vector<T> &arr){
    int n = arr.size();
    for(int i = 0; i < n-1; ++i){
        bool flag = false;
        for(int j = 0; j < n-1-i; ++j){
            if(arr[j] > arr[j+1]){
                std::swap(arr[j], arr[j+1]);
                flag = true;
            }
        }
        if(!flag) break;
    }
}

int main(){
    std::vector<int> arr{3, 5, 1, 4, 2};
    bubbleSort(arr);
    for(auto x : arr) std::cout << x << " ";
    std::cout << std::endl;
    return 0;
}

5. 折半查找：

#include <iostream>
#include <vector>

template<typename T>
int binarySearch(std::vector<T> &arr, const T &x){
    int l = 0, r = arr.size()-1;
    while(l <= r){
        int mid = (l+r)/2;
        if(arr[mid] == x) return mid;
        else if(arr[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

int main(){
    std::vector<int> arr{1, 2, 3, 4, 5};
    int pos = binarySearch(arr, 4);
    std::cout << pos << std::endl;
    return 0;
}