[算法]应用选择排序对链表进行排序(C++版)

By | April 19, 2019

Created On: 2019-04-18

选择排序的核心思想是:选择最小/最大的那个数据与指定的数据(比选择出来的数据大/小)进行交换。

例如,有一个数组 Arr={10, 8, -1, 3, 2, 1, 5},那么按照选择排序的核心思想,假设从小到大的排序,第一次扫描过后就要用第一个元素10以后的一个最小数,也就是-1与10交换;第二次扫描过后就要用元素1与第二个元素数据8交换,以此类推。重要的一点是确保已排序的元素不要比后面的任意一个元素大,相等可以,因为还会继续扫描,直到最后一个元素排好序。

/*================================================================
*   Copyright (C) 2019 Navin Xu. All rights reserved.
*   
*   Filename    :linked_list.cpp
*   Author      :Navin Xu
*   E-Mail      :admin@navinxu.com
*   Create Date :2019年04月18日
*   Description :
================================================================*/
#include <iostream>

struct Node {
    int num = 0;
    Node * next = nullptr;
};


/**
 * 创建链表
 */
Node * create_linked_list() {
    int input = 0;

    Node *pHead = nullptr, *current = nullptr, *last = nullptr;
    std::cout << "请输入若干数字来构建链表(每行一个),输入 0 终止数据输入:" << std::endl;
    std::cin >> input;
    while (input != 0) {
        if (!pHead) {
            pHead = new Node;

            pHead->num = input;
            current = pHead;
        } else {
            current = new Node;
            current->num = input;
            last->next = current;
        }
        std::cin >> input; 
        last = current;
    }

    if (pHead)
        last->next = nullptr;

    return pHead;
}

/**
 * 展示链表的数据
 */
void display_linked_list(Node *list) {
    Node *tmp = list;

    while (tmp) {
        std::cout << tmp->num << std::endl;
        tmp = tmp->next;
    }
}

/**
 * 交换两个数据
 */
void exchange_data(Node *&p, Node *&q) {
    int tmp = p->num;
    p->num = q->num;
    q->num = tmp;
}

/**
 *
 * 选择排序算法对链表进行从小到大的排序
 */
void select_asc_sort_for_lined_table(Node *&list) {
    Node *tmp = nullptr, *p = nullptr, *q = nullptr;

    for (p = list; p; p = p->next) {
        tmp = p;
        for (q = p; q; q = q->next) {
            if (tmp->num > q->num)
                tmp = q;
        }

        if (tmp != p)
            exchange_data(tmp, p);
    }
}

/**
 * 从内存销毁链表的数据
 */
void destroy_linked_list(Node *&list) {
    Node *tmp = nullptr;
    while (list) {
        tmp = list;
        delete tmp;
        // 证明一下数据是否清除
        //std::cout << "::" << list->num << std::endl;
        list = list->next;
    }
}

int main() {

    Node *pHead = create_linked_list();

    std::cout << "========输入结束==========" << std::endl;

    display_linked_list(pHead);

    std::cout << "========以上是原数据==========" << std::endl;

    select_asc_sort_for_lined_table(pHead);

    std::cout << "========排序完成后==========" << std::endl;

    display_linked_list(pHead);


    destroy_linked_list(pHead);
    //display_linked_list(pHead);

    return 0;
}

鉴于本人的相关知识储备以及能力有限,本博客的观点和描述如有错漏或是有考虑不周到的地方还请多多包涵,也欢迎指正,一起学习,共同进步。如果本文对您有帮助,而且让您觉得值得为内容付费,那么就请赞助(打赏)一下本人,这不强制。打赏支持微信支付,方法是使劲地戳一下下方的“打赏”按钮,然后得到微信收款的二维码,再用微信支付扫一下,就像买菜那样。祝好!