Hướng dẫn các thuật toán tìm kiếm và sắp xếp cơ bản mới nhất 2020

Các thuật toán tìm kiếm là một trong những từ khóa được tìm kiếm nhiều nhất trên google về chủ đề các thuật toán tìm kiếm. Trong bài viết này, coder.com.vn sẽ viết bài Hướng dẫn các thuật toán tìm kiếm và sắp xếp cơ bản mới nhất 2020

Mục Lục

Những thuật toán tìm kiếm :

Tìm kiếm tuyến tính:

Là kiểm duyệt tuần tự từng phần tử của mảng, đến khi nào giống thì thôi.

1
2
3.
4
5
6.
int linearSearch (int a[], int n, int x) 
for (int i = 0; i < n; i++) 
if (a[i] == x) return i; //trả về địa điểm tìm thấy
else return -1; //trả về -1 nếu ko tìm thấy

Tìm kiếm nhị phân:

Điều kiện của thuật toán này là mảng đã được bố trí tăng dần. So sánh x với giá trị của phần tử nằm ở giữa mảng (mid=(left+right)/2). nếu như x nhỏ hơn a[mid] thì nó chỉ có thể nằm ở nửa bên trái, trái lại x lớn hơn a[mid] thì x nằm ở nửa bên phải. chọn lựa x nằm ở nửa nào thì ta lặp lại thuật toán với nửa đó. Như vậy số lần kiểm duyệt giảm đi nhiều do ko phải mất công kiểm tra các phần tử thuộc nửa còn lại.

1
2
3.
4
5
6.
7.
8.
9
10
int binarySearch (int a[], int n, int x) 
int left = 0, right = n - 1, mid;
do
mid = (left + right) / 2
if (a[mid] == x) return mid;
else if (a[mid] <= x) left = mid + 1;
else right = mid - 1;
while (left <= right);
return -1;

Tìm kiếm nội suy:

Là cải tiến của thuật toán tìm kiếm nhị phân. Thay vì chia đôi, thuật toán này chia theo phép tính $\mathrm<span class=$

1
2.
3.
4
5.
6
7.
8.
9
10
int interpolationSearch (int a[], int n, int x) 
int left = 0, right = n - 1, mid;
do
mid = left + (right - left) / (a[right] - a[left]) * (x - a[left]);
if (a[mid] == x) return mid;
else if (a[mid] <= x) left = mid + 1;
else right = mid - 1;
while (left <= right);
return -1;

Những thuật toán sắp xếp :

Bố trí đổi chỗ (interchange sort):

Xuất phát từ đầu dãy, lần lượt so sánh phần tử đầu dãy với các phần tử còn lại, nếu như thấy lớn hơn thì đổi chỗ cho nhau, mục đích là để Khi mà đã quét một lượt, phần tử nhỏ bé nhất sẽ về đầu dãy.

1
2
3
4
5
6.
7
8
9
10
void interchangeSort (int a[], int n) 
for (int i = 0; i < n - 1; i++)
for (j = i + 1; j < n; j++)
if (a[i] > a[j]) swap(a, i, j);
void swap (int a[], int i, int j) 
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;

Độ phức tạp: O(n^2).

Xem thêm: Stored Procedure là gì? Cách viết và sử dụng Stored Procedures hiện nay?

Sắp đặt chọn (selection sort):

Tìm phần tử nhỏ dại nhất trước, rồi mới đổi chỗ nó cho phần tử đầu tiên, xong lặp lại với phần khác.

1
2.
3
4
5.
6.
7
8
9.
10
11
void selectionSort (int a[], int n) 
int min;
int iMin;
for (i = 0; i < n - 1; i++) 
min = a[i];
iMin = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[iMin])  min = a[j]; iMin = j; 
swap(a, iMin, i);

Độ phức tạp: O(n^2).

Số phép so sánh tương tự với sắp xếp đổi chỗ, tuy nhiên số lần hoán vị được giảm đi nhiều.

sắp đặt nổi bọt (bubble sort):

Lần lượt đổi chỗ các cặp đôi phần tử cạnh nhau nếu như chúng ngược thứ tự, mục tiêu cũng là sau một lượt, phần tử bé xíu nhất sẽ về đầu dãy.

1
2.
3
4.
5.
void bubbleSort (int a[], int n) 
for (i = 0; i < n - 1; i++)
for (j = n - 1; j > i; j--)
if (a[j] < a[j - 1]) swap(a, j, j - 1);

Độ phức tạp: O(n^2).

Số phép so sánh , hoán vị tương đương bố trí đổi chỗ.

Thuật toán này có lợi thế là phát hiện được mảng đã được sắp xếp hay chưa, bằng việc kiểm tra xem có phải swap lần nào ko.

Bố trí hỗn hợp (cocktail shaker sort):

