首页 > 试题广场 >

单链表的选择排序

[编程题]单链表的选择排序

热度指数：2088 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无序单链表，实现单链表的选择排序(按升序排序)。

输入描述:

第一行一个整数 n，表示单链表的节点数量。
第二行 n 个整数 val 表示单链表的各个节点。

输出描述:

在给出的函数内返回给定链表的头指针。

示例1

输入

5
1 3 2 4 5

输出

1 2 3 4 5

备注:

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct ListNode {
  ElemType val;
  struct ListNode* next;
} ListNode, *PListNode, *List;

// function declaration
void printList(List L);
// 简单选择排序算法。复杂的选择排序又称堆排序!!!
List simple_selection_sort_algorithm(List L, const int size);

int main(const int argc, const char* argv[]) {
  int n, val;
  fscanf(stdin, "%d", &n);
  
  PListNode head = NULL, tail = NULL, p;
  while (fscanf(stdin, "%d", &val) != EOF) {
    p = (PListNode) malloc(sizeof(ListNode));
    p->val = val;
    p->next = NULL;
    if (!tail) head = tail = p;
    else tail = tail->next = p;
  }
  
  head = simple_selection_sort_algorithm(head, n);
  return printList(head), 0;
}

void printList(List L) {
  PListNode p = L;
  while (p) {
    fprintf(stdout, "%d", p->val);
    if (p->next) fputc(32, stdout);
    p = p->next;
  }
}

List simple_selection_sort_algorithm(List L, const int size) {
  // corner case
  if (size < 2) return L;
  
  PListNode nodes[size], p = L;
  int i, t;
  for (i = 0; i < size; ++i, p = p->next)
    *(nodes + i) = p;
  
  int min;
  PListNode tmp;
  for (t = 0; t < size - 1; ++t) {
    min = t;
    for (i = t + 1; i < size; ++i)
      if ((*(*(nodes + i))).val < (*(*(nodes + min))).val)
        min = i;
    tmp = *(nodes + t);
    *(nodes + t) = *(nodes + min);
    *(nodes + min) = tmp;
  }
  
  for (i = 0; i < size - 1; ++i)
    (*(nodes + i))->next = *(nodes + i + 1);
  (*(nodes + size - 1))->next = NULL;
  
  return *nodes;
}

发表于 2021-07-25 12:02:50 回复(0)

pein531

不交换节点，而交换节点的值就行。这样数组怎么进行选择排序，链表就怎么进行选择排序。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strArr = br.readLine().trim().split(" ");
        ListNode head = new ListNode(Integer.parseInt(strArr[0]));
        ListNode cur = head;
        for(int i = 1; i < n; i++){
            cur.next = new ListNode(Integer.parseInt(strArr[i]));
            cur = cur.next;
        }
        head = selectionSort(head);
        while(head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    
    private static ListNode selectionSort(ListNode head) {
        ListNode cur = head;
        while(cur.next != null){
            ListNode minNode = cur;
            ListNode innerCur = minNode.next;
            while(innerCur != null){
                if(innerCur.val < minNode.val)
                    minNode = innerCur;
                innerCur = innerCur.next;
            }
            if(minNode.val != cur.val){
                int val = minNode.val;
                minNode.val = cur.val;
                cur.val = val;
            }
            cur = cur.next;
        }
        return head;
    }
}

发表于 2021-06-14 17:20:33 回复(0)

EVANnnn1996

书上的解法复杂了，直接按照选择排序写就行了，数组是怎么操作的，链表就怎么操作。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    
    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value +" ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static Node selectionSort(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node cur = head;
        Node node;
        Node min;
        int temp;
        while (cur != null) {
            node = cur.next;
            min = cur;
            while (node != null) {
                if (node.value < min.value) {
                    min = node;
                }
                node = node.next;
            }
            temp = cur.value;
            cur.value = min.value;
            min.value = temp;
            cur = cur.next;
        }
        return head;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] numbers = bufferedReader.readLine().split(" ");
        Node head = listGenerator(n, numbers);
        head = selectionSort(head);
        printList(head);
    }
}

