Các thuật toán sắp xếp trên mảng trên php năm 2024

Hàm rsort() trong PHP được sử dụng để sắp xếp một mảng theo thứ tự giảm dần dựa trên giá trị của các phần tử.

Cú pháp của hàm rsort() như sau:

rsort(array &$array, int $sort_flags = SORT_REGULAR): bool

Trong đó:

• $array: là mảng cần sắp xếp.
• $sort_flags (tùy chọn): là một hằng số được sử dụng để chỉ định cách sắp xếp. Mặc định là SORT_REGULAR, tương đương với sắp xếp theo thứ tự giảm dần dựa trên giá trị của các phần tử.

Hàm rsort() sẽ sắp xếp lại mảng $array và trả về giá trị boolean

$fruits = array("apple", "banana", "orange", "kiwi");
rsort($fruits);
print_r($fruits);

1 nếu sắp xếp thành công, và

$fruits = array("apple", "banana", "orange", "kiwi");
rsort($fruits);
print_r($fruits);

2 nếu không thành công.

Ví dụ:

$fruits = array("apple", "banana", "orange", "kiwi");
rsort($fruits);
print_r($fruits);

Kết quả:

Array
(
    [0] => orange
    [1] => kiwi
    [2] => banana
    [3] => apple
)

Trong ví dụ trên, hàm rsort() đã sắp xếp mảng

$fruits = array("apple", "banana", "orange", "kiwi");
rsort($fruits);
print_r($fruits);

4 theo thứ tự giảm dần dựa trên giá trị của các phần tử, và in ra kết quả trên màn hình.

Để viết một hàm tương tự như hàm rsort() trong PHP, ta có thể sử dụng thuật toán sắp xếp giải thuật Quicksort để thực hiện việc sắp xếp mảng. Sau đây là một ví dụ về việc viết một hàm sắp xếp giảm dần một mảng sử dụng giải thuật Quicksort:

function quicksort_desc(&$arr, $left = 0, $right = null) {
    if ($right === null) {
        $right = count($arr) - 1;
    }
    if ($left >= $right) {
        return;
    }
    $pivot = $arr[($left + $right) >> 1];
    $i = $left - 1;
    $j = $right + 1;
    while (true) {
        do {
            $i++;
        } while ($arr[$i] > $pivot);
        do {
            $j--;
        } while ($arr[$j] < $pivot);
        if ($i >= $j) {
            break;
        }
        list($arr[$i], $arr[$j]) = array($arr[$j], $arr[$i]);
    }
    quicksort_desc($arr, $left, $j);
    quicksort_desc($arr, $j + 1, $right);
}

Hàm trên sử dụng tham chiếu để sắp xếp trực tiếp trên mảng đầu vào. Giá trị

$fruits = array("apple", "banana", "orange", "kiwi");
rsort($fruits);
print_r($fruits);

6 và

$fruits = array("apple", "banana", "orange", "kiwi");
rsort($fruits);
print_r($fruits);

7 được sử dụng để chỉ định phạm vi của mảng cần sắp xếp. Nếu không được chỉ định, giá trị mặc định của

$fruits = array("apple", "banana", "orange", "kiwi");
rsort($fruits);
print_r($fruits);

7 là phần tử cuối cùng của mảng. Thuật toán sử dụng phương pháp chọn pivot giữa mảng và sử dụng hai biến

$fruits = array("apple", "banana", "orange", "kiwi");
rsort($fruits);
print_r($fruits);

9 và

Array
(
    [0] => orange
    [1] => kiwi
    [2] => banana
    [3] => apple
)

0 để di chuyển các phần tử để đưa các phần tử nhỏ hơn pivot vào bên trái và các phần tử lớn hơn pivot vào bên phải của pivot.

Hàm reset() trong PHP Hàm shuffle() trong PHP

Chắc hẳn bạn vẫn còn khá mông lung với thuật toán, để giúp bạn hiểu rõ hơn, chúng ta hãy cùng đến với một trò chơi "hành quân" sau:

Xét một dãy số như sau:

6,1,2,7,9,3,4,5,10,86, 1, 2, 7, 9, 3, 4, 5, 10, 8

Yêu cầu là sắp xếp dãy trên theo thứ tự không giảm từ trái qua phải.

Chọn phần tử chốt là số 6, xét hai "quân lính" là quân lính AA và quân lính BB lần lượt đặt ở hai đầu của dãy số (quân AA ở vị trí đầu tiên bên trái, quân BB ở vị trí cuối cùng bên phải). Luật hành quân như sau: quân BB đi trước, bắt đầu di chuyển về bên trái, đến khi gặp được phần tử có giá trị nhỏ hơn giá trị của phần tử chốt thì dừng lại, ở đây quân BB dừng ở vị trí của số 55; Tiếp theo đến lượt quần AA, bắt đầu di chuyển về bên phải, đến khi gặp được phần từ có giá trị lớn hơn giá trị của phần tử chốt thì dừng lại, ở đây quân AA dừng ở vị trí số 77. Lúc này ta đổi chỗ 22 số ở vị trí của quân AA và BB cho nhau, sau đó hai quân AA và BB trở về vị trí như lúc đầu, ta thu được dãy số sau:

