JavaScript实现链表插入排序和链表归并排序

本篇文章详细的介绍了javascript实现链表插入排序和链表归并排序，链表的归并排序就是对每个部分都进行归并排序，然后合并在一起。

1.链表

1.1链表的存储表示

//链表的存储表示
typedef int elemtype;
typedef struct lnode
{
  elemtype data;
  struct lnode *next;
}lnode, *linklist;

1.2基本操作

创建链表：

/*
 * 创建链表。
 * 形参num为链表的长度，函数返回链表的头指针。
 */
linklist creatlink(int num)
{
  int i, data;
 
  //p指向当前链表中最后一个结点，q指向准备插入的结点。
  linklist head = null, p = null, q;
 
  for (i = 0; i < num; i++)
  {
    scanf("%d", &data);
    q = (linklist)malloc(sizeof(lnode));
    q->data = data;
    q->next = null;
    if (i == 0)
    {
      head = q;
    }
    else
    {
      p->next = q;
    }
    p = q;
  }
  return head;
}

输出链表：

/*
 * 输出链表结点值。
 */
int printlink(linklist head)
{
  linklist p;
  for (p = head; p ;p = p->next)
  {
    printf("%-3d ", p->data);
  }
  return 0;
}

2.链表插入排序

基本思想：假设前面n-1个结点有序，将第n个结点插入到前面结点的适当位置，使这n个结点有序。

实现方法：

将链表上第一个结点拆下来，成为含有一个结点的链表(head1)，其余的结点自然成为另外一个链表(head2)，此时head1为含有

一个结点的有序链表；

将链表head2上第一个结点拆下来，插入到链表head1的适当位置，使head1仍有序，此时head1成为含有两个结点的有序链表；

依次从链表head2上拆下一个结点，插入到链表head1中，直到链表head2为空链表为止。最后，链表head1上含所有结点，且结点有序。

插入排序代码：

/*
 * 链表插入排序(由小到大)。
 * 输入：链表的头指针，
 * 输出：排序后链表的头指针。
 * 实现方法：将原链表拆成两部分：链表1仍以head为头指针，链表结点有序。链表2以head2为头指针，链表结点无序。
 * 将链表2中的结点依次插入到链表1中，并保持链表1有序。
 * 最后链表1中包含所有结点，且有序。
 */
linklist linkinsertsort(linklist head)
{
  //current指向当前待插入的结点。
  linklist head2, current, p, q;
 
  if (head == null)
    return head;
 
  //第一次拆分。
  head2 = head->next;
  head->next = null;
 
  while (head2)
  {
    current = head2;
    head2 = head2->next;
 
    //寻找插入位置，插入位置为结点p和q中间。
    for (p = null, q = head; q && q->data <= current->data; p = q, q = q->next);
 
    if (q == head)
    {
      //将current插入最前面。
      head = current;
    }
    else
    {
      p->next = current;
    }
    current->next = q;
  }
  return head;
}

完整源代码：

/*
 * 链表插入排序，由小到大
 */
#define _crt_secure_no_warnings
#include <stdio.h>
#include <stdlib.h>

#define total 10    //链表长度

//链表的存储表示
typedef int elemtype;
typedef struct lnode
{
  elemtype data;
  struct lnode *next;
}lnode, *linklist;

linklist creatlink(int num);
linklist linkinsertsort(linklist head);
int printlink(linklist head);

/*
 * 创建链表。
 * 形参num为链表的长度，函数返回链表的头指针。
 */
linklist creatlink(int num)
{
  int i, data;

  //p指向当前链表中最后一个结点，q指向准备插入的结点。
  linklist head = null, p = null, q;

  for (i = 0; i < num; i++)
  {
    scanf("%d", &data);
    q = (linklist)malloc(sizeof(lnode));
    q->data = data;
    q->next = null;
    if (i == 0)
    {
      head = q;
    }
    else
    {
      p->next = q;
    }
    p = q;
  }
  return head;
}

/*
 * 链表插入排序(由小到大)。
 * 输入：链表的头指针，
 * 输出：排序后链表的头指针。
 * 实现方法：将原链表拆成两部分：链表1仍以head为头指针，链表结点有序。链表2以head2为头指针，链表结点无序。
 * 将链表2中的结点依次插入到链表1中，并保持链表1有序。
 * 最后链表1中包含所有结点，且有序。
 */
