DanH Sach Lien Ket Vong

Danh Sách liên kết vòng là danh sách liên kết nhưng trướng next của nút cuối chỉ nút đầu tiên trong danh sách.

Không nói dài dòng chúng ta sẽ nghiên cứu luôn về cách cài đặt danh sách liên kết vòng bằng biến động.
C Code:Lựa chọn code | Ẩn/Hiện code
int listsize(NODEPTR *plist)
{
     NODEPTR p;
   int i;
   if(empty(plist))
       return (0);
   p = (*plist->next);
   i = 1;
   while(p != *plist)
   {
        i++;
      p = p->next;
   }
}

1. Khai báo cấu trúc một nút strong danh sách liên kết vòng.
Khai báo một nút là một mẫu tin (struct) có hai trường là info và next.
Trường info: chứa nội dung của nút.
Trường next: là con trỏ chỉ nút, dùng chỉ nút kế trong danh sách liên kết vòng.

struct node
{
      int info;
            struct node *next;
};
//khai bao kieu con tro chi den nut
typedef struct node *NODEPTR;
Chúng ta quản lý danh sách liên kết vòng qua con trỏ plist chỉ nút cuối của danh sách. Con trỏ plist có thể khai báo toàn cục hay cụ bộ.


2. Các tác vụ trên danh sách liên kết vòng:

Tác vụ getnode:
Cấp phát một biến động làm cho nút một danh sách liên kết vòng:

NODEPTR getnode(void)
{
      NODEPTR p;
   p = (NODEPTR) malloc(sizeof(struct node));
   return (p);
};

Tác vụ freenode:
Giải phóng biến động đã cấp phát trước đó.

void freenode(NODEPTR p)
{
      free(p);
}

Tác vụ initialize:
Khởi động danh sách liên kết vòng:

void initialize(NODEPTR *plist)
{
     *plist = NULL;
}

Tác vụ empty:
Kiểm tra danh sách liên kết vòng có rỗng không.

int empty(NODEPTR *plist)
{
       return(*plist == NULL ? true : false);
}

Tác vụ listsize:
Đếm số nút có trong danh sách liên kết vòng:

int listsize(NODEPTR *plist)
{
     NODEPTR p;
   int i;
   if(empty(plist))
       return (0);
   p = (*plist->next);
   i = 1;
   while(p != *plist)
   {
        i++;
      p = p->next;
   }
   return (i);
}

Tác vụ nodepointer:
Trả về con trỏ nút thứ i (i = 0,1,2,....) trong danh sách liên kết vòng

NODEPTR nodepointer(NODEPTR *plist, int i)
{
      NODEPTR p;
      int vitri;
      if(i < 0 || i >= listsize(plist))
           return(null);
      p = (*plist)->next; //p chi nut dau dslk vong
      for(vitri = 0;vitri < i;vitri++)
          p = p->next;
      return(p);
}

Tác vụ push:
Thêm một nút vào đầu danh sách liên kết vòng.

void push(NODEPTR *plist, int x)
{
      NODEPTR p;
   p = getnode();
   p->info = x;
   if(empty(plist) == true)
       *plist = p;
   else
       p->next = (*plist)->next;
   (*plist)->next = p;
};

Tác vụ insend:
Thêm nút vào cuối danh sách liên kết vòng.

void insend(NODEPTR *plist, int x)
{
    NODEPTR p;
    p = getnode();
    p->info = x;
    if(empty(plist) == true)
        p->next = p;
    else
    {
         p->next = (*plist)->next;
      (*plist)->next = p;
    }
    *plist = p;
};

Tác vụ pop:
Xóa nút ở đầu danh sách liên kết vòng.

int pop(NODEPTR *plist)
{
      NODEPTR p;
   int x;
   if(empty(plist))
       printf("Danh sach bi rong");
   else
   {
        p = (*plist)->next; // p la nut can xoa
      x = p->info;
      if(p == *plist) // truong hop ds chi co mot nut
          *plist = NULL;
      else
          (*plist)->next = p->next;
      freenode(p);
      return (x);
   }
};

Tác vụ dellast:
Xóa nút ở cuối danh sách liên kết vòng.

int dellast(NODEPTR *plist)
{
     NODEPTR p;
   int x;
   if(empty(plist))  // truong hop danh sach bi rong
       printf("Danh sach bi rong");
   else
   {
        if((*plist)->next == plist) // truong hop cho co mot nut
           {
              p = *plist;
               x = p->info;
             *plist = NULL;
              freenode(p);
              return(x);
         }
         p = *plist;    // p la nut can xoa
         x = p->info;
         *plist = nodepointer(plist, listsize(plist) - 2);
         (*plist)->next = p->next;
         freenode(p);
         return (x);
   }
}

Tác vụ traverse:
Duyệt danh sách liên kết vòng từ nút đầu đến nút cuối.

void traverse(NODEPTR *plist)
{
     NODEPTR p;
   if(*plist == NULL)
       printf("Danh sach rong")
   else
   {
        p = (*plist)->next; //p chi nut dau
      printf("%d", p->info);
      p = p->next;        //p chi nut thu hai
      while(p != (*plist)->next)
      {
           printf("%d",p->info);
         p = p->next;
      }
   }
}

Cai Dat Danh Sach Lien Ket Don

// DSLKD.cpp : Defines the entry point for the console application.
//


//File:quanliSV.c
//Chuong trinh quan li sinh vien so cap
//Input: cac thong tin cua sinh vien nhap vao tu ban phim
//Ouput: in ra danh sach sinh vien va thuc hien mot so chuc nang
//------------------------------------------------------------------------------
//Class:                                Instructor:
//Assignment:                           Date assigned:
//Programmer:                           Date completed:
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#include <iostream>
using namespace std;

/*dinh nghia cac gia tri ma nguoi dung co the chon*/
#define kiHieu (1,2,3,4,5,0)

//Cau truc cua mot sinh vien
typedef struct pp{
    char ht[20];
    char que[20];
    char maSoSV[20];
    struct pp *next;
}sinhVien;

//Ham nhap danh sach sinh vien
void nhapSV(sinhVien **pdau,int *n);

//Ham sua thong tin cua mot sinh vien trong danh sach
void suaSV(sinhVien *pdau,int *n);

//Ham them sinh vien vao trong danh sach
void themSV(sinhVien *pdau,int *n);