发表于 2020-02-13 21:22:19 回复(0)

Python 3

毓毓子最可爱

n=input()
arr = list(map(int, input().split(' ')))
arr = sorted(arr)
arr = list(map(str, arr))
print(' '.join(arr))

发表于 2021-09-07 09:13:49 回复(0)

C++

echo-djx

不使用辅助栈或者调整节点的值

不断的把当前链表的最小节点放到末尾

list_node * selection_sort(list_node * head)
{
    //////在下面完成代码
    int count = 0;
    list_node *newhead = new list_node();
    newhead->next = head;
    head = newhead;
    while(head->next!=nullptr){
        count ++;
        head=head->next;
    }
    list_node *tailnode = head;
    head = newhead;
    int min = INT32_MAX;
    list_node *minnode;
    while(count){
        for(int i = 0;i < count;i++){
            if(head->next->val < min){
                min = head->next->val;
                minnode = head;
            }
            head = head->next;
        }
        head = newhead;
        tailnode->next  = minnode->next;
        minnode->next = minnode->next->next;
        tailnode = tailnode->next;
        min = INT32_MAX;
        count--;
        if(count == 0)tailnode->next = nullptr;
    }
    return newhead->next;
}

发表于 2021-10-13 11:13:11 回复(0)

牛客380870390号

＃include <bits> using namespace std; struct list_node{ int val; struct list_node * next; }; list_node * input_list(void) { int n, val; list_node * phead = new list_node(); list_node * cur_pnode = phead; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &val); if (i == 1) { cur_pnode->val = val; cur_pnode->next = NULL; } else { list_node * new_pnode = new list_node(); new_pnode->val = val; new_pnode->next = NULL; cur_pnode->next = new_pnode; cur_pnode = new_pnode; } } return phead; } list_node * selection_sort(list_node * head) { //////在下面完成代码 if(head==nullptr)return head; list_node *cur=new list_node(); cur->val=-1; cur->next=head; list_node *pHead=cur; while(cur->next!=nullptr){ list_node *small=cur->next; list_node *p=small; list_node *preSmall=p; list_node *pre=p; while(p!=nullptr){ if(p->val<small->val){ small=p; preSmall=pre; } pre=p; p=p->next; } if(small!=cur->next){ preSmall->next=small->next; small->next=cur->next; cur->next=small; } cur=cur->next; } return pHead->next; } void print_list(list_node * head) { while (head != NULL) { printf("%d ", head->val); head = head->next; } puts(""); } int main () { list_node * head = input_list(); list_node * new_head = selection_sort(head); print_list(new_head); return 0; }</small-></bits>

发表于 2021-05-06 18:23:20 回复(0)

一只老风铃

不想努力了，冒泡排序吧。

list_node * selection_sort(list_node * head)
{
    //////在下面完成代码
    if(head==NULL || head->next==NULL)
        return head;
    int len=0;
    list_node* p=head;
    while(p)
    {
        len++;
        p=p->next;
    }
    //冒泡排序
    for(int i=0;i<len;i++)
        for(list_node* p=head;p->next;p=p->next)
        {
            if(p->val>p->next->val)
                swap(p->val,p->next->val);
        }
    return head;
}

发表于 2021-01-12 19:06:06 回复(0)

程序猿的浪漫

// 只有简单的题，才敢发到评论区
list_node * selection_sort(list_node * head,int n)
{
    //////在下面完成代码
    list_node* cur = head;
    list_node* ans = cur;
    while(cur != nullptr){
        int Min = cur->val;
        list_node* m = cur;
        head = cur->next;
        while(head != nullptr){
            if(head->val < Min){
                m = head; 
                Min = head->val;
            }
            head = head->next;
        }
        swap(cur->val,m->val);
        cur = cur->next;
    }
    
    return ans;
}

发表于 2020-07-08 20:48:53 回复(0)

ccf123

list_node * selection_sort(list_node * head)
{
    //////在下面完成代码
    if(head==nullptr)return head;
    list_node *cur=new list_node();
    cur->val=-1;
    cur->next=head;
    list_node *pHead=cur;
    
   
    while(cur->next!=nullptr){
        list_node *small=cur->next;
        list_node *p=small;
        list_node *preSmall=p;
        list_node *pre=p;
        while(p!=nullptr){
            if(p->val<small->val){
             small=p;
             preSmall=pre;
            }
            pre=p;
            p=p->next;
          
        }
        if(small!=cur->next){         
            preSmall->next=small->next;
            small->next=cur->next;
            cur->next=small;          
        }
        
          cur=cur->next;
       
    }
       
    return pHead->next;

}

发表于 2020-05-30 21:57:44 回复(0)

mysterioussuperstar

# include <bits/stdc++.h>
using namespace std;

struct list_node{
int val;
struct list_node * next;
};

list_node * input_list(void)
{
int n, val;
list_node * phead = new list_node();
list_node * cur_pnode = phead;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &val);
if (i == 1) {
cur_pnode->val = val;
cur_pnode->next = NULL;
}
else {
list_node * new_pnode = new list_node();
new_pnode->val = val;
new_pnode->next = NULL;
cur_pnode->next = new_pnode;
cur_pnode = new_pnode;
}
}
return phead;
}