linklist linkinsertsort(linklist head)
{
  //current指向当前待插入的结点。
  linklist head2, current, p, q;

  if (head == null)
    return head;

  //第一次拆分。
  head2 = head->next;
  head->next = null;

  while (head2)
  {
    current = head2;
    head2 = head2->next;

    //寻找插入位置，插入位置为结点p和q中间。
    for (p = null, q = head; q && q->data <= current->data; p = q, q = q->next);

    if (q == head)
    {
      //将current插入最前面。
      head = current;
    }
    else
    {
      p->next = current;
    }
    current->next = q;
  }
  return head;
}

/*
 * 输出链表结点值。
 */
int printlink(linklist head)
{
  linklist p;
  for (p = head; p ;p = p->next)
  {
    printf("%-3d ", p->data);
  }
  return 0;
}

int main()
{
  linklist head;

  printf("输入total个数以创建链表：\n");
  head = creatlink(total);
  
  head = linkinsertsort(head);
  printf("排序后：\n");
  printlink(head);
  putchar('\n');
  return 0;
}

3.链表归并排序

基本思想：如果链表为空或者含有一个结点，链表自然有序。否则，将链表分成两部分，对每一部分分别进行归并排序，然后将已排序的两个链表归并在一起。

归并排序代码：

/*
 * 链表归并排序(由小到大)。
 * 输入：链表的头指针，
 * 输出：排序后链表的头指针。
 * 递归实现方法：将链表head分为两部分，分别进行归并排序，再将排序后的两部分归并在一起。
 * 递归结束条件：进行递归排序的链表为空或者只有一个结点。
 */
linklist linkmergesort(linklist head)
{
  linklist head1, head2;
  if (head == null || head->next == null)
    return head;
 
  linksplit(head, &head1, &head2);
  head1 = linkmergesort(head1);
  head2 = linkmergesort(head2);
  head = linkmerge(head1, head2);
  return head;
}

其中链表分割函数如下，基本思想是利用slow/fast指针，具体实现方法见注释。

/*
 * 链表分割函数。
 * 将链表head均分为两部分head1和head2，若链表长度为奇数，多出的结点从属于第一部分。
 * 实现方法：首先使指针slow/fast指向链首，
 * 然后使fast指针向前移动两个结点的同时，slow指针向前移动一个结点，
 * 循环移动，直至fast指针指向链尾。结束时，slow指向链表head1的链尾。
 */
int linksplit(linklist head, linklist *head1, linklist *head2)
{
  linklist slow, fast;
 
  if (head == null || head->next == null)
  {
    *head1 = head;
    *head2 = null;
    return 0;
  }
  slow = head;
  fast = head->next;
  while (fast)
  {
    fast = fast->next;
    if (fast)
    {
      fast = fast->next;
      slow = slow->next;
    }
  }
  *head1 = head;
  *head2 = slow->next;
 
  //注意：一定要将链表head1的链尾置空。
  slow->next = null;
  return 0;
}

链表归并函数有递归实现和非递归实现两种方法：

非递归实现：

/*
 * 链表归并。
 * 将两个有序的链表归并在一起，使总链表有序。
 * 输入：链表head1和链表head2
 * 输出：归并后的链表
 * 实现方法：将链表head2中的结点依次插入到链表head1中的适当位置，使head1仍为有序链表。
 */
linklist linkmerge(linklist head1, linklist head2)
{
  linklist p, q, t;
 
  if (!head1)
    return head2;
  if (!head2)
    return head1;
 
  //循环变量的初始化，q指向链表head1中的当前结点，p为q的前驱。
  p = null;
  q = head1;
  while (head2)
  {
    //t为待插入结点。
    t = head2;
    head2 = head2->next;
    //寻找插入位置，插入位置为p和q之间。
    for (;q && q->data <= t->data; p = q, q = q->next);
    if (p == null)
      head1 = t;
    else
      p->next = t;
    t->next = q;
    //将结点t插入到p和q之间后，使p重新指向q的前驱。
    p = t;
  }
  return head1;
}

递归实现：

linklist linkmerge2(linklist head1, linklist head2)
{
  linklist result;
 
  if (!head1)
    return head2;
  if (!head2)
    return head1;
 
  if (head1->data <= head2->data)
  {
    result = head1;
    result->next = linkmerge(head1->next, head2);
  }
  else
  {
    result = head2;
    result->next = linkmerge(head1, head2->next);
  }
  return result;
}

完整源代码：

/*
* 链表归并排序，由小到大。
*/
#define _crt_secure_no_warnings
#include <stdio.h>
#include <stdlib.h>

