Các Thuật Toán Sắp Xếp Trong Cấu Trúc Dữ Liệu, Cấu Trúc Dữ Liệu Vào Giải Thuật

Sắp xếp là quá trình bố trí lại các bộ phận trong một tập đúng theo theo một trình tự nào đó nhằm mục đích giúp làm chủ và kiếm tìm kiếm các thành phần dễ dàng và hối hả hơn.

Tại sao buộc phải sắp xếp?

Để hoàn toàn có thể sử dụng thuật toán kiếm tìm nhị phânĐể thực hiện làm việc nào đó được nhanh hơn

Các phương pháp sắp xếp thông dụng:

Phương pháp Đổi vị trí trực tiếp (Interchange sort)

Phương pháp Nổi bong bóng (Bubble sort)

Phương pháp Chèn trực tiếp (Insertion sort)

Phương pháp chọn trực tiếp (Selection sort)

Interchange Sort

Khái niệm nghịch thế:

Xét một mảng những số a<0>, a<1>, … aNếu tất cả i a, thì ta gọi đó là một trong những nghịch thế

Mảng không sắp xếp sẽ có được nghịch thế

Mảng đã có thứ tự sẽ không còn chứa nghịch thế

a<0> Để sắp xếp một dãy số, ta có thể xét những nghịch thế gồm trong dãy và có tác dụng triệt tiêu dần bọn chúng đi

Ý tưởng:

Xuất phát từ đầu dãy, tìm tất cả nghịch nỗ lực chứa thành phần này, triệt tiêu chúng bằng cách đổi chỗ thành phần này với thành phần tương ứng trong cặp nghịch thếLặp lại cách xử trí trên với các bộ phận tiếp theo trong dãy

void Swap(int &a, int &b) int temp = a; a = b; b = temp;void InterchangeSort(int a<>, int n) for (int i = 0; i a) //nếu bao gồm nghịch thế thì đổi khu vực Swap(a, a);Đánh giá:

Số lượng các phép đối chiếu xảy ra không phụ thuộc vào vào tình trạng của dãy số ban đầuSố lượng phép hoán vị thực hiện tùy trực thuộc vào tác dụng so sánh
Bubble Sort
Ý tưởng:
Xuất phát từ cuối dãy, đổi chỗ các cặp bộ phận kế cận để đưa phần tử nhỏ hơn vào cặp thành phần đó về địa chỉ đầu dãy hiện hành, sau đó sẽ ko xét mang đến nó ở cách tiếp theo
Ở lần cách xử lý thứ i có vị trí đầu hàng là i
Lặp lại xử trí trên cho đến khi không thể cặp bộ phận nào để xét
void BubbleSort(int a<>, int n){for (int i = 0; i i; j--) if(a
Đánh giá:
Số lượng các phép so sánh xảy ra không nhờ vào vào triệu chứng của dãy số ban đầu
Số lượng phép hoán vị triển khai tùy thuộc vào công dụng so sánh
Khuyết điểm:
Không nhận diện được triệu chứng dãy đã gồm thứ tự hay tất cả thứ từ bỏ từng phầnCác phần tử bé dại được mang đến vị trí đúng khôn cùng nhanh, trong khi các thành phần lớn lại được mang đến vị trí đúng vô cùng chậm
Insertion Sort
Nhận xét:
Mọi dãy a<0> , a<1> ,..., a luôn luôn có i-1 thành phần đầu tiên a<0> , a<1> ,... , a đã gồm thứ tự (i ≥ 2)
Ý tưởng chính:
Tìm phương pháp chèn phần tử a vào vị trí thích hợp của đoạn đã có sắp để có dãy mới a<0> , a<1> ,...
Xem thêm: Bột Mì Số 11 Làm Bánh Gì ? Công Dụng Và Giá Cả Bột Mì Số 11 Là Gì
, a trở nên có thứ tựVị trí này đó là pos thỏa :a
void InsertionSort(int a<>, int n){int pos, x;for(int i = 1; i 0 && x Đánh giá:
Giải thuật thực hiện tất cả N-1 vòng lặp tìm kiếm pos, do con số phép đối chiếu và dời nơi này nhờ vào vào tình trạng của hàng số ban đầu, cần chỉ rất có thể ước lược trong từng trường thích hợp như sau:
Selection Sort
Nhận xét:
Mảng có thứ từ thì a = min(a, a, …, a)
Ý tưởng: mô phỏng trong số những cách sắp xếp tự nhiên nhất vào thực tế:
Chọn phần tử bé dại nhất trong n phần tử ban đầu, đưa thành phần này về vị trí đúng là đầu dãy hiện hànhXem dãy hiện hành chỉ từ n-1 thành phần của dãy ban đầu, bước đầu từ địa điểm thứ 2; lặp lại quá trình trên cho dãy hiện tại hành... Cho đến lúc dãy hiện hành chỉ còn một phần tử
void SelectionSort(int a<>, int n){int min; // chỉ số phần tử bé dại nhất trong dãy hiện hànhfor (int i = 0; i Đánh giá:
Ở lượt trang bị i, phải (n-i) lần so sánh để khẳng định phần tử nhỏ nhất hiện tại hànhSố lượng phép đối chiếu không dựa vào vào triệu chứng của hàng số ban đầuTrong đầy đủ trường hợp, số lần đối chiếu là:
Tạm kết
Như vậy là bản thân đã reviews cho chúng ta 4 thuật toán bố trí thông dụng. Ở phần tới mình sẽ trình làng thêm cho các bạn thêm các thuật toán bố trí khác.