Các thuật toán này có độ phức tạp trung bình là O(N2)
1. Sắp xếp chọn (Selection Sort)
Ý tưởng
- Sắp xếp một mảng bằng cách đi tìm phần tử có giá trị nhỏ nhất (giả sử với sắp xếp mảng tăng dần) trong đoạn chưa được sắp xếp và đổi cho phần tử nhỏ nhất đó với phần tử ở đầu đoạn chưa được sắp xếp (không phải đầu mảng).
- Tại mỗi bước lặp của thuật toán, phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp.
Ưu điểm
- Dễ dàng cài đặt
Nhược điểm
- Không đủ nhanh với dữ liệu lớn
Code minh họa (C#)
// Sắp xếp chọn
void SelectionSort(ref int[] a)
{
int n = a.Length;
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[i] > a[j])
{
// Hoán đổi vị trí a[i] và a[j]
Swap(ref a[i], ref a[j]);
}
}
}
}2. Sắp xếp nổi bọt (Bubble Sort)
Ý tưởng
- Xét lần lượt các cặp 2 phần tử liên tiếp. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước, ta đổi chỗ 2 phần tử. Nói cách khác, phần tử lớn nhất sẽ nổi lên trên (cuối mảng).
- Lặp lại đến khi không còn 2 phần tử nào thỏa mãn. Có thể chứng minh được số lần lặp không quá N−1, do một phần tử chỉ có thể nổi lên trên không quá N−1 lần.
Ưu điểm
- Code đơn giản, dễ hiểu.
- Không tốn thêm bộ nhớ.
Nhược điểm
- Không đủ nhanh với dữ liệu lớn
Code minh họa (C#)
// Sắp xếp nổi bọt
void BubbleSort(ref int[] a)
{
int n = a.Length;
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
// Hoán đổi vị trí a[j] và a[j+1]
Swap(ref a[j], ref a[j + 1]);
}
}
}
}3. Sắp xếp chèn (Insertion Sort)
Ý tưởng
- Ý tưởng chính của thuật toán là ta sẽ sắp xếp lần lượt từng đoạn gồm 1 phần tử đầu tiên, 2 phần tử đầu tiên, …, N phần tử.
- Giả sử ta đã sắp xếp xong ii phần tử của mảng. Để sắp xếp i+1 phần tử đầu tiên, ta tìm vị trí phù hợp của phần tử thứ i+1 và “chèn” nó vào đó.
Ưu điểm
- Nếu danh sách đã gần đúng thứ tự, Insertion Sort sẽ chạy rất nhanh. Ví dụ bạn cần sắp xếp Highscore trong game.
Nhược điểm
- Không đủ nhanh với dữ liệu lớn
Code minh họa (C#)
// Sắp xếp chèn
void InsertionSort(ref int[] a)
{
int n = a.Length;
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
}
}4. Hàm Swap
// Hàm hoán đổi vị trí s1 và s2
static void Swap(ref int s1, ref int s2)
{
int temp = s1;
s1 = s2;
s2 = temp;
}
// Hàm hoán đổi vị trí s1 và s2
// không dùng biến tạm
static void SwapNotTemp(ref int s1, ref int s2)
{
s2 = s1 + s2;
s1 = s2 - s1;
s2 = s2 - s1;
}
quoc9x 