#define total 10    //链表长度

//链表的存储表示
typedef int elemtype;
typedef struct lnode
{
  elemtype data;
  struct lnode *next;
}lnode, *linklist;

linklist creatlink(int num);
linklist linkmergesort(linklist head);
linklist linkmerge(linklist head1, linklist head2);
linklist linkmerge2(linklist head1, linklist head2);
int linksplit(linklist head, linklist *head1, linklist *head2);
int printlink(linklist head);

/*
* 创建链表。
* 形参num为链表的长度，函数返回链表的头指针。
*/
linklist creatlink(int num)
{
  int i, data;

  //p指向当前链表中最后一个结点，q指向准备插入的结点。
  linklist head = null, p = null, q;

  for (i = 0; i < num; i++)
  {
    scanf("%d", &data);
    q = (linklist)malloc(sizeof(lnode));
    q->data = data;
    q->next = null;
    if (i == 0)
    {
      head = q;
    }
    else
    {
      p->next = q;
    }
    p = q;
  }
  return head;
}

/*
* 输出链表结点值。
*/
int printlink(linklist head)
{
  linklist p;
  for (p = head; p; p = p->next)
  {
    printf("%-3d ", p->data);
  }
  return 0;
}

int main()
{
  linklist head;

  printf("输入total个数以创建链表：\n");
  head = creatlink(total);

  head = linkmergesort(head);
  printf("排序后：\n");
  printlink(head);
  putchar('\n');
  return 0;
}

/*
 * 链表归并排序(由小到大)。
 * 输入：链表的头指针，
 * 输出：排序后链表的头指针。
 * 递归实现方法：将链表head分为两部分，分别进行归并排序，再将排序后的两部分归并在一起。
 * 递归结束条件：进行递归排序的链表为空或者只有一个结点。
 */
linklist linkmergesort(linklist head)
{
  linklist head1, head2;
  if (head == null || head->next == null)
    return head;

  linksplit(head, &head1, &head2);
  head1 = linkmergesort(head1);
  head2 = linkmergesort(head2);
  head = linkmerge(head1, head2);    //非递归实现
  //head = linkmerge2(head1, head2);  //递归实现
  return head;
}

/*
 * 链表归并。
 * 将两个有序的链表归并在一起，使总链表有序。
 * 输入：链表head1和链表head2
 * 输出：归并后的链表
 * 实现方法：将链表head2中的结点依次插入到链表head1中的适当位置，使head1仍为有序链表。
 */
linklist linkmerge(linklist head1, linklist head2)
{
  linklist p, q, t;

  if (!head1)
    return head2;
  if (!head2)
    return head1;

  //循环变量的初始化，q指向链表head1中的当前结点，p为q的前驱。
  p = null;
  q = head1;
  while (head2)
  {
    //t为待插入结点。
    t = head2;
    head2 = head2->next;
    //寻找插入位置，插入位置为p和q之间。
    for (;q && q->data <= t->data; p = q, q = q->next);
    if (p == null)
      head1 = t;
    else
      p->next = t;
    t->next = q;
    //将结点t插入到p和q之间后，使p重新指向q的前驱。
    p = t;
  }
  return head1;
}

linklist linkmerge2(linklist head1, linklist head2)
{
  linklist result;

  if (!head1)
    return head2;
  if (!head2)
    return head1;

  if (head1->data <= head2->data)
  {
    result = head1;
    result->next = linkmerge(head1->next, head2);
  }
  else
  {
    result = head2;
    result->next = linkmerge(head1, head2->next);
  }
  return result;
}

/*
 * 链表分割函数。
 * 将链表head均分为两部分head1和head2，若链表长度为奇数，多出的结点从属于第一部分。
 * 实现方法：首先使指针slow/fast指向链首，
 * 然后使fast指针向前移动两个结点的同时，slow指针向前移动一个结点，
 * 循环移动，直至fast指针指向链尾。结束时，slow指向链表head1的链尾。
 */
int linksplit(linklist head, linklist *head1, linklist *head2)
{
  linklist slow, fast;

  if (head == null || head->next == null)
  {
    *head1 = head;
    *head2 = null;
    return 0;
  }
  slow = head;
  fast = head->next;
  while (fast)
  {
    fast = fast->next;
    if (fast)
    {
      fast = fast->next;
      slow = slow->next;
    }
  }
  *head1 = head;
  *head2 = slow->next;

  //注意：一定要将链表head1的链尾置空。
  slow->next = null;
  return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。