Các bài tập về thuật toán sắp xếp năm 2024

Sắp xếp dữ liệu là một phần không thể thiếu khi bạn học và làm việc về lập trình. Phần này mình sẽ liệt kê 6 giải thuật sắp xếp thông dụng.

Các giải thuật sắp xếp trong PHP

Dưới đây là danh sách các giải thuật sắp xếp trong PHP. Bạn click chuột vào đường link để theo dõi lời giải minh họa cũng như kết quả của bài tập PHP tương ứng.

• Giải thuật sắp xếp nhanh (Quick Sort)
• Giải thuật sắp xếp chèn (Insertion Sort)
• Giải thuật sắp xếp chọn (Selection Sort)
• Giải thuật Shell Sort
• Giải thuật sắp xếp nổi bọt (Bubble Sort)
• Giải thuật sắp xếp trộn (Merge Sort)

Quảng cáo

Các bài tập PHP có giải khác có trên VietJack:

• Mục lục
• Bài tập PHP cơ bản
• Bài tập mảng
• Bài tập vòng lặp for
• Bài tập hàm
• Bài tập Regular Expression
• Bài tập Date Time
• Bài tập String
• Bài tập về Class (Lớp)
• Xử lý JSON trong PHP
• Các thuật toán sắp xếp

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Ngữ pháp tiếng Anh, luyện thi TOEIC, PHP, Java, C, C++, Javascript, HTML, Python, Database, Mobile ... mới nhất của chúng tôi.

Sắp xếp là một trong những thao tác cơ bản mà chúng ta thực hiện trên các đối tượng. Ngay cả khi còn nhỏ, trẻ em được dạy sắp xếp khi chúng phát triển kỹ năng tư duy. Máy tính và phần mềm cũng không ngoại lệ. Có rất nhiều thuật toán sắp xếp trong Java . Tôi khuyên bạn nên kiểm tra chúng là gì và chúng hoạt động như thế nào. Điều gì sẽ xảy ra nếu bạn được hỏi về một trong số họ tại một cuộc phỏng vấn vào một ngày nào đó?

Giới thiệu

Sắp xếp các phần tử là một trong những loại thuật toán mà nhà phát triển phải biết. Nếu khoa học máy tính đã từng không được coi trọng khi tôi còn đi học, thì học sinh ngày nay phải có khả năng thực hiện và hiểu các thuật toán sắp xếp. Các thuật toán cơ bản, đơn giản nhất, được thực hiện bằng vòng lặp for . Đương nhiên, để sắp xếp một tập hợp các phần tử, chẳng hạn như một mảng, bằng cách nào đó bạn cần duyệt qua tập hợp đó. Ví dụ:

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
for (int i = 0; i < array.length; i++) {  
  System.out.println(array[i]);  
}  

Có thể nói gì về đoạn mã này? Chúng ta có một vòng lặp trong đó chúng ta thay đổi chỉ số (

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

2. từ 0 thành phần tử cuối cùng trong mảng. Trên thực tế, chúng ta chỉ đơn giản là lấy từng phần tử trong mảng và in nội dung của nó. Càng nhiều phần tử trong mảng, mã sẽ mất nhiều thời gian hơn để hoàn thành. Đó là, nếu

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

3là số lượng phần tử, khi đó

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

4chương trình sẽ mất gấp đôi thời gian để chạy so với khi

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

5. Nếu chương trình của chúng ta có một vòng lặp duy nhất, thời gian thực hiện sẽ tăng theo tuyến tính: càng có nhiều phần tử thì thời gian thực hiện càng dài. Hóa ra thuật toán trên hoạt động trong thời gian tuyến tính (một hàm tuyến tính của n). Trong những trường hợp như vậy, chúng ta nói rằng độ phức tạp của thuật toán là "O(n)". Ký hiệu này còn được gọi là "big O" hoặc "hành vi tiệm cận". Nhưng bạn chỉ có thể nhớ "

Thuật toán sắp xếp đơn giản nhất (sắp xếp bong bóng)

Giả sử chúng ta có một mảng và chúng ta có thể lặp qua nó. Tuyệt vời. Bây giờ hãy thử sắp xếp nó theo thứ tự tăng dần. Điều đó có nghĩa là gì? Có nghĩa là đã cho 2 phần tử (ví dụ ,

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

7, chúng ta phải sắp xếp lại

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

8và

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

9if

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

8lớn hơn

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

9(if

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {    
    swap(array, i, i-1);  
  }  
}  
System.out.println(Arrays.toString(array));  

2). Điều này có nghĩa là gì khi chúng ta đang sử dụng một chỉ mục để làm việc với một bộ sưu tập (như trường hợp của một mảng)? Nghĩa là nếu phần tử có chỉ số a lớn hơn phần tử có chỉ số

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

9(

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {    
    swap(array, i, i-1);  
  }  
}  
System.out.println(Arrays.toString(array));  

4. thì phải đổi chỗ các phần tử. Có nhiều cách khác nhau để thay đổi địa điểm. Nhưng chúng ta sẽ sử dụng một kỹ thuật đơn giản, dễ hiểu và dễ nhớ:

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

Bây giờ chúng ta có thể viết như sau:

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {    
    swap(array, i, i-1);  
  }  
}  
System.out.println(Arrays.toString(array));  