//Ham xoa sinh vien trong danh sach
void xoaSV(sinhVien *pdau,int *n);

//Ham tim kiem thong tin ve 1 sinh vien trong danh sach
void timSV(sinhVien *pdau,int *n);

//Ham in ra danh sach cac sinh vien duoc quan li trong danh sach
void inSV(sinhVien *pdau,int *n);

//Ham main
void main()
{
    //Khai bao dia chi cua sinh vien dau tien
    sinhVien *pdau = NULL;
    int n;
    int chon;
    //Nhap danh sach sinh vien ban dau
    nhapSV(&pdau,&n);
    printf("HAY AN 1 PHIM CHUC NANG SAU:\n\
Phim 1 de sua thong tin cua mot sv trong danh sach\n\
Phim 2 de them 1 sv vao trong danh sach\n\
Phim 3 de xoa 1 sv trong danh sach\n\
Phim 4 de tim kiem 1 sv trong danh sach\n\
Phim 5 de in ra thong tin cac sv trong danh sach\n\
Phim 0 de thoat khoi chuong trinh\n");
    printf("Chon: "); scanf("%d",&chon);
    //Kiem tra so ma nguoi dung nhap vao co hop le hay khong
    while(chon > 6|| chon < 0){
        printf("So ban nhap khong hop le!\n Xin ban nhap lai: ");
        scanf("%d",&chon);
    }
    //Xoa luong du lieu vao
    fflush(stdin);
    //Cac chuc nang tuong ung voi cac so
    switch(chon){
        case 0:
            exit(0);
        case 1:
            suaSV(pdau,&n);
        case 2:
            themSV(pdau,&n);
        case 3:
            xoaSV(pdau,&n);
        case 4:
            timSV(pdau,&n);
        case 5:
            inSV(pdau,&n);
    }
    getch();
}

//Ham nhap danh sach sinh vien
void nhapSV(sinhVien **pdau,int *n)
{
    sinhVien *p;
    char ht[20];
    //tao danh sach sinh vien
    while(1){

        //Nhap ten sinh vien roi kiem tra
        printf("\n Hay nhap ten cua sinh vien: ");
        //Kiem tra xem ten sinh vien co the them vao danh sach duoc hay khong
        gets(ht);
        if(ht[0]==0){
            break;
        }
        //Kiem tra xem dau danh sach da co phan tu nao chua
        //Neu chua co thi se tao ra phan tu dau tien
        if(*pdau==NULL){
            //Cap phat bo nho cho phan tu dau tien
            *pdau=(sinhVien*)malloc(sizeof(sinhVien));
            p=*pdau;
            strcpy(p->ht,ht);
            printf("\n Nhap que cua sinh vien: ");
            gets(p->que);
            printf("\n Ma so sinh vien: ");
            gets(p->maSoSV);
            p->next = NULL;
            *n++;
        }else{
            //Thuc hien tao cac phan tu tiep theo cua danh sach
            //Den khi nguoi dung khong nhap nua
            p->next=(sinhVien*)malloc(sizeof(sinhVien));
            p=p->next;
            /*printf("Hay nhap ten cua sinh vien nay: ");
            gets(ht);
            if(ht==0){
                break;
            }*/
            strcpy(p->ht,ht);
            printf("Que quan: ");
            gets(p->que);
            printf("Ma so sinh vien: ");
            gets(p->maSoSV);
            p->next = NULL;
            *n++;
        }
    }
    return;
}

//Ham sua thong tin cua mot sinh vien
void suaSV(sinhVien *pdau,int *n)
{
    //Con tro chua vi tri cua sinh vien dang kiem tra
    sinhVien *p;
    int kiemTra=1;
    char ht[20];
    char c;
    printf("Hay nhap ten cua sinh vien can sua thong tin: ");
    gets(ht);
    while(1){
        if(ht==0){
            return;
        }
        if(strcmp(p->ht,ht)==0){
            break;
        }
        if(p->next!=NULL){
            p=p->next;
            kiemTra=1;
        }else{
            kiemTra=0;
            break;
        }
    }
    if(kiemTra=0){
        printf("Khong so sinh vien nao co ten nhu ban vua nhap!");
    }else{
        printf("Ban muon sau thong tin gi cua sinh vien nay:\n\
       Chon 1 de sua ten\n\
       Chon 2 de sua que quan\n\
       Chon 3 de sua ma so sinh vien.");
        c=getch();
        while(c!=kiHieu){
            printf("So ban nhap khong hop le!\n\
           Xin hay nhap lai hoac an 0 de thoat");
        }
        while(c!='0'){
            switch(c){
                case 0:
                    exit(0);
                case 1:
                    printf("Hay nhap ten moi ban muon sua:");
                    gets(p->ht);
                case 2:
                    printf("Hay nhap que moi ban muon sua:");
                    gets(p->que);
                case 3:
                    printf("Hay nhap ma so sinh vien moi:");
                    gets(p->maSoSV);
            }
            printf("Ban muon thuc hien sua thong tin gi nua khong\n\
           Hay chon so tuong ung muon thuc hien hoac an so 0 de thoat");
            c=getch();
        }
    }
}

//Ham them 1 sinh vien vao danh sach
void themSV(sinhVien *pdau,int *n)
{
    sinhVien *p;
    char ht[20];
    printf("Ban hay nhap ten cua sinh vien muon them vao danh sach:");
    gets(ht);
    if(ht==0){
        exit(0);
    }
    p=pdau;
    while(p!=NULL){
        p=p->next;
    }
    p->next=(sinhVien*)malloc(sizeof(sinhVien));
    p=p->next;
    strcpy(p->ht,ht);
    printf("Nhap que cua sinh vien moi: ");
    gets(p->que);
    printf("Nhap ma so cua sinh vien moi: ");
    gets(p->maSoSV);
}

//Ham xoa mot sinh vien trong danh sach
void xoaSV(sinhVien *pdau,int *n)
{
    sinhVien *p=pdau,*luu;
    char ht[20];
    printf("Ban hay nhap ten cua sinh vien can xoa khoi danh sach: ");
    gets(ht);
    if(ht==0){
        exit(0);
    }
    if(pdau==NULL){
        printf("Danh sach khong co ai nen tim kiem khong thanh cong!");
        exit(0);
    }
    while(p!=NULL){
        if(strcmp(p->ht,ht)==0){
            break;
        }else{
            if(p->next!=NULL){
                luu=p;
                p=p->next;
            }else{
                exit(0);
            }
        }
    }
    if(p->next==NULL){
        luu->next=NULL;
    }else{
        luu->next=p->next;
    }
}

