Trong hướng dẫn này, bạn sẽ tìm hiểu cách sắp xếp chèn hoạt động. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về sắp xếp chèn trong C, C ++, Java và Python.
Sắp xếp chèn hoạt động tương tự như chúng ta sắp xếp các quân bài trên tay trong một trò chơi bài.
Chúng tôi giả định rằng thẻ đầu tiên đã được sắp xếp sau đó, chúng tôi chọn một thẻ chưa được sắp xếp. Nếu thẻ chưa được phân loại lớn hơn thẻ trên tay, nó được đặt ở bên phải, ngược lại là bên trái. Theo cách tương tự, các thẻ chưa được phân loại khác được lấy và đặt vào đúng vị trí của chúng.
Một cách tiếp cận tương tự được sử dụng bằng cách sắp xếp chèn.
Sắp xếp chèn là một thuật toán sắp xếp đặt một phần tử chưa được sắp xếp vào vị trí thích hợp của nó trong mỗi lần lặp.
Cách sắp xếp chèn hoạt động?
Giả sử chúng ta cần sắp xếp mảng sau.
Mảng ban đầu
- Phần tử đầu tiên trong mảng được giả định là đã được sắp xếp. Lấy phần tử thứ hai và lưu trữ riêng trong
key.
So sánhkeyvới phần tử đầu tiên. Nếu phần tử đầu tiên lớn hơnkey, thì khóa được đặt trước phần tử đầu tiên.
Nếu phần tử đầu tiên lớn hơn khóa, thì khóa sẽ được đặt trước phần tử đầu tiên. - Bây giờ, hai phần tử đầu tiên đã được sắp xếp.
Lấy phần tử thứ ba và so sánh nó với các phần tử bên trái của nó. Đặt nó ngay sau phần tử nhỏ hơn nó. Nếu không có phần tử nào nhỏ hơn nó, thì hãy đặt nó ở đầu mảng.
Đặt 1 ở đầu - Tương tự, hãy đặt mọi phần tử chưa được sắp xếp vào đúng vị trí của nó.
Đặt 4 sau 1 
Đặt 3 sau 1 và mảng được sắp xếp
Thuật toán sắp xếp chèn
inserttionSort (mảng) đánh dấu phần tử đầu tiên được sắp xếp cho từng phần tử chưa được sắp xếp X 'giải nén' phần tử X cho j X di chuyển phần tử đã sắp xếp sang phải bằng 1 vòng lặp ngắt và chèn X vào đây kết thúc inserttionSort
Ví dụ về Python, Java và C / C ++
Python Java C C ++ # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)
// Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )
// Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )
Phức tạp
Thời gian phức tạp
- Độ phức tạp của trường hợp tồi tệ nhất: Giả sử, một mảng có thứ tự tăng dần và bạn muốn sắp xếp nó theo thứ tự giảm dần. Trong trường hợp này, trường hợp xấu nhất phức tạp xảy ra. Mỗi phần tử phải được so sánh với mỗi phần tử khác, do đó, đối với mỗi phần tử thứ n, số lần so sánh được thực hiện. Như vậy, tổng số phép so sánh =
O(n2)(n-1)n*(n-1) ~ n2 - Độ phức tạp của trường hợp tốt nhất:
O(n)
Khi mảng đã được sắp xếp, vòng lặp bên ngoài chạy theonsố lần trong khi vòng lặp bên trong hoàn toàn không chạy. Vì vậy, chỉ có mộtnsố so sánh. Do đó, độ phức tạp là tuyến tính. - Độ phức tạp của trường hợp trung bình: Nó xảy ra khi các phần tử của một mảng có thứ tự lộn xộn (không tăng dần cũng không giảm dần).
O(n2)
Không gian phức tạp
Không gian phức tạp là O(1)do một biến phụ keyđược sử dụng.
Ứng dụng sắp xếp chèn
Sắp xếp chèn được sử dụng khi:
- mảng có một số phần tử nhỏ
- chỉ còn lại một số yếu tố được sắp xếp
