Sắp xếp chèn – Du Học Trung Quốc 2023 – Wiki Tiếng Việt

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 a 1 , . . . , a k {\displaystyle a_{1},…,a_{k}}  . 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 a 1 , . . . , a k − 1 {\displaystyle a_{1},…,a_{k-1}}   đã được sắp. Để sắp xếp phần tử a k = x {\displaystyle a_{k}=x}   ta tìm vị trí thích hợp của nó trong dãy a 1 , . . . , a k − 1 {\displaystyle a_{1},…,a_{k-1}}  . 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ử ≤xVị trí thích hợpCác phần tử>xCác phần tử chưa sắp

a 1 {\displaystyle a_{1}}

 …

a i − 1 {\displaystyle a_{i-1}}

 x

a i + 1 {\displaystyle a_{i+1}}

 …

a k − 1 {\displaystyle a_{k-1}}

 

a k + 1 {\displaystyle a_{k+1}}

 …

a n {\displaystyle a_{n}}

 

Ví dụ

Cho danh sách

137-6425

Danh sách con gồm 3 phần tử bên trái 1,3,7 đã được sắp. Để tiếp tục sắp xếp phần tử thứ tư a 4 = 6 {\displaystyle a_{4}=6}   vào danh sách con đó, ta tìm vị trí thích hợp của nó là sau 3 và trước 7.

1367-425

Làm tiếp theo với a 5 = 4 {\displaystyle a_{5}=4}   ta được

13467-25

Làm tiếp theo với a 6 = 2 {\displaystyle a_{6}=2}   ta được

123467-5

Cuối cùng chèn a 7 = 5 {\displaystyle a_{7}=5}  

1234567-

Giải thuật

• Danh sách a bắt đầu từ chỉ số 1 tới length

Procedure insert (array a, int k, value) {   int i:= k-1;  while (i > 0 and a[i] > value) {    a[i+1]:= a[i];    i:= i - 1;  }  a[i+1]:= value;}

Procedure InsertSort (array a, int length) {  int k:= 2;  while (k < length) {    insert(a, k, a[k]);    k:= k + 1;  }}

// Mã giả viết bằng ngôn ngữ C++

void InsertSort (int a[],int n){    int t,j;    for(int i=1;i<n;i++)    {       j=i-1;       t=a[i];       while(j >= 0 && t < a[j])       {           a[j+1]=a[j];           j--;       }       a[j+1]=t; // Chèn    }  }

Đánh giá

• Thuật toán sử dụng trung bình n2/4 phép so sánh và n2/4 lần hoán vị, n2/2 phép so sánh và n2/2 lần hoán vị trong trường hợp xấu nhất, n-1 phép so sánh và 0 lần hoán vị trong trường hợp tốt nhất.
• Thuật toán thích hợp đối với mảng đã được sắp xếp một phần hoặc mảng có kích thước nhỏ.

Xem thêm

Tham khảo

Liên kết