//Ham tim kiem 1 sinh vien trong danh sach theo ten
void timSV(sinhVien *pdau,int *n)
{
    sinhVien *p=pdau;
    char ht[20];
    printf("Nhap ten sinh vien ban muon tim trong danh sach: ");
    gets(ht);
    if(pdau==NULL){
        printf("Danh sach chong nen tim kiem khong thuc hien!");
        exit(0);
    }
    while(p!=NULL){
        if(strcmp(p->ht,ht)==0){
            break;
        }else{
            if(p->next!=NULL){
                p=p->next;
            }else{
                printf("Khong co sinh vien nao ten nhu ban vua nhap!");
                exit(0);
            }
        }
    }
    printf("Thong tin cua sinh vien ban vua nhap vao la: ");
    printf("ten: %s \nQue quan: %s\nMa so sinh vien: %s",p->ht,p->que,p->maSoSV);
}

//Ham in ra danh sach cac sinh sien
void inSV(sinhVien *pdau,int *n)
{
    sinhVien *p=pdau;
    printf("%-30s%-30s%-30s\n","Ten sinh vien","Que quan","Ma so sinh vien");
    while(p!=NULL){
        printf("%-30s%-30s%-30s\n",p->ht,p->que,p->maSoSV);
        p=p->next;
    }
}
//End

Danh Sach Lien Ket Don

Ý tưởng: 
Khác với stack, queue danh sách liên kết đơn cũng là một kiểu danh sách tuyến tính gồm các phần tử vào lần lượt theo thứ tự tuy nhiên nó khác stack và queue ở chỗ là nó được cấp phát trong bộ nhớ bởi các phần tử rời rạc nhau, không nằm kề nhau, tuy nhiên giữa phần tử trước thì có 1 liên kết đến phần tử sau nó.
Thông thường thì người ta xây dựng stack, queue bằng mảng, nhưng điểm hạn chế là nó sẽ bị giới hạn về số lượng phần tử, bởi thế cách hay nhất là xây dựng stack, queue bẳng danh sách liên kết đơn ==> stack, queue là 1 danh sách liên kết đơn.

Các thao tác trên danh sách liên kết đơn(single-link list):

Định nghĩa tổng quát

struct tq {
thtin_t phantu;
struc tq*tiep;
};
typedef struct tq tq_t;

Con trỏ tới 1 node

struct  node {
        int infor;
        struct node *next;
    };
    typedef struct node *NODEPTR;

Cấp phát bộ nhớ cho 1 node

NODEPTR Getnode(void) {
    NODEPTR p;
    P = (NODEPTR) malloc(sizeof( struct node));
    Return(p);
}

Giải phóng 1 node

NODEPTR Freenode( NODEPTR p){
        free(p);
    }

Thêm phần tử vào đỉnh danh sách

void Push_Top( NODEPTR *plist, int x) {
    NODEPTR p;
    p= Getnode();
    p -> infor = x;
    p ->next = *plist;
    *plist = p;
}

Thêm node mới vào cuối danh sách

void Push_Bottom( NODEPTR *plist, int x) {
    NODEPTR p, q;
    p= Getnode(); //
    p->infor = x;
    q = *plist;
    while (q-> next != NULL)
        q = q -> next;
   
    q -> next = p;
    p ->next = NULL;
}

Thêm node mới vào giữa danh sách

void Push_Before( NODEPTR p, int x ){
    NODEPTR q;
    if (p->next==NULL)
        Push_Bottom(p, x);
    else {
        q= Getnode();
        q -> infor = x;
        q-> next = p-> next;  
        p->next = q;
    }
}

Xóa 1 node đầu danh sách

void Del_Top( NODEPTR *plist) {
    NODEPTR p;
    p = *plist;
    if (p==NULL) return;
    (*plist) = (*plist) -> next;
    p-> next = NULL;
    Freenode(p);
}

Xóa node cuối danh sách

void Del_Bottom(NODEPTR *plist) {
    NODEPTR p, q;
    if (*plist==NULL) return;
    else if ( (*plist)->next==NULL))
        Del_Top(plist);
    else {
        p = *plist;
        while (p->next!=NULL){
            q = p;
            p = p->next;
        }
        // p lµ node cuèi danh s¸ch;
        q->next =NULL;
        Freenode(p);
    }
}

Xóa node giữa danh sách

void Del_before(NODEPTR p){
    NODEPTR q;
    if (p->next==NULL) return;
    q = p ->next;
    p->next = q->next;
    Freenode(q);
}

Danh Sach Lien Ket

Định nghĩa:
  Trong khoa học máy tính , một danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút với nhau đại diện cho một chuỗi. Dưới hình thức đơn giản, mỗi nút bao gồm dữ liệu và  một liên kết đến nút tiếp theo trong chuỗi các biến thể phức tạp thêm các liên kết bổ sung. Cấu trúc này cho phép chèn hoặc loại bỏ có hiệu quả các yếu tố từ bất kỳ vị trí theo thứ tự.

  Danh sách liên kết là một trong những đơn giản và cấu trúc dữ liệu phổ biến nhất. Chúng có thể được sử dụng để thực hiện một số khác phổ biến dữ liệu trừu tượng các loại , bao gồm cả ngăn xếp , hàng đợi , mảng kết hợp , và các biểu thức tượng trưng , mặc dù nó không phải là phổ biến để thực hiện các cấu trúc dữ liệu khác trực tiếp mà không cần sử dụng một danh sách các cơ sở thực hiện.

  Lợi ích chủ yếu của một danh sách liên kết trong một thông thường mảng là danh sách các yếu tố có thể dễ dàng thêm vào hoặc gỡ bỏ mà không tái phân bổ, tổ chức lại toàn bộ cấu trúc bởi vì các mục dữ liệu không cần phải được lưu trữ liên tục kế nhau trong bộ nhớ hoặc trên đĩa. Danh sách liên kết cho phép chèn và loại bỏ các nút tại bất kỳ điểm nào trong danh sách, và có thể làm như vậy với một số liên tục hoạt động nếu liên kết trước đó để liên kết được thêm vào hoặc gỡ bỏ được duy trì trong danh sách traversal.