6,1,2,5,9,3,4,7,10,86, 1, 2, 5, 9, 3, 4, 7, 10, 8

Tiếp tục cuộc hành quân như trên, lượt này ta sẽ cần đổi chỗ hai số 44 và 99 cho nhau, ta được dãy số:

6,1,2,5,4,3,9,7,10,86, 1, 2, 5, 4, 3, 9, 7, 10, 8

Đến với lượt hành quân tiếp theo, ta thấy quân BB sẽ dừng lại ở vị trí của số 33, tuy nhiên quân AA chưa tìm được số nào lớn hơn 66 đã "đụng mặt" quân B, như vậy ta coi lượt hành quân này là thất bại, và ta tiến hành đổi chỗ số 33 (số mà quân BB đang dừng lại) với phần tử chốt là số 66. Ta thu được:

3,1,2,5,4,6,9,7,10,83, 1, 2, 5, 4, 6, 9, 7, 10, 8

Lúc này, chúng ta hãy quan sát phần tử chốt (số 66): sau loạt hành quân đầu tiền thì tất cả những phần tử nằm bên trái phần tử chốt đều nhỏ hơn nó, và tất cả những phần tử nằm bên phải phần tử chốt đều lớn hơn nó. Như vậy ta đã đưa số 66 về đúng vị trí của nó.

Tiếp theo dãy được chia thành 22 dãy nhỏ hơn là dãy bên trái số 66 và dãy bên phải số 66. Ta tiếp tục thực hiện luật hành quân như trên đối với hai dãy này và sẽ thu được thêm các phần tử chốt khác ở đúng vị trí và xuất hiện thêm các dãy con độ dài ngắn hơn. Thực hiện đến cuối ta thu được dãy có thứ tự như mong muốn.

III. Thuật toán tham khảo

• Thuật toán sắp xếp nhanh C++:

void quickSort(int a[], int l, int r){
  int p = a[(l+r)/2];
  int i = l, j = r;
  while (i < j){
    while (a[i] < p){
      i++;
    }
    while (a[j] > p){
      j--;
    }
    if (i <= j){
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
      i++;
      j--;
    }
  }
  if (i < r){
    quickSort(a, i, r);
  }
  if (l < j){
    quickSort(a, l, j);
  }
}

• Thuật toán sắp xếp nhanh Java:

package quick.sort.algo;
public class QuickSort {
    // Hàm nhận phần tử cuối cùng làm chốt,
    // đặt các phần tử nhỏ hơn chốt ở trước
    // và lớn hơn ở sau nó
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1); // index of smaller element
        for (int j = low; j < high; j++) {
            // Nếu phần tử hiện tại nhỏ hơn chốt
            if (arr[j] < pivot) {
                i++;
                // swap arr[i] và arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // swap arr[i+1] và arr[high] (hoặc pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
    // arr[] --> Mảng cần được sắp xếp,
    // low --> chỉ mục bắt đầu,
    // high --> chỉ mục kết thúc
    void sort(int arr[], int low, int high) {
        if (low < high) {
            // pi là chỉ mục của chốt, arr[pi] vị trí của chốt
            int pi = partition(arr, low, high);
            // Sắp xếp đệ quy các phần tử
            // trướcphân vùng và sau phân vùng
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }
    // In các phần tử của mảng
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String args[]) {
        int arr[] = { 10, 80, 30, 90, 40, 50, 70 };
        int n = arr.length;
        System.out.println("Mảng ban đầu:");
        printArray(arr);
        QuickSort ob = new QuickSort();
        ob.sort(arr, 0, n - 1);
        System.out.println("Mảng sau khi sắp xếp:");
        printArray(arr);
    }
}

• Thuật toán sắp xếp nhanh PHP:

function simple_quick_sort($arr)
{
    if(count($arr) <= 1){
        return $arr;
    }
    else{
        $pivot = $arr[0];
        $left = array();
        $right = array();
        for($i = 1; $i < count($arr); $i++)
        {
            if($arr[$i] < $pivot){
                $left[] = $arr[$i];
            }
            else{
                $right[] = $arr[$i];
            }
        }
        return (
            array_merge(simple_quick_sort($left),
            array($pivot), simple_quick_sort($right))
        );
    }
}

IV. Những điều lưu ý về thuật toán

1. Phần tử chốt.

Sau khi hiểu về thuật toán, có lẽ bạn sẽ có một nghi vấn nhỏ nảy lên trong đầu: Tại sao chọn phần tử chốt là phần tử đầu tiên bên trái? Và cách chọn phần tử chốt có ảnh hưởng đến độ nhanh chậm của sắp xếp hay không? Thực tế thì kỹ thuật chọn phần tử chốt ảnh hưởng khá lớn đến thuật toán, bởi chúng ta có khả năng bị rơi vào các vòng lặp vô hạn. Một số cách chọn phần tử chốt để bạn tham khảo: