[Thuật toán] Các thuật toán sắp xếp trong lập trình C- Thuật toán sắp xếp chèn

Bubble sort. (Nổi bọt, nổi bong bóng)

Quick sort. (Sắp xếp nhanh)

Simple selection sort. (Sắp xếp chọn)

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.
Thuật toán:
Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu . Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu  đã được sắp. Để sắp xếp phần tử ta tìm vị trí thích hợp của nó trong dãy . Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

Các phần tử ≤x			Vị trí thích hợp	Các phần tử>x			Các phần tử chưa sắp
	...		x		...			...

Mô tả thuật toán sắp xếp chèn

Thuật toán viết bằng C++ : 

Code:
#include <iostream>
using namespace std;
void insertion_sort(int a[], int n)
{
     int i,tg,x;
     for (i=1;i<n;i++)
      {
        tg=a[i];
        x=i-1;
        while((x>=0)&&(a[x]>tg))
            {
            a[x+1] = a[x];
            x--;
            }
        a[x+1] =tg;
     }
}
int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep:  ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    insertion_sort(a,n);
    cout<<"Day sau khi sap xep:  ";
    for(int i=0;i<n;i++)
        cout<<a[i] << "  ";}

5.Heap sort. (Sắp xếp vun đống)

6.Simple insertion sort.(Sắp xếp chèn)
7. Shell sort.
8.Merge sort. (Sắp xếp hòa nhập)