Mặt khác, danh sách đơn giản liên kết tự không cho phép truy cập ngẫu nhiên các dữ liệu, hoặc bất kỳ hình thức lập chỉ mục hiệu quả. Vì vậy, nhiều hoạt động cơ bản - như có nút cuối cùng của danh sách (giả định rằng các nút cuối cùng không được duy trì như là tài liệu tham khảo nút riêng biệt trong cấu trúc danh sách), hoặc tìm kiếm một nút có chứa những mốc nhất định, hoặc vị trí nơi mà một nút mới cần được đưa vào có thể yêu cầu quét hầu hết hoặc tất cả danh sách các yếu tố.

Danh sách liên kết được xây dựng năm 1955-1956 bởi Allen Newell , Cliff Shaw và Herbert A. Simon tại RAND Corporation cấu trúc dữ liệu chính cho xử lý ngôn ngữ Thông tin . IPL được sử dụng bởi các tác giả để phát triển trí thông minh nhân tạo một số đầu chương trình, bao gồm cả máy Lý thuyết Logic, Giải quyết vấn đề chung , và cờ tướng máy tính một chương trình. Báo cáo về công việc của họ xuất hiện trong giao dịch IRE thông tin Lý thuyết vào năm 1956, và một số biên bản hội nghị từ 1957 đến 1959, bao gồm Kỷ yếu của Hội nghị máy tính phương Tây chung vào năm 1957 và 1958, và xử lý thông tin (Kỷ yếu đầu tiên UNESCO Hội nghị quốc tế về xử lý thông tin ) vào năm 1959. Sơ đồ cổ điển hiện nay bao gồm các khối đại diện cho các nút danh sách với các mũi tên trỏ đến các nút trong danh sách, xuất hiện trong "Lập trình máy Lý thuyết Logic" của Newell và Shaw trong Proc. WJCC, tháng 2 năm 1957. Newell và Simon đã được công nhận với giải thưởng ACM Turing năm 1975 đã có những đóng góp cơ bản vào trí thông minh nhân tạo, tâm lý của sự nhận thức của con người, và xử lý danh sách ". Các vấn đề của máy dịch thuật ngôn ngữ tự nhiên xử lý đã dẫn Victor Yngve tại Viện Công nghệ Massachusetts (MIT) để sử dụng danh sách liên kết cấu trúc dữ liệu trong ngôn ngữ lập trình COMIT của mình cho nghiên cứu máy tính trong lĩnh vực ngôn ngữ học . Một báo cáo về ngôn ngữ này mang tên "Một ngôn ngữ lập trình cho dịch cơ học" xuất hiện trong dịch cơ khí vào năm 1958.

LISP , đứng cho bộ xử lý danh sách, được tạo ra bởi John McCarthy vào năm 1958 trong khi ông tại MIT và vào năm 1960, ông xuất bản thiết kế của nó trong một bài báo trong truyền thông của ACM , mang tên "đệ quy Chức năng của biểu thức tượng trưng và tính toán của họ bằng máy, phần I ". Một trong những cấu trúc dữ liệu lớn của LISP là danh sách liên kết. Đầu những năm 1960, các tiện ích của cả hai danh sách liên kết và ngôn ngữ sử dụng các cấu trúc dữ liệu chính như đại diện của họ cũng được thành lập. Bert xanh của Phòng thí nghiệm Lincoln MIT xuất bản một bài báo mang tên "ngôn ngữ máy tính cho các thao tác biểu tượng" trong giao dịch IRE trên yếu tố con người trong Điện tử tháng 3 năm 1961 trong đó tóm tắt những lợi thế của phương pháp tiếp cận danh sách liên kết. Một bài báo sau đó, "So sánh các ngôn ngữ máy tính xử lý danh sách" Bobrow và Raphael, xuất hiện trong Truyền thông của ACM vào tháng Tư năm 1964.

Một số hệ điều hành được phát triển bởi các hệ thống tư vấn kỹ thuật (ban đầu của West Lafayette Indiana, và sau đó Chapel Hill, Bắc Carolina) đã sử dụng danh sách đơn lẻ liên kết như các cấu trúc tập tin. Một mục nhập thư mục chỉ cho khu vực đầu tiên của một tập tin, và một phần thành công của tập tin được đặt con trỏ đi qua. Hệ thống sử dụng kỹ thuật này bao gồm Flex ( 6800 Motorola CPU), mini-Flex (cùng CPU), và Flex9 (cho Motorola 6809 CPU). Một biến thể được phát triển bởi TSC và tiếp thị bởi khói tín hiệu phát thanh truyền hình tại California, đã sử dụng danh sách liên kết kép trong cùng một cách thức.

  TSS/360 điều hành hệ thống, phát triển bởi IBM cho hệ thống 360/370 máy, sử dụng một danh sách liên kết đôi cho danh mục hệ thống tập tin của họ. Cấu trúc thư mục tương tự như Unix, một thư mục có thể chứa các tập tin và / hoặc thư mục khác và mở rộng đến chiều sâu nào. Một trời tiện ích được tạo ra để sửa chữa vấn đề hệ thống tập tin sau khi một tai nạn, kể từ khi phần sửa đổi của các cửa hàng của tập tin đôi khi trong bộ nhớ khi một vụ tai nạn xảy ra. Vấn đề đã được phát hiện bằng cách so sánh những liên kết về phía trước và lạc hậu nhất quán. Nếu một liên kết chuyển tiếp là tham nhũng, sau đó nếu một liên kết ngược trở lại, các nút bị nhiễm bệnh đã được tìm thấy, liên kết chuyển tiếp được thiết lập để các nút với các liên kết ngược. Một bình luận hài hước trong mã nguồn mà tiện ích này được gọi nói "Mọi người đều biết một cổ áo trời được thoát khỏi lỗi ở mèo".

  Khái niệm về một danh sách liên kết có thể được giải thích bằng một phép loại suy đơn giản để hộp bưu điện thế giới thực . Giả sử Alice là một gián điệp người muốn cung cấp cho một codebook cho Bob bằng cách đặt nó trong một hộp bưu điện và sau đó cho anh ta chìa khóa. Tuy nhiên, cuốn sách là quá dày để phù hợp với một hộp văn phòng bài duy nhất, do đó, thay vì chia cuốn sách thành hai nửa và mua hai hộp văn phòng bài. Trong ô đầu tiên, bà đặt một nửa đầu tiên của cuốn sách và một chìa khóa để vào ô thứ hai, và trong hộp thứ hai, cô đặt một nửa thứ hai của cuốn sách. Bà ta đưa cho Bob một chìa khóa để các hộp đầu tiên. Không có vấn đề lớn của cuốn sách, chương trình này có thể được mở rộng cho bất kỳ số lượng các hộp bằng cách luôn luôn đặt chìa khóa vào hộp tiếp theo trong hộp trước.