list_node * selection_sort(list_node * head)
{
//////在下面完成代码
     list_node * i;
    list_node * j;
    int min_val, tmp;
    list_node * index;
    for (i = head; i; i = i->next)
    {
        min_val = i->val;
        index = i;
        for (j = i->next; j; j = j->next)
        {
            if (min_val > j->val)
            {
                min_val = j->val;
                index = j;
            }
        }
        //交换
        tmp = i->val;
        i->val = index->val;
        index->val = tmp;

    }
    return head;

}

void print_list(list_node * head)
{
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
puts("");
}

int main ()
{
list_node * head = input_list();
list_node * new_head = selection_sort(head);
print_list(new_head);
return 0;
}

发表于 2020-02-20 18:40:41 回复(0)

林阿司匹

list_node * selection_sort(list_node 
* head)
{
    //////在下面完成代码
    for(list_node* p = head;p->next!=NULL;p=p->next)
    {
        int min = p->val;
        list_node *point=p;;
        list_node* q;
        for(q = p->next;q!=NULL;q=q->next){
            if(min > q->val){
                min = q->val;
                point = q;
            }
        }
        point->val = p->val;
        p->val = min;
    }
    return head;
}

发表于 2020-01-30 21:49:12 回复(0)

小妹妹的超仔

#include <stdio.h>
#include <stdlib.h>
typedef struct LinkedList{
    int data;
    struct LinkedList *next;
}*LinkedList,Node;

void output(LinkedList L)//遍历
{
   Node *p;
   for (p = L->next; p != NULL; p = p->next)
   {
       printf("%d ", p->data);
   }
}

void Sort(LinkedList L)
{
    Node *p,*pre,*q;
    p=L->next->next;
    L->next->next=NULL;
    while(p!=0)
    {
        q=p->next;
        pre=L;
        while(pre->next!=NULL&&pre->next->data<p->data)
        {
            pre=pre->next;
        }
        p->next=pre->next;
        pre->next=p;
        p=q;
    }
}

LinkedList CreateLinkedListTail(int n)
{
    int x;
    LinkedList L;
    L = (LinkedList*)malloc(sizeof(LinkedList));
    L->next = NULL;
    LinkedList now;
    now = (LinkedList*)malloc(sizeof(LinkedList));
    now = L;
    for(int i=0;i<n;i++){
        Node *p;
        p =(Node*)malloc(sizeof(Node));
        scanf("%d",&x);
        p->data = x;
        now->next = p;
        now = p;
    }
    now->next = NULL;
    return L;
}
int main(int argc,char **argv)
{
    int len;
    LinkedList L;
    scanf("%d ",&len);
    L = CreateLinkedListTail(len);
    Sort(L);
    output(L);
    return 0;
}

发表于 2019-11-27 17:16:37 回复(0)