Như bạn có thể thấy, các yếu tố thực sự đã được hoán đổi. Chúng tôi đã bắt đầu với chỉ mục 1, bởi vì nếu mảng chỉ có một phần tử, thì biểu thức

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {    
    swap(array, i, i-1);  
  }  
}  
System.out.println(Arrays.toString(array));  

5không hợp lệ cho chỉ mục

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {    
    swap(array, i, i-1);  
  }  
}  
System.out.println(Arrays.toString(array));  

6. Làm điều này cũng bảo vệ chúng ta khỏi các trường hợp mảng không có phần tử hoặc chỉ có một phần tử và nó làm cho mã trông đẹp hơn. Nhưng mảng kết quả vẫn chưa được sắp xếp, vì một lượt không đủ để thực hiện việc sắp xếp. Chúng ta sẽ phải thêm một vòng lặp khác trong đó chúng ta sẽ thực hiện lặp đi lặp lại cho đến khi nhận được một mảng đã sắp xếp:

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
boolean needIteration = true;  
while (needIteration) {  
  needIteration = false;  
  for (int i = 1; i < array.length; i++) {  
    if (array[i] < array[i - 1]) {  
      swap(array, i, i-1);  
      needIteration = true;  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

Vì vậy, chúng tôi đã hoàn thành thuật toán sắp xếp đầu tiên của mình. Chúng tôi lặp lại vòng lặp bên ngoài (

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {    
    swap(array, i, i-1);  
  }  
}  
System.out.println(Arrays.toString(array));  

7. cho đến khi chúng tôi quyết định rằng không cần lặp lại nữa. Theo mặc định, trước mỗi lần lặp mới, chúng tôi giả định rằng mảng của chúng tôi đã được sắp xếp và chúng tôi không cần lặp lại nữa. Theo đó, chúng tôi di chuyển tuần tự qua các yếu tố và kiểm tra giả định này. Nhưng nếu các phần tử không theo thứ tự, thì chúng tôi hoán đổi các phần tử và hiểu rằng bây giờ chúng tôi không đảm bảo rằng các phần tử theo đúng thứ tự. Điều này có nghĩa là chúng ta cần thực hiện một lần lặp khác. Ví dụ: giả sử chúng ta có

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {    
    swap(array, i, i-1);  
  }  
}  
System.out.println(Arrays.toString(array));  

8.

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {    
    swap(array, i, i-1);  
  }  
}  
System.out.println(Arrays.toString(array));  

9còn hơn cả

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
boolean needIteration = true;  
while (needIteration) {  
  needIteration = false;  
  for (int i = 1; i < array.length; i++) {  
    if (array[i] < array[i - 1]) {  
      swap(array, i, i-1);  
      needIteration = true;  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

0— tất cả đều tốt. Nhưng

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
boolean needIteration = true;  
while (needIteration) {  
  needIteration = false;  
  for (int i = 1; i < array.length; i++) {  
    if (array[i] < array[i - 1]) {  
      swap(array, i, i-1);  
      needIteration = true;  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

1ít hơn

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {    
    swap(array, i, i-1);  
  }  
}  
System.out.println(Arrays.toString(array));  

9. Tuy nhiên,

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
boolean needIteration = true;  
while (needIteration) {  
  needIteration = false;  
  for (int i = 1; i < array.length; i++) {  
    if (array[i] < array[i - 1]) {  
      swap(array, i, i-1);  
      needIteration = true;  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

3yêu cầu một lần vượt qua khác, vì

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
boolean needIteration = true;  
while (needIteration) {  
  needIteration = false;  
  for (int i = 1; i < array.length; i++) {  
    if (array[i] < array[i - 1]) {  
      swap(array, i, i-1);  
      needIteration = true;  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

4và chúng cần được hoán đổi. Bởi vì chúng tôi đang sử dụng một vòng lặp trong một vòng lặp, độ phức tạp của thuật toán của chúng tôi tăng lên. Các phần tử đã cho

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

3, nó trở thành

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
boolean needIteration = true;  
while (needIteration) {  
  needIteration = false;  
  for (int i = 1; i < array.length; i++) {  
    if (array[i] < array[i - 1]) {  
      swap(array, i, i-1);  
      needIteration = true;  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

6, nghĩa là,

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
boolean needIteration = true;  
while (needIteration) {  
  needIteration = false;  
  for (int i = 1; i < array.length; i++) {  
    if (array[i] < array[i - 1]) {  
      swap(array, i, i-1);  
      needIteration = true;  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

7. Đây được gọi là độ phức tạp bậc hai. Nói chung, chúng ta không thể biết chính xác sẽ cần bao nhiêu lần lặp. Biểu thức độ phức tạp của một thuật toán cho thấy độ phức tạp tăng lên như thế nào trong trường hợp xấu nhất. Nghĩa là, nó cho biết thời gian thực hiện sẽ tăng lên bao nhiêu khi số phần tử

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

3thay đổi. Sắp xếp bong bóng là một trong những thuật toán sắp xếp đơn giản và kém hiệu quả nhất. Đôi khi nó còn được gọi là "stupid sort". Tài liệu về chủ đề này:

• "HackerRank: Thuật toán - Sắp xếp bong bóng "

sắp xếp lựa chọn

Một thuật toán sắp xếp khác là sắp xếp lựa chọn. Nó cũng có độ phức tạp bậc hai, nhưng nhiều hơn về điều đó sau. Vì vậy, ý tưởng là đơn giản. Trên mỗi lần vượt qua, chúng tôi chọn phần tử nhỏ nhất và chuyển nó về đầu. Ngoài ra, mỗi lần vượt qua bắt đầu một bước bên phải. Nói cách khác, lượt đầu tiên bắt đầu từ phần tử thứ 0, lượt thứ hai bắt đầu từ phần tử đầu tiên, v.v. Nó sẽ trông như thế này:

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

Cách sắp xếp này không ổn định, vì các phần tử giống hệt nhau (về bất kỳ đặc điểm nào mà chúng ta đang sử dụng để sắp xếp các phần tử) có thể thay đổi vị trí tương đối của chúng. Có một ví dụ điển hình là trong bài viết trên Wikipedia về sắp xếp lựa chọn . Tài liệu về chủ đề này:

• "CS50: Sắp xếp lựa chọn"

Sắp xếp chèn

Sắp xếp chèn cũng có độ phức tạp bậc hai, vì chúng ta lại có một vòng lặp bên trong một vòng lặp. Điều gì làm cho sắp xếp chèn khác nhau? Thuật toán sắp xếp này là "ổn định." Điều này có nghĩa là các phần tử giống hệt nhau sẽ không thay đổi thứ tự tương đối của chúng. Một lần nữa, chúng tôi có nghĩa là giống hệt nhau về các đặc điểm mà chúng tôi sắp xếp theo.

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  // Get an element  
  int value = array[left];  
  // Iterate through the elements that are in front of this element  
  int i = left - 1;  
  for (; i >= 0; i--) {  
    // If the current element is smaller, then move the larger element to the right.  
    if (value < array[i]) {  
      array[i + 1] = array[i];  
    } else {  
      // If the current element is larger, we stop  
      break;  
    }  
  }  
  // Insert the current value in the empty space  
  array[i + 1] = value;  
}  
System.out.println(Arrays.toString(array));  

loại xe đưa đón

Có một thuật toán sắp xếp đơn giản khác: sắp xếp con thoi. Điều này còn được gọi là sắp xếp bong bóng hai chiều hoặc sắp xếp bình lắc cocktail. Những tên thay thế này cho chúng ta biết rằng loại tàu con thoi không phải là về tàu con thoi. Đó là về một cái gì đó di chuyển qua lại. Bây giờ bạn có thể nghĩ về điều đó khi nghĩ về thuật toán này. Bản chất của thuật toán là gì? Bản chất của thuật toán là chúng ta lặp từ trái sang phải, hoán đổi các phần tử và kiểm tra xem có phần tử nào còn lại theo hướng khác cần hoán đổi hay không.

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int i = 1; i < array.length; i++) {  
  if (array[i] < array[i - 1]) {  
    swap(array, i, i - 1);  
    for (int z = i - 1; (z - 1) >= 0; z--) {  
      if (array[z] < array[z - 1]) {  
        swap(array, z, z - 1);  
      } else {  
        break;  
      }  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

Tài liệu về chủ đề này:

• Quyết định AQA 1 2.02a Giới thiệu Shuttle Sort của Jack Brown

phân loại vỏ

Một thuật toán sắp xếp đơn giản khác là sắp xếp vỏ. Ý chính của nó tương tự như sắp xếp bong bóng, nhưng trong mỗi lần lặp lại, chúng ta có một khoảng cách khác nhau giữa các phần tử được so sánh. Nó được cắt làm đôi với mỗi lần lặp lại. Đây là một triển khai:

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
// Calculate the gap between the checked elements  
int gap = array.length / 2;  
// As long as there is a gap between the elements  
while (gap >= 1) {  
    for (int right = 0; right < array.length; right++) {  
        // Shift the right index until we find one for which  
        // there is the necessary gap between it and the element before it  
       for (int c = right - gap; c >= 0; c -= gap) {  
           if (array[c] > array[c + gap]) {  
               swap(array, c, c + gap);  
           }  
        }  
    }  
    // Recalculate the gap  
    gap = gap / 2;  
}  
System.out.println(Arrays.toString(array));  

Tài liệu về chủ đề này:

• AQA Quyết định 1 2.03a Shell Sort - một ví dụ với 8 số

Hợp nhất sắp xếp

Ngoài các thuật toán sắp xếp đơn giản này, còn có các thuật toán sắp xếp phức tạp hơn. Ví dụ: sắp xếp hợp nhất. Có hai điều cần lưu ý. Đầu tiên, đệ quy đến để giải cứu chúng tôi ở đây. Thứ hai, độ phức tạp của thuật toán không còn là bậc hai như chúng ta đã quen. Độ phức tạp của thuật toán này là logarit. Điều này được viết là

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
boolean needIteration = true;  
while (needIteration) {  
  needIteration = false;  
  for (int i = 1; i < array.length; i++) {  
    if (array[i] < array[i - 1]) {  
      swap(array, i, i-1);  
      needIteration = true;  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

9. Vì vậy, hãy thực hiện nó. Đầu tiên, chúng ta sẽ viết một lời gọi đệ quy tới phương thức sắp xếp:

  
public static void mergeSort(int[] source, int left, int right) {  
        // Select the delimiter, i.e. split the input array in half  
        int delimiter = left + ((right - left) / 2) + 1;  
        // Recursively execute this function on the two halves (if we can split the input array)  
        if (delimiter > 0 && right > (left + 1)) {  
            mergeSort(source, left, delimiter - 1);  
            mergeSort(source, delimiter, right);  
        }  
}  

Bây giờ, hãy thêm hành động chính vào phần triển khai của chúng ta. Đây là siêu phương pháp của chúng tôi:

  
public static void mergeSort(int[] source, int left, int right) {  
        // Select the delimiter, i.e. split the input array in half  
        int delimiter = left + ((right - left) / 2) + 1;  
        // Recursively execute this function on the two halves (if we can split the input array)  
        if (delimiter > 0 && right > (left + 1)) {  
            mergeSort(source, left, delimiter - 1);  
            mergeSort(source, delimiter, right);  
        }  
        // Create a temporary array with the required size  
        int[] buffer = new int[right - left + 1];  
        // Starting from the specified left index, go through each element.  
        int cursor = left;  
        for (int i = 0; i < buffer.length; i++) {  
            // We use delimeter to point to the element on the right half  
            // If delimeter> right, then the right half has no elements that haven't been added  
            if (delimiter > right || source[cursor] > source[delimiter]) {  
                buffer[i] = source[cursor];  
                cursor++;  
            } else {  
                buffer[i] = source[delimiter];  
                delimiter++;  
            }  
        }  
        System.arraycopy(buffer, 0, source, left, buffer.length);  
}  

Chúng ta có thể chạy ví dụ của mình bằng cách gọi

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

0. Như bạn có thể thấy, quy trình rút gọn lại để chấp nhận một mảng đầu vào cùng với các chỉ dẫn về phần đầu và phần cuối của phần cần được sắp xếp. Khi sắp xếp bắt đầu, đây là phần đầu và phần cuối của mảng. Sau đó, chúng tôi tính toán dấu phân cách, là chỉ mục mà chúng tôi sẽ phân chia mảng. Nếu mảng có thể được chia thành 2 phần, thì chúng ta gọi phương thức sắp xếp theo cách đệ quy cho hai nửa của mảng. Chúng tôi chuẩn bị một bộ đệm phụ, nơi chúng tôi sẽ chèn phần đã sắp xếp. Tiếp theo, đặt chỉ mục ở đầu phần sẽ được sắp xếp và bắt đầu đi qua từng phần tử của bộ đệm trống, lấp đầy nó bằng các phần tử nhỏ nhất. Nếu phần tử được trỏ đến bởi chỉ mục nhỏ hơn phần tử được trỏ đến bởi dấu phân cách, chúng ta đặt phần tử vào bộ đệm và dịch chuyển chỉ mục. Nếu không thì, chúng tôi đặt phần tử được trỏ bởi dấu phân cách vào bộ đệm và dịch chuyển dấu phân cách. Ngay khi dấu phân cách vượt ra ngoài ranh giới của phần được sắp xếp hoặc chúng tôi điền vào toàn bộ mảng, phạm vi đã chỉ định được coi là đã sắp xếp.Tài liệu về chủ đề này:

• CS50: Hợp nhất sắp xếp
• Hướng dẫn ý tưởng - Sắp xếp hợp nhất

Đếm sắp xếp và sắp xếp cơ số

Một thuật toán sắp xếp thú vị khác là sắp xếp đếm. Độ phức tạp của thuật toán ở đây là

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

1, ở đâu

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

3là số phần tử và

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

3là giá trị lớn nhất của một phần tử. Thuật toán này có một thiếu sót: chúng ta cần biết các giá trị tối thiểu và tối đa trong mảng. Dưới đây là một ví dụ về sắp xếp đếm:

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

0

Bạn có thể hiểu rằng rất bất tiện khi chúng ta cần biết trước giá trị nhỏ nhất và giá trị lớn nhất. Và chúng ta có một thuật toán khác ở đây: sắp xếp cơ số. Tôi sẽ chỉ trình bày thuật toán ở đây một cách trực quan. Xem các tài liệu bổ sung để thực hiện: Tài liệu:

• Video về sắp xếp đếm
• thuật toán sắp xếp đếm

Sắp xếp nhanh chóng

Chà, đã đến lúc ăn tráng miệng — sắp xếp nhanh, một trong những thuật toán sắp xếp nổi tiếng nhất. Nó có độ phức tạp logarit:

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
boolean needIteration = true;  
while (needIteration) {  
  needIteration = false;  
  for (int i = 1; i < array.length; i++) {  
    if (array[i] < array[i - 1]) {  
      swap(array, i, i-1);  
      needIteration = true;  
    }  
  }  
}  
System.out.println(Arrays.toString(array));  

9. Thuật toán sắp xếp này được phát triển bởi Tony Hoare. Thật thú vị, anh ấy đã phát minh ra nó khi sống ở Liên Xô, nơi anh ấy học dịch máy tại Đại học Moscow và phát triển một cuốn sách cụm từ tiếng Nga-Anh. Hơn nữa, Java sử dụng phiên bản phức tạp hơn của thuật toán này trong

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

5. Thế còn

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

6? Tại sao không xem xét cách mọi thứ được sắp xếp "dưới mui xe"? Đây là mã:

  
private void swap(int[] array, int ind1, int ind2) {  
    int tmp = array[ind1];  
    array[ind1] = array[ind2];  
    array[ind2] = tmp;  
}  

1

Đây là tất cả những thứ rất đáng sợ, vì vậy hãy tìm hiểu sâu về nó. Đối với mảng đầu vào (

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

7nguồn ), chúng ta tạo hai điểm đánh dấu: trái (

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

8. và phải (

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

9). Trong lần gọi phương thức đầu tiên, chúng tương ứng với phần đầu và phần cuối của mảng. Sau đó, chúng tôi xác định phần tử trục, được đặt tên một cách thích hợp

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  // Get an element  
  int value = array[left];  
  // Iterate through the elements that are in front of this element  
  int i = left - 1;  
  for (; i >= 0; i--) {  
    // If the current element is smaller, then move the larger element to the right.  
    if (value < array[i]) {  
      array[i + 1] = array[i];  
    } else {  
      // If the current element is larger, we stop  
      break;  
    }  
  }  
  // Insert the current value in the empty space  
  array[i + 1] = value;  
}  
System.out.println(Arrays.toString(array));  

0. Sau đó, nhiệm vụ của chúng ta là di chuyển các giá trị nhỏ hơn

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  // Get an element  
  int value = array[left];  
  // Iterate through the elements that are in front of this element  
  int i = left - 1;  
  for (; i >= 0; i--) {  
    // If the current element is smaller, then move the larger element to the right.  
    if (value < array[i]) {  
      array[i + 1] = array[i];  
    } else {  
      // If the current element is larger, we stop  
      break;  
    }  
  }  
  // Insert the current value in the empty space  
  array[i + 1] = value;  
}  
System.out.println(Arrays.toString(array));  

0sang trái của

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  // Get an element  
  int value = array[left];  
  // Iterate through the elements that are in front of this element  
  int i = left - 1;  
  for (; i >= 0; i--) {  
    // If the current element is smaller, then move the larger element to the right.  
    if (value < array[i]) {  
      array[i + 1] = array[i];  
    } else {  
      // If the current element is larger, we stop  
      break;  
    }  
  }  
  // Insert the current value in the empty space  
  array[i + 1] = value;  
}  
System.out.println(Arrays.toString(array));  

0, và các giá trị lớn hơn — sang phải. Để làm điều này, trước tiên chúng tôi di chuyển

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  int minInd = left;  
  for (int i = left; i < array.length; i++) {  
    if (array[i] < array[minInd]) {  
      minInd = i;  
    }  
  }  
  swap(array, left, minInd);  
}  
System.out.println(Arrays.toString(array));  

8điểm đánh dấu cho đến khi chúng tôi tìm thấy giá trị lớn hơn

  
int[] array = {10, 2, 10, 3, 1, 2, 5};  
System.out.println(Arrays.toString(array));  
for (int left = 0; left < array.length; left++) {  
  // Get an element  
  int value = array[left];  
  // Iterate through the elements that are in front of this element  
  int i = left - 1;  
  for (; i >= 0; i--) {  
    // If the current element is smaller, then move the larger element to the right.  
    if (value < array[i]) {  
      array[i + 1] = array[i];  
    } else {  
      // If the current element is larger, we stop  
      break;  
    }  
  }  
  // Insert the current value in the empty space  
  array[i + 1] = value;  
}  
System.out.println(Arrays.toString(array));  

0. Nếu không tìm được giá trị nào nhỏ hơn thì