Trong tương tự này, các ô tương ứng với các yếu tố hoặc các nút, các phím tương ứng để con trỏ, và chính cuốn sách là các dữ liệu. Chìa khóa cho Bob là con trỏ đầu, trong khi những người được lưu trữ trong các hộp là con trỏ tiếp theo. Đề án như mô tả ở trên là một danh sách đơn lẻ liên kết (xem dưới đây). 

Các lọai DSLK:
 Danh sách vòng tròn :Trong các nút cuối cùng của một danh sách, các lĩnh vực liên kết thường có chứa một tham chiếu null, một giá trị đặc biệt được sử dụng để chỉ ra thiếu các nút tiếp tục. Một quy ước ít phổ biến hơn là để làm cho nó trỏ đến nút đầu tiên của danh sách, trong trường hợp đó, danh sách được cho là tròn hoặc tròn liên kết, nếu không nó được cho là cởi mở hay tuyến tính.

 Danh sách liên kết đơn: Danh sách đơn lẻ liên kết có chứa các nút có một trường dữ liệu cũng như các lĩnh vực tiếp theo, mà chỉ vào nút tiếp theo trong danh sách liên kết.

 Danh sách liên kết kép : trong một danh sách liên kết kép , mỗi nút chứa, bên cạnh các liên kết nút tiếp theo, một  liên kết thứ hai trỏ đến nút trước đó trong chuỗi. Hai liên kết có thể được gọi là phía trước (s) và sau, hoặc tiếp theo và trước (ious).

Cai Dat Cac Thuat Toan Sap Xep

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<dos.h>

//Khai bao so phan tu & kieu cua no
const Max_Size=100;
float a[100];
int n;

//Tao Menu chon
void menu()
{
 cout<<"\n   Hay Chon Chuc Nang:"<<endl;
 cout<<"\n 1.Nhap Du Lieu"<<endl;
 cout<<"\n 2.Tim Kiem Bang PP LinearSeach"<<endl;
 cout<<"\n 3.Tim Kiem Bang PP BinarySearch"<<endl;
 cout<<"\n 4.Sap Xep Bang PP InsertionSort"<<endl;
 cout<<"\n 5.Sap Xep Bang PP SelectionSort"<<endl;
 cout<<"\n 6.Sap Xep Bang PP InterchangeSort"<<endl;
 cout<<"\n 7.Sap Xep Bang PP BubbleSort"<<endl;
 cout<<"\n 8.Sap Xep Bang PP ShakerSort"<<endl;
 cout<<"\n 9.Sap Xep Bang PP HeapSort"<<endl;
 cout<<"\n 10.Sap Xep Bang PP BInsertionSort"<<endl;
 cout<<"\n 11.Sap Xep Bang PP ShellSort"<<endl;
 cout<<"\n 12.Sap Xep Bang PP QuickSort"<<endl;
 cout<<"\n 13.Sap Xep Bang PP MergeSort"<<endl;
 cout<<"\n 14.Sap Xep Bang PP RadixSort"<<endl;
 cout<<"\n 15.Giai Thoat"<<endl;
 cout<<"\n Chon (1->15): ";
}

//Xac lap vung gioi han chon
int chon_menu()
{
   int ch;
   cin>>ch;
   if ((ch >= 1) && (ch <= 15)) return ch;
   else  
return -1;
}

//Thuat toan tim kiem tuyen tinh
int LinearSearch(float a[],int n,int x)
{
 int i=1;
 while((i<n)&&(a[i]!=x)) i++;
 if(a[i]==x) return i;
 else return -1;
}

//Thuat toan tim kiem nhi phan
int BinarySearch( float a[], int n, int x)
{
 int l=1,r=n,mid;
 do
  {
   mid=(l+r)/2;
   if(x==a[mid]) return mid;
   else if(x<a[mid]) r=mid-1;
   else l=mid+1;
  }
   while(l<=r);
   return -1;
}

// Thuat toan sap xep chen truc tiep
void InsertionSort(float a[],int n)
{
 float temp;
 for(int i=2;i<=n;i++)
  {
   temp=a[i];
   int vt=i;
   while ((a[vt-1]>temp)&&(vt>1))
    {
     a[vt]=a[vt-1];
     vt=vt-1;
    }
   a[vt]=temp;
  }
}

//Thuat toan sap xep chon truc tiep
void SelectionSort(float a[],int n)
{
 int min;
 float temp;//la chi so phan tu nho nhat
 for(int i=1;i<=n-1;i++)
  {
   //tim phan tu nho nhat ben phai a[i], tu [a[i]+1->a[n]
   min=i+1;
   for(int j=i+2;j<=n;j++)
   if(a[j]<a[min])min=j;
   if(a[min]<a[i])
    {
     temp=a[i];
     a[i]=a[min];
     a[min]=temp;
    }
  }
}

//Thuat toan sap xep doi cho truc tiep
void InterChangeSort(float a[],int n)
{
 float temp;
 for(int i=1;i<n;i++)
 for(int j=i+1;j<=n;j++)
 if(a[i]>a[j])
  {
   temp=a[i];
   a[i]=a[j];
   a[j]=temp;
  }
}

//Thuat toan sap xep bang pp noi bot
void BubbleSort(float a[],int n)
{
 float temp;
 for(int i=1;i<n;i++)
 for(int j=n;j>i;j--)
 if(a[j]<a[j-1])
  {
   temp=a[j];
   a[j]=a[j-1];
   a[j-1]=temp;
  }
}

//Thuat toan sap xep bang pp ShakerSort
void ShakerSort(float a[],int n)
{
 int l=1,r=n,k=n;
 float  temp;
 while (l<r)
  {
   for(int j=r;j>l;j--)
   if(a[j]<a[j-1])
    {
     temp=a[j];
     a[j]=a[j-1];
     a[j-1]=temp;
     k=j;
    }
   l=k;
   for(j=l;j<r;j++)
   if(a[j]>a[j+1])
    {
    temp=a[j];
    a[j]=a[j+1];
    a[j+1]=temp;
    k=j;
    }
   r=k;
  }
}