Thu thập hình ảnh xóc bình cocktail, biến j có thể chạy 2. chiều, chiều xuôi thì đưa phần tử lớn nhất về cuối dãy, sau đó đảo lại để đưa phần tử bé nhất về đầu dãy.

1
2.
3
4.
5.
6.
7.
8.
9
10
11
void shakerSort (int a[], int n) 
int left = 0, right = n - 1, k = left;
while (left < right) 
for (int i = left; i < right; i++)
if (a[i] > a[i + 1])  swap(a, i, i + 1); k = i; 
right = k;
for (int i = right; i > left; i--)
if (a[i - 1] > a[i])  swap(a, i - 1, i); k = i; 
left = k;

Độ phức tạp: O(n^2).

đây chính là thuật toán cải tiến của sắp đặt nổi bọt nên nó cũng nhận diện được mảng đã sắp xếp. Thuật toán này có lợi thế hơn nổi bọt khi mảng có dải những phần tử đã được sắp xếp.

Sắp xếp chèn (insertion sort):

Chúng ta coi phần bên trái của biến chạy i là phần đã được sắp đặt theo đúng thứ tự (sẽ chuyển dần các phần tử từ mớ hỗn độn ở phần bên phải sang). Tìm vị trí hợp lý trong nửa trái đấy để chèn phần tử a[i] vào cho đúng thứ tự, sau đấy chuyển dịch dần những phần tử bên phải kể từ địa điểm vừa tìm ra để nong thu thập một lỗ trống, rồi mới chèn x (mang giá trị của a[i]) vào.

1
2
3.
4
5.
6
7
8
9
10
11
void insertionSort (int a[], int n) 
int pos, x;
for (int i = 1; i < n; i++) 
x = a[i]; pos = i - 1;
while (pos >= 0 && a[pos] > x) 
a[pos + 1] = a[pos];
pos--;
a[pos + 1] = x;

Độ phức tạp: O(n^2).

Thuật toán này chỉ hợp lý với mảng đã được sắp xếp một phần, còn với mảng ngẫu nhiên thì thuật toán này phế hơn cả sắp xếp nổi bọt do hoán vị quá nhiều.

Chèn nhị phân (binary insertion sort):

Là cải tiến một chút của insertion sort, thay vì tìm địa điểm để chèn một bí quyết tuần tự, ta áp dụng ý tưởng như thuật toán tìm kiếm nhị phân, cứ chia đôi rồi chia đôi.

1
2
3
4
5
6
7.
8
9
10
11
12
13
void binaryInsertionSort (int a[], int n) 
int left, right, mid, x;
for (int i = 1; i < n; i++) 
x = a[i]; left = 0; right = i - 1;
while (left <= right) 
mid = (left + right) / 2
if (x < a[mid]) right = mid - 1;
else left = mid + 1;
for (int j = i - 1; j >= left; j--) a[j + 1] = a[j];
a[left] = x;

Shell sort:

Là cải tiến của insertion sort, chia nhỏ thành nhiều dãy con có độ dài h, sau đấy so sánh từng vị trí tương ứng giữa các đoạn con rồi đổi chỗ cho đúng, ít đi độ dài h lại đến khi bằng 1 thì dừng.

1
2.
3
4
5.
6.
7
8
9
10
11
12
13
14
15
void shellSort (int a[], int n, int h[], int k) 
int i, j, step, x, len;
for (step = 0; step < k; step++) 
len = h[step];
for (i = len; i < n; i++) 
x = a[i];
j = i - len;
while (x < a[j] && j >= 0) 
a[j + len] = a[j];
j -= len;
a[j + len] = x;

Mảng h[] thường hay chứa một dãy số quan trọng, chẳng hạn như như dãy (3n+1), hay dãy các số lẻ (2n+1), ít ai để dãy h ít đi từng đơn vị một, nhằm hạn chế số bước k phải hành động, tăng tốc độ bố trí lên. do đó rất khó lựa chọn độ phức tạp của thuật toán, nó phụ thuộc vào mảng ban đầu và cách chọn những số h.

bố trí nhanh (quick sort):

Chọn phần tử x ở giữa mảng. Tìm ở bên trái của x phần tử nào lớn hơn x, ở bên cần có phần tử nào nhỏ dại hơn x, rồi đổi chỗ 2. phần tử đó. Quét hết lượt thì lặp lại thuật toán với từng nửa. Đến khi nào độ dài các đoạn để quét là 1 thì dừng.

1
2
3.
4.
5
6.
7
8.
9
10
11
12
void quickSort (int a[], int left, int right) 
int i, j, x;
x = a[(left + right) / 2];
i = left; j = right;
do
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j)  swap(a, i, j); i++; j--; 
while (i <= j);
if (left < j) quickSort(a, left, j);
if(i < right) quickSort(a, i, right);

Độ phức tạp trung bình: O( n log(n) ).

Bố trí trộn (merge sort):

Chia đôi dãy thành 2 dãy con bằng hàm mergeSort(). Giả sử rằng mỗi dãy con đã được sắp đặt theo thứ tự, thì giờ chỉ cần trộn hai dãy con với nhau thành một dãy duy nhất bằng hàm merge(). nếu dãy con chưa được sắp đặt thì lại ứng dụng hàm mergeSort() lên dãy con đấy, cứ chia đôi như vậy cho đến khi ko cần phải chia nữa.

Xem thêm: Những ngôn ngữ lập trình trí tuệ nhân tạo c++ phổ biến nhất hiện nay

1
2.
3.
4
5.
6
7.
8
9.
10
11
12
13
14
15
16
17
18
19
2.
2
//trộn 2. dãy con lại với nhau
void merge (int a[], int left, int mid, int right) 
int tmp[right - left + 1];
int i = left, j = mid + 1, pos = 0;
while (i <= mid 
//phân hoạch
void mergeSort (int a[], int left, int right) 
if (left < right) 
int mid = (left + right) / 2.
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);

Thuật toán này có điểm không tốt lớn là vừa tốn bộ nhớ do đệ quy, vừa tốn bộ nhớ do khởi tạo thêm mảng tạm thời làm mảng trộn.

Sắp đặt vun đống (heap sort):

Sở dĩ gọi là vun đống vì mô hình thuật toán có dạng hình như quả núi.

Để dễ gọi hơn, mình gọi là cây phả hệ, mỗi một nốt là bố, mỗi bố có 2. nốt con (ở đây chọn mô hình phân hoạch nhị phân cho dễ), tương tự với các đời con sau.

Bước 1: hiệu chỉnh thành dạng vun đống.

Bước 2. so sánh bố với con. Giả sử bài toán là sắp xếp mảng tăng dần, vậy ta hoán đổi vị trí sao cho thằng lớn hơn lên làm bố. cuất phát từ thế hệ cháu chắt chút chít trước, sau đấy đẩy dần lên thế hệ ông cụ kị, đến sau cuối ta sẽ được thằng to nhất lên chức cụ tổ. Khi cụ tổ đã ở đúng địa điểm của nó trên bàn thờ rồi, ta chỉ việc lặp lại thuật toán với đám con cháu còn lại, cũng hiệu chỉnh thành đống rồi so sánh bố con. Chương trình kết thúc khi đám con cháu hoá ra chỉ còn 1 đứa.

1
2.
3.
4.
5
6
7.
8.
9.
10
11
12
13
14
15
16
17
18
19
2.
2.
2
2
2.
2.
2.
2.
2.
2
3
3.
3
3.
3.
//tìm kiếm , hoán đổi vào khoảng thời gian l đến r
void shift (int a[], int l, int r) 
int x, i, j;
i = l; j = 2. * i + 1; //i trỏ vào bố, j trỏ vào con đầu tiên của bố i
x = a[i];
while (j <= r) 
if( j < r && a[j] < a[j + 1]) j++; //2 đứa con của cùng 1 bố, đứa nào to hơn thì trỏ j về đứa đấy
if (a[j] <= x) return;
else  //nếu thấy con lớn hơn bố, hoán đổi bố con , tăng biến trỏ i, j xuống thế hệ dưới
a[i] = a[j];
a[j] = x;
i = j; j = 2. * i + 1;
x = a[i];
//hàm hiệu chỉnh mảng a thành dạng heap
void createHeap (int a[], int n) 
int l = n / 2 - 1;
while (l >= 0) 
shift(a, l, n - 1);
l--;
void heapSort (int a[], int n) 
createHeap(a, n);
int r = n - 1;
while (r > 0) 
swap(a, 0, r); //đưa cụ về cuối dãy
r--;
if (r > 0) shift(a, 0, r);

Độ phức tạp trung bình: O( n log(n) ).

Có thể bạn quan tâm: Data Science là gì? Vai trò của Data Science trong doanh nghiệp 2020

Nguồn: https://maitroisang.wordpress.com/

Trending Tags

Trending Tags

Hướng dẫn các thuật toán tìm kiếm và sắp xếp cơ bản mới nhất 2020

Những thuật toán tìm kiếm :

Tìm kiếm nhị phân:

Tìm kiếm nội suy:

Những thuật toán sắp xếp :

Bố trí đổi chỗ (interchange sort):

Sắp đặt chọn (selection sort):

Bố trí hỗn hợp (cocktail shaker sort):

Sắp xếp chèn (insertion sort):

Chèn nhị phân (binary insertion sort):

bố trí nhanh (quick sort):

Bố trí trộn (merge sort):

Sắp đặt vun đống (heap sort):

Tổng kết 4 phương pháp rèn luyện tư duy lập trình mới nhất 2020

Top 5 phần mềm tạo game miễn phí mới nhất 2020

CODER

Chuyên mục

Phần mềm - Công cụ

Liên kết