Ninja IT

Sắp xếp nhanh

Sắp xếp nhanh

Sắp xếp nhanh chọn một khóa và chia mảng thành hai phần với phần bên trái nhỏ hơn khóa, và phần bên phải lớn hơn khóa. Khóa được chọn là một phần tử trong mảng.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * @param arr là array
 * @param left là index ở phía bên trái tính từ 0
 * @param right là index ở phía bên trái tính từ 0, luôn < độ lớn của arr
 */
void quickSort(int* arr, int left, int right) {
  int x = arr[(left + right) / 2];
  int i = left;
  int j = right;
  while (i <= j) {
    while (arr[i] < x) {
      i++;
    }
    while (arr[j] > x) {
      j--;
    }
    if (i <= j) {
      swap(arr, i, j);
      i++;
      j--;
    }
  };

  if (left < j) {
    quickSort(arr, left, j);
  }
  if (i < right) {
    quickSort(arr, i, right);
  }
}
Thuật toán có nhược điểm là phụ thuộc vào cách chọn khóa. Thời gian chạy trung bình của thuật toán là `O(n*log(n))`. Trong trường hợp xấu nhất thời gian chạy của thuật toán là O(n2).