/* Thuat toan sap xep bang pp HeapSort
  1.Chinh Heap */
void ShiftHeap(float a[],int l,int r)
{
 int i,j;
 float x;
 i=l;
 j=2*i;
 x=a[i];
 while(j<=r)
  {
   if(j<r)
   if(a[j]<a[j+1])
   j=j+1;
   if(a[j]<x)break;
   else
    {
     a[i]=a[j];
     a[j]=x;
     i=j;
     j=2*i;
    }
  }
}
// 2.Tao Heap
void CreateHeap(float a[],int n)
{
 int l;
 l=n/2;//a[1] la phan tu ghep them
 while(l>0)
  {
  ShiftHeap(a,l,n);
  l=l-1;
  }
}
// 3.Sap Xep Tren Heap
void HeapSort(float a[],int n)
{
 int r;
 float temp;
 CreateHeap(a,n);
 r=n;// la vi tri dung cho phan tu nho nhat
 while(r>0)
  {
   temp=a[1];
   a[1]=a[r];
   a[r]=temp;
   r=r-1;
   ShiftHeap(a,1,r);
  }
}

//Thuat toan sap xep chen nhi phan
void BInsertionSort(float a[],int n)
{
 int l,r,m;
 float  x; //luu gia tri a[i] tranh bi ghi de khi doi cho cac phan tu
 for(int i=2;i<=n;i++)
  {
   x=a[i];
   l=1;
   r=i-1;
   while(i<=r) //tim vi tri can chen
    {
     m=(l+r)/2; //tim vi tri thich hop m
     if(i<m) r=m-1;
     else l=m+1;
    }
   int vt=i;
   while((a[vt-1]>x)&&(vt>1))
    {
     a[vt]=a[vt-1];
     vt=vt-1;
    }
   a[vt]=x;
  }
}

//Thuat toan sap xep bang pp ShellSort
void ShellSort(float a[],int n,int k)
{
 int step,i,j;
 float x;
 for(step=1;step<=k;step++)
  {
    for(i=1;i<=n;i++)
     {
      x=a[i];
      j=i-1;
      while((x<a[j])&&(j>=1))
       {
    a[j+1]=a[j];
    j=j-1;
       }
      a[j+1]=x;
     }
   }
}

//Thuat toan sap xep bang pp QuickSort
void QuickSort(float a[],int l,int r)
{
 int i,j;
 float x;
 i=l;
 j=r;
 x=a[(l+r)/2];
 do
  {
   while (a[i]<x)i++;
   while(a[j]>x)j--;
   if(j<=j)
    {
     if(i<j)
      {
       float temp=a[i];
       a[i]=a[j];
       a[j]=temp;
      }
   i++;
   j--;
     }
   }
   while(i<j);
   if(l<j)QuickSort(a,l,j);
   if(i<r)QuickSort(a,i,r);
}

//Tao Merge
void Merge(float a[],int first,int mid,int last)
{
 int first1=first;
 int last1=mid;
 int first2=mid+1;
 int last2=last;
 int i=first1;
 float temp[Max_Size];
 for(i=first1;first1<=last1&&first2<=last2;i++)
   {
    if(a[first1]<a[first2])
     {
      temp[i]=a[first1];
      first1++;
     }
    else
     {
      temp[i]=a[first2];
      first2++;
     }
   }
 for(;first1<=last1;first1++,i++) temp[i]=a[first1];
 for(;first2<=last2;first2++,i++) temp[i]=a[first2];
 for(i=first;i<=last;i++) a[i]=temp[i];
}

// Sap Merge
void MergeSort(float a[],int first,int last)
{
 if(first<last)
  {
   int mid=(first+last)/2;
   MergeSort(a,first,mid);
   MergeSort(a,mid+1,last);
   Merge(a,first,mid,last);
  }
}

//Tao lo cho tung phan tu cua day
int GetDigit(unsigned long n,int k)
{
 switch(k)
 {
  case 0: return (n%10);
  case 1: return ((n/10)%10);
  case 2: return ((n/100)%10);
  case 3: return ((n/1000)%10);
  case 4: return ((n/10000)%10);
  case 5: return ((n/100000)%10);
  case 6: return ((n/1000000)%10);
  case 7: return ((n/10000000)%10);
  case 8: return ((n/100000000)%10);
  case 9: return ((n/1000000000)%10);
 }
 return n; //Tra ve gia tri neu khong thuoc lo nao
}

//Tron lo & Sap lai lo thanh day moi
void RadixSort(float a[],int n,int m)
{
 int i,j=1,k=0;
 float  temp[Max_Size];
 do
  {
   for(int lo=0;lo<=9;lo++) //lo duoc don tu 0->9
   for(int i=1;i<=n;i++) // so phan tu duoc quet lai toan bo theo lo
    {
     int n=GetDigit(a[i],k);
     if(lo==n)
      {
       temp[j]=a[i];
       j++;
      }
    }
   j=1;
   for(i=1;i<=n;i++) a[i]=temp[i];
   k=k+1;
  }
 while(k<=m);
}



//Thu tuc vao phan tu mang
void input(float a[],int n)
{
 int i;
 for (i = 1; i <= n; i++)
  {
   cout<<"\n Nhap phan tu: a["<<i<<"]= ";
   cin>>a[i];
  }
}

// Thu tuc in ra phan tu mang
void output(float a[],int n)
{
  int i;
  for (i = 1; i <= n; i++)
      cout<<a[i]<<"  ";
}

//Chuong trinh chinh
void main()
{
 int x,vt;
 int chon;

 do
  {
   menu();
   chon = chon_menu();
   switch(chon)
    {
     case 1:
         
          cout<<"Hay nhap vao so phan tu : n=";
          cin>>n;
          cout<<endl;
 cout<<"\n";
          if(n>0)
          {
          input(a,n);
          cout<<"\n Day vua nhap la: ";
          output(a,n);
          }
          else cout<<endl<<"Khong hop le !...Quay ve Menu !";
         
          break;



      case 2:          
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\n---Tim kiem theo PP LinearSearch---";
          cout<<endl;
          cout<<"\nNhap phan tu can tim: ";
          cin>>x;
       
          vt = LinearSearch(a,n,x);
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          if (vt ==-1) cout<<endl<<"\nKhong co phan tu can tim !";
          else
        {
         cout<<endl<<"Co phan tu can tim !"<<endl;
         cout<<endl<<"La so: "<<x;
         cout<<endl<<"\nTai vi tri thu: "<<vt;
        }
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
       
          break;

      case 3:
       
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\n---Tim kiem theo PP BinarySearch---";
          cout<<endl;
          cout<<"\nNhap phan tu can tim: ";
          cin>>x;
       
          cout<<endl;
          vt = BinarySearch(a,n,x);
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          if (vt == -1) cout<<endl<<"\nKhong co phan tu can tim !";
          else
           {
         cout<<endl<<"Co phan tu can tim !"<<endl;
         cout<<endl<<"La so: "<<x;
         cout<<endl<<"\nTai vi tri thu: "<<vt;
        }
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
       
         
          break;

      case 4:
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP InsertionSort:"<<endl;
          cout<<endl;
          InsertionSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
         
          break;

      case 5:
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP SelectionSort:"<<endl;
          cout<<endl;
          SelectionSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
       
         
          break;

      case 6:
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP InterchangerSort:"<<endl;
          cout<<endl;
          InterChangeSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
         
         
          break;

      case 7:
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP BubbleSort:"<<endl;
          cout<<endl;
          BubbleSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
         
          break;

      case 8:
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP ShakerSort:"<<endl;
          cout<<endl;
          ShakerSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
       
       
          break;

      case 9:
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP HeapSort:"<<endl;
          cout<<endl;
          HeapSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
       
          break;

      case 10:
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP BInsertionSort:"<<endl;
          cout<<endl;
          BInsertionSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";  
         
          break;

      case 11:
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP ShellSort:"<<endl;
          cout<<endl;
          ShellSort(a,n,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";        
          break;

      case 12:
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP QuickSort:"<<endl;
          cout<<endl;
          QuickSort(a,1,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
       
          break;

      case 13:
          if(n>0)
          {
          cout<<" Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\n Sap xep theo PP MergeSort:"<<endl;
          cout<<endl;
          MergeSort(a,1,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";      

         
          break;

      case 14:

          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\n Sap xep theo PP RadixSort:"<<endl;
          cout<<endl;
          RadixSort(a,n,4);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";        

          break;


 case 15:        
          exit(1);
    }
   }
   while (1);
}

Thuat Toan Shaker Sort

Ý tưởng:
Thuật toán Shaker Sort là cải tiến của Bubble Sort bằng cách thực hiện 2 lượt đi và về cùng lúc. Lượt đi sẽ đẩy các phần tử nhỏ về đầu dãy, lượt về sẽ đẩy các phần tử lớn về cuối dãy.
Thuật toán:

Bước 1:
Khởi tạo: l=0; r = N-1;//từ l đến r là đoạn cần được sắp xếp
K=N-1; //ghi nhận lại vị trí l xảy ra hoán vị sau cùng để làm cơ sở
thu hẹp đoạn l đến r
Bước 2:
Bước 2a: j = r;//đẩy phần tử nhỏ nhất về đầu mảng
Trong khi (j>l)
Nếu a[j] < a[j-1]:
a[j]↔ a[j-1];
k=j;//lưu lại nơi xảy ra hoán vị
j = j-1;
l=k;//loại bớt phần tử đã có thứ tự ở đầu dãy

Bước 2:

b: j=l; // đẩy phần tử lớn về cuối mảng

Trong khi (j<r)
Nếu a[j]>a[j+1]:
a[j]↔ a[j+1];
k=j;//lưu lại nơi xảy ra hoán vị
j=j+1;
r=k;//loại bớt phần tử đã có thứ tự ở cuối dãy
Bước 3: 
Nếu l < r : lặp lại bước 2.
Ví dụ:







Cài đặt:

void ShakerSort(int a[], int N)
{
   int i, k, left, right;
   k = 0;
   left = 0;
   right = N - 1;
   while (left < right) {
       for (i = right; i > left; i--)
           if (a[i] < a[i - 1]) {
               Swap(a[i], a[i - 1]); // Hoan vi a[i], a[i - 1]
               k = i; // Dung bien k danh dau de bo qua doan da co thu tu.
           }
       left = k;
       for (i = left; i < right; i++)
           if (a[i] > a[i + 1]) {
              Swap(a[i], a[i + 1]);
              k = i;
          }
      right = k;
   }
}

Thuat Toan HeapSort

Ý tưởng:
Để tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp đã không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Phương pháp Heap Sort khắc phục được nhược điểm này.
 Giả sử xét trường hợp sắp xếp tăng dần, khi đó Heap được định nghĩa là một dãy các phần tử al,..,ar thoã các quan hệ sau với mọi  i  thuộc (r,l)
 ai , a2i
 ai  ,  a2i+1      (ai,a2i), (ai,a2i+1) là các cặp phần tử liên đới
o   Tính chất của heap:
 Tính chất 1: Nếu al,.,ar là một Heap thì khi cắt bỏ một số phần tử ở hai đầu của Heap thì dãy con còn lại vẫn là một Heap .
 Tính chất 2: Nếu các phần tử a1,..,an là một Heap thì phần tử a1 (đầu heap) luôn là  phần tử lớn nhất trong Heap.
 Tính chất 3: Mọi dãy al,al+1,…,ar với  2l > r là một Heap
Thuật toán:
  Giai đoạn 1:    Hiệu chỉnh dãy số ban đầu thành Heap
Giai đoạn 2:    Sắp xếp dãy số dựa trên Heap
o   Bước 1:Đưa phần tử lớn nhất về vị trí đứng ở cuối dãy
  r = n;
 Hoán vị (a1,ar)
o   Bước 2: Loại bỏ phần tử lớn nhất ra khỏi Heap r=r-1;
  Hiệu chỉnh phần còn lại của dãy từ al đến ar thành một Heap.
o   Bước 3:Nếu r >1 ( heap còn phần tử) : lặp lại bước 2
  Ngược lại: dừng
o   Dựa vào tính chất 3, ta có thể thực hiện giai đoạn 1 bằng cách bắt đầu từ heap mặc nhiên an/2+1, an/2+2,…,an,  lần lượt thêm vào các phần tử an/2, an/2-1,…,a1. ta sẽ nhận được Heap theo mong muốn. Như vậy giải đoạn 1 tương đương với n/2 lần thực hiện bước 2 của giai đoạn 2.
o   Cài đặt
o   Để cài đặt Heap sort cần xây dựng một số thủ tục phụ trợ:
1. Thủ tục hiệu chỉnh một dãy al,ar thành heap
o   Giả sử có al,al+1,…ar, trong đó đoạn al+1,…ar, đã là một heap.  ta cần xây dựng al,al+1,…,ar thành một heap. để làm điều này ta lần lượt xét quan hệ của một phần tử ai nào đó với các phần tử liên đới của nó trong dãy là a2i và a2i+1,  nếu nó vi phạm quan hệ của heap  thì đổi chổ ai với phần tử liên đới thich hợp của nó – việc đổi này có thể gây phản ứng dây chuyền.
2. Hiệu chỉnh ao,..,an-1 thành heap.
  Cho một dãy bất kỳ al,…,ar ,  theo tính chất 3 ta có dãy an/2+1, an/2+2,…,an đã là một heap. Ghép thêm phần tử an/2  vào bên trái của heap hiện hành và hiệu chỉnh lại dãy an/2,an/2+1,..,ar thành heap.

Ví dụ:

Ví dụ:  Cho dãy : 15 , 19 , 10 , 7 , 17 , 16

 Giai đoạn 1: tạo heap: i= [0+length]/2=[0+5]/2=2,  (ai , a2i)

 (ai  ,  a2i+1) trong đó: (ai,a2i), (ai,a2i+1) là các cặp phần tử liên đới, nếu thỏa thì i=i-1, không thi hoán vị (ai,a2i+1).

Giai đoạn 2: Sắp xếp dựa trên heap, phần tử đầu heap lớn nhất dãy, trong quá trình sx nếu mảng không còn là heap thì phải hiệu chỉnh lại

Cài đặt:
void heap_sort(int a[], int n)
{
int i,j,size=n-1,k,tg,tg2;
//Gioi han dan cac phan tu van vun
while(size>0)
{
k=(int)(size-1)/2; //Vun cac phan tu mang thanh dong
while(k>=0)
{
i=k; //Vun phan tu lon nhat len nut tren
while(i*2<size)
{
j=2*i+1;
if ((j+1<=size)&&(a[j]<a[j+1])) //***
j=j+1;
if (a[i]<a[j]) //***
{
tg=a[i];
a[i]=a[j];
a[j]=tg;
i=j;
}
else break;
}
k--;
}
tg2=a[0];
a[0]=a[size];
a[size]=tg2;
size--;
}
}
Đây là trang Web về các thuật toán rất hay

Thuat Toan MergeSort

Ý tưởng:
Merge sort chia danh sách dữ liệu  cần được sắp xếp thành hai nữa bằng nhau, và đặt chúng vào các vùng chứa  dữ liệu riêng biệt (list, array,…). Mỗi mảng dữ liệu được sắp xếp một  cách đệ quy, sau đó trộn lẫn vào nhau tạo thành danh sách dữ liệu được  sắp xếp cuối cùng. Giống như hầu hết các phương pháp sắp xếp đệ quy,  Merge sort có độ phức tạp là O(n log n).
Cách triển khai cơ bản của Merge sort là dùng ba mảng dữ liệu – mỗi mảng  để chứa mổi nữa của tập dữ liệu cần sắp xếp và một mảng chứa danh sách  được sắp xếp cuối cùng. Thuật toán được giới thiệu sau đây trộn các mảng  lại thành một, vì vậy chỉ sử dụng hai mảng cho toàn bộ quá trình xử lý.  Hiện nay cũng tồn tại phiên bản không đệ quy của Merge sort, nhưng  chúng không thu được bất kì một cải tiến tốc độ nào so với phiên bản đệ  quy qua thử nghiệm trên hầu hết các kiến trúc xử lý.
Merge sort thì nhanh hơn một ít so với Heap sort với các tập dữ liệu  lớn, nhưng nó đòi hỏi 2 lần bộ nhớ so với Heap sort vì vậy nó không được  ưa chuộng trong việc triển khai ứng dụng dù cho mục đích là gì – Quick  sort là lựa chọn tốt hơn cho thời gian và Heap sort thì lại là lựa chọn  tốt hơn với các tập dữ liệu rất lớn.
Giống như Quick sort, Merge sort là phương pháp dựa trên đệ quy, điều  này khiến nó sẽ là lựa chọn tồi với các ứng dụng chạy trên máy tính bị  giới hạn về bộ nhớ.
Thuật giải:

- Ta xem dãy cần sắp xếp có N phần tử là N đoạn và mỗi đoạn đã được sắp xếp là dãy tăng dần rồi (Tất nhiên vì chỉ mỗi đoạn chỉ có 1 phần tử).
- Sau đó ta trộn 2 đoạn liên tiếp nhau để tạo thành các đoạn có độ dài bằng 2 sao cho mỗi đoạn đã được sắp xếp tăng dần.
- Và tiếp tục cứ trộn 2 đoạn liên tiếp, ta sẽ được những đoạn có độ dài lớn hơn và đồng thời số đoạn trong dãy cũng sẽ ít đi... và cho tới khi chỉ còn lại 1 đoạn duy nhất là dãy đã được sắp xếp tăng dần.
Ví dụ:  Cho dãy : 38 , 27 , 43 , 3 , 9 , 82  , 10

Ví dụ:   Cho dãy: 6 , 5 ,  3 , 1 , 8 ,  7 ,  2 ,  4

Cài dặt:

void merge(int a[],int k1,int k2,int k3)
{
int i,j,z,t[100];
i=k1;
j=k2;
z=k1;
// Tron phan tu
// So sanh cac phan tu de dua vao day T
while((i<k2)&&(j<=k3))
{
if (a[i]<=a[j]) //***
{
t[z]=a[i];
i++;
}
else
{
t[z]=a[j];
j++;
}
z++;
}
// Gan cac phan tu con lai cua day (k1->k2-1) vao day T (neu con)
if(i>=k2)
while (z<=k3)
{
t[z]=a[j];
j++;
z++;
}
// Gan cac phan tu con lai cua day (k2->k3) vao day T (neu con)
if (j>k3)
while (z<=k3)
{
t[z]=a[i];
i++;
z++;
}
// Sao chep day T vao day A
for(z=k1;z<=k3;z++)
a[z]=t[z];
}