Các thuật toán sắp xếp trong cấu trúc dữ liệu

     

Thuật toán sắp xếp là giữa những loại thuật toán được sử dụng tương đối nhiều trong cuộc sống, dễ dàng nó là các phương thức sắp xếp lại hàng kí tự theo mong muốn của bạn lập trình.Việc học những thuật toán nhuần nhuyễn sẽ giúp các bạn nâng cao tứ duy giải quyết và xử lý vấn đề bởi lập trình.

Bạn đang xem: Các thuật toán sắp xếp trong cấu trúc dữ liệu

Bài này bên trong serie học tập lập trình C tự A cho tới Z


Sắp xếp nổi bọt bong bóng (Bubble Sort)Sắp xếp chèn (Insertion Sort)Sắp xếp lựa chọn (Selection Sort)Sắp xếp trộn (Merge Sort)Sắp xếp nhanh (Quick Sort)Shell SortThuật toán sắp xếp đếm (Counting Sort)Thuật toán thu xếp theo cơ số (Radix Sort)Thuật toán thu xếp theo khối (Bucket Sort)Thuật toán sắp xếp vun lô (Heap Sort)Lời kết

Tổng quan tiền chung

Sắp xếp dữ liệu là một phần thế tất trong bài toán phân tích dữ liệu. Việc sắp xếp dữ liệu giúp bạn nhanh chóng trực quan liêu hóa và hiểu rõ rộng về dữ liệu của mình, tổ chức và tìm kiếm kiếm dữ liệu mà bạn có nhu cầu và sau cuối là giới thiệu quyết định hiệu quả hơn.

Sắp xếp dữ liệu tương quan đến việc bố trí mảng theo một máy tự làm sao đo chẳng hạn như tăng dần dần hoặc bớt dần. Những thuật toán thu xếp cơ phiên bản bao gồm:

Sắp xếp nổi bong bóng (Bubble Sort)Sắp xếp chèn (Insertion Sort)Sắp xếp chọn (Selection Sort)Sắp xếp trộn (Merge Sort)Sắp xếp nhanh (Quick Sort)Shell SortSắp xếp đếm (Counting Sort)Sắp xếp theo cơ số (Radix Sort)Sắp xêp theo khối (Bucket Sort)Sắp xếp vun đụn (Heap Sort)

Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp nổi bọt bong bóng là như thế nào

Sắp xếp nổi bọt là 1 trong giải thuật bố trí đơn giản. Giải thuật sắp xếp này được triển khai dựa trên việc so sánh cặp thành phần liền kề nhau cùng tráo đổi thứ tự trường hợp chúng không tuân theo thứ tự.

Giải thuật này không tương thích sử dụng với các tập dữ liệu lớn khi nhưng mà độ tinh vi trường hòa hợp xấu nhất cùng trường phù hợp trung bình là Ο(n2) cùng với n là số phần tử.

Giải thuật bố trí nổi bọt bong bóng là lời giải chậm nhất trong những các lời giải sắp xếp cơ bản. Giải mã này còn chậm hơn lời giải đổi địa điểm trực tiếp tuy nhiên số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau yêu cầu số lần đổi chỗ nhiều hơn.

Có hai phương pháp trong sắp xếp nổi bọt bong bóng được triển khai:

Từ dưới lên bên trên (Bottom – up): So sánh các giá trị lần lượt từ thời điểm cuối mảng nếu nhỏ tuổi hơn thì dần dần cho lên trên.Từ bên trên xuống: So sánh ban đầu từ phần tử trên cùng, nếu thành phần lớn hơn sẽ ảnh hưởng chìm xuống dưới.

Ý tưởng bài toán:

*
Minh họa thuật toán sắp xếp nổi bọt

Triển khai ý tưởng

Thuật toán sắp xếp nổi bọt tiến hành sắp xếp dãy số bằng cách lặp lại quá trình đổi vị trí 2 số tiếp tục nhau nếu chúng đứng sai vật dụng tự(số sau bé thêm hơn số trước với ngôi trường hợp thu xếp tăng dần) cho tới khi dãy số được sắp tới xếp.

Giả sử họ cần sắp xếp dãy số <5 1 4 2 8> này tăng dần. Lần lặp đầu tiên:5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Ở đây, thuật toán sẽ đối chiếu hai phần tử đầu tiên, và đổi chỗ lẫn nhau do 5 > 1. ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Đổi chỗ vì chưng 5 > 4 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Đổi chỗ vì 5 > 2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Ở đây, hai bộ phận đang xét sẽ đúng vật dụng tự (8 > 5), vậy ta không buộc phải đổi chỗ.

Lần lặp máy 2:1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Đổi chỗ do 4 > 2 ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) Bây giờ, dãy số sẽ được chuẩn bị xếp, tuy thế thuật toán của chúng ta không thừa nhận ra điều ấy ngay được. Thuật toán sẽ bắt buộc thêm một lượt lặp nữa để kết luận dãy đã bố trí khi cùng khi khi nó đi từ đầu tới cuối cơ mà không có ngẫu nhiên lần đổi chỗ nào được thực hiện.

Lần lặp thiết bị 3:1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

PHƯƠNG PHÁP CHUNG:Cho một mảng tất cả n phần tửLặp lại quá trình sau n-1 lần:

+ cùng với a và a:

trường hợp a to hơn a thì thay đổi vị trí mang đến nhau

Cách viết thuật toán sắp xếp nổi bong bóng với C

Ví dụ 1: sắp xếp lại mảng gồm sẵn theo vật dụng thự nhỏ tuổi tới to dùng thuật toán thu xếp nổi bọt

*
*

Kết quả hiển thị:

*

Ví dụ 2: cụ thể quá trình sắp xếp 

#include #include #define MAX 10int list = 1,8,4,6,0,3,5,2,7,9;void display()int i;printf("<");// Duyet qua tat ca phan tufor(i = 0; i list) temp = list;list = list;list = temp;swapped = true;printf(" => trao doi <%d, %d> ",list,list);else printf(" => khong can trao doi ");// neu khong can trao doi nua, tuc la// sở hữu da duoc sap xep va thoat khoi vong lap.if(!swapped) break;printf("Vong lap thu %d#: ",(i+1));display();}}main()printf("Mang du lieu dau vao: ");display();printf(" ");bubbleSort();printf(" Mang sau thời điểm da sap xep: ");display();Kết quả

*

Sắp xếp chèn (Insertion Sort)

Thuật toán bố trí chèn là gì?

Sắp xếp chèn là 1 trong những giải thuật bố trí dựa trên so sánh in-place. Ở đây, một list con luôn luôn luôn được bảo trì dưới dạng sẽ qua chuẩn bị xếp. Thu xếp chèn là chèn thêm 1 phần tử vào list con sẽ qua sắp xếp. Phần tử được chèn vào vị trí mê say hợp làm thế nào cho vẫn bảo đảm rằng list con này vẫn sắp theo đồ vật tự.

Với kết cấu dữ liệu mảng, chúng ta tưởng tượng là: mảng tất cả hai phần: một danh sách con vẫn được bố trí và phần khác là các thành phần không tất cả thứ tự. Giải thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các bộ phận không tất cả thứ tự đã được di chuyển và được chèn vào vị trí tương thích trong list con (của cùng mảng đó).

Giải thuật này không phù hợp sử dụng với những tập dữ liệu lớn khi độ phức hợp trường hợp xấu nhất với trường thích hợp trung bình là Ο(n2) với n là số phần tử.

Một vài phương pháp được sử dụng trong bố trí chèn:

Đối với mỗi thành phần của mảng, để nó vào đúng địa chỉ giữa các thành phần khác được sắp đến xếp.Khi bộ phận cuối cùng được đặt vào vị trí, mảng được sắp xếp xong.

Ý tưởng bài toán:

*
Minh họa thuật toán thu xếp chèn

Thuật toán bố trí chèn tiến hành sắp xếp hàng số theo phong cách duyệt từng phần tử và chèn từng bộ phận đó vào đúng địa điểm trong mảng con(dãy số từ đầu đến bộ phận phía trước nó) đã sắp tới xếp sao để cho dãy số trong mảng chuẩn bị đã xếp đó vẫn bảo đảm tính hóa học của một hàng số tăng dần.

Khởi chế tạo ra mảng với dãy bé đã thu xếp có k = 1 phần tử(phần tử đầu tiên, thành phần có chỉ số 0)Duyệt từng phần tử từ phần tử thứ 2, tại mỗi lần duyệt bộ phận ở chỉ số i thì đặt thành phần đó vào trong 1 vị trí nào đó trong đoạn trường đoản cú <0…i> sao để cho dãy số tự <0…i> vẫn đảm bảo tính chất dãy số tăng dần. Sau các lần duyệt, số thành phần đã được thu xếp k vào mảng tăng thêm một phần tử.Lặp tính đến khi săn sóc hết toàn bộ các phần tử của mảng.

Sắp xếp chèn với ngôn ngữ C

Ví dụ minh họa: sắp xếp mảng từ thấp mang lại cao sử dụng thuật toán thu xếp chèn

*
*

Kết quả hiển thị:

*

Ví dụ: cụ thể quá trình thu xếp chèn

#include #include #define MAX 7int intArray = 4,6,3,2,1,9,7;void printline(int count)int i;for(i = 0;i 0 && intArray > valueToInsert)intArray = intArray;holePosition--;printf(" Di chuyen phan tu : %d " , intArray);if(holePosition != i)printf(" Chen phan tu : %d, tai vi tri : %d " , valueToInsert,holePosition);// chen phan tu tai vi tri chenintArray = valueToInsert;printf("Vong lap thu %d#:",i);display();}main()printf("Mang du lieu dau vao: ");display();printline(50);insertionSort();printf("Mang sau thời điểm da sap xep: ");display();printline(50);

Hiển thị:

*

Sắp xếp lựa chọn (Selection Sort)

Thuật toán sắp xếp chọn là gì?

Giải thuật thu xếp chọn (Selection Sort) là một giải thuật đối kháng giản. Giải thuật sắp xếp này là một giải thuật dựa vào việc so sánh in-place, trong số ấy danh sách được chia thành hai phần, phần được thu xếp (sorted list) ở bên trái và phần không được sắp xếp (unsorted list) ở bên phải. Ban đầu, phần được bố trí là trống cùng phần không được sắp xếp là toàn bộ danh sách ban đầu.

Phần tử nhỏ tuổi nhất được tuyển lựa từ mảng không được sắp xếp với được tráo đổi với phần bên trái tốt nhất và bộ phận đó trở thành phần tử của mảng được sắp xếp. Các bước này tiếp tục tính đến khi toàn thể từng phần tử trong mảng không được sắp xếp hầu hết được dịch rời sang mảng vẫn được sắp đến xếp.

Ý tưởng bài bác toán
*
Minh họa thuật toán bố trí chọn

Thuật toán sắp xếp chọn sẽ bố trí một mảng bằng cách đi tìm bộ phận có giá trị nhỏ nhất(giả sử với thu xếp mảng tăng dần) trong khúc đoạn chưa được sắp xếp và đổi cho chỗ tử nhỏ nhất kia với thành phần ở đầu đoạn không được sắp xếp(không yêu cầu đầu mảng). Thuật toán sẽ phân tách mảng làm 2 mảng con

Một mảng con đã được sắp tới xếpMột mảng con không được sắp xếp

Tại từng bước một lặp của thuật toán, phần tử bé dại nhất làm việc mảng con không được sắp xếp đang được dịch chuyển về đoạn đã chuẩn bị xếp.

Sắp xếp chọn với ngôn từ C

Ví dụ minh họa: sắp xếp mảng từ rẻ tới cao với thuật toán sắp xếp chọn

*
*
*

Kết trái hiển thị

*

Ví dụ: cụ thể cách buổi giao lưu của sắp xếp chọn

#include #include #define MAX 7int intArray = 4,6,3,2,1,9,7;void printline(int count){int i;for(i = 0;i Hiển thị:

*

Sắp xếp trộn (Merge Sort)

Thuật toán thu xếp trộn là gì?

Sắp xếp trộn (Merge Sort) là một giải thuật bố trí dựa trên giải thuật Chia nhằm trị (Divide và Conquer). Với độ phức tạp thời gian trường hợp xấu duy nhất là Ο(n log n) thì đó là một trong số giải thuật xứng đáng được thân thương nhất.

Giải thuật sắp xếp trộn phân tách mảng thành nhị nửa liên tục, tới khi còn 1 phẩn tử và sau đó kết hợp chúng lại cùng nhau thành một mảng sẽ được chuẩn bị xếp.

Ý tưởng bài bác toán:
*
Minh họa thuật toán sắp xếp trộn

Hình hình ảnh dưới trên đây từ wikipedia đã hiển thị cho mình toàn cỗ sơ đồ quá trình của thuật toán merge sort cho mảng 38, 27, 43, 3, 9, 82, 10. Nếu chú ý kỹ hơn vào sơ trang bị này, chúng ta có thể thấy mảng ban đầu được lặp lại hành vi chia cho tới khi kích thước các mảng sau phân chia là 1.

Khi form size các mảng nhỏ là 1, tiến trình gộp sẽ bắt đầu thực hiện nay gộp lại các mảng này tính đến khi hoàn thành và chỉ từ một mảng đã sắp đến xếp.

*

Thuật toán sắp xếp trộn trong C

Ví dụ minh họa

#include #define max 10int a<10> = 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 ;int b<10>;void merging(int low, int mid, int high) int l1, l2, i;for(l1 = low, l2 = mid + 1, i = low; l1 hiện tại thị:

*

Sắp xếp nhanh (Quick Sort)

Thuật toán thu xếp nhanh là gì

Giải thuật thu xếp nhanh (Quick Sort) là một giải thuật kết quả cao và dựa trên việc phân tách mảng dữa liệu thành những mảng bé dại hơn. Lời giải sắp xếp cấp tốc chia mảng thành nhị phần bằng phương pháp so sánh từng phần tử của mảng với một trong những phần tử được chọn điện thoại tư vấn là phần tử chốt (Pivot): một mảng bao gồm các phần tử nhỏ dại hơn hoặc bằng phần tử chốt và mảng còn lại bao gồm các thành phần lớn rộng hoặc bằng bộ phận chốt.

Ý tưởng bài toán:
*
Mô tả thuật toán thu xếp quick sort

Giống như Merge sort, thuật toán thu xếp quick sort là một trong thuật toán phân tách để trị( Divide & Conquer algorithm). Nó chọn 1 phần tử trong mảng làm điểm tiến công dấu(pivot). Thuật toán sẽ thực hiện chia mảng thành các mảng con dựa vào pivot vẫn chọn. Bài toán lựa lựa chọn pivot ảnh hưởng rất các tới vận tốc sắp xếp. Nhưng máy vi tính lại quan trọng biết bao giờ thì nên lựa chọn theo biện pháp nào. Dưới đấy là một số phương pháp để chọn pivot thường được sử dụng:

Luôn chọn thành phần đầu tiên của mảng.Luôn chọn thành phần cuối cùng của mảng. (Được thực hiện trong nội dung bài viết này)Chọn 1 phần tử random.Chọn một phần tử có giá trị nằm giữa mảng(median element).Tầm quan trọng của phân đoạn vào thuật toán Quick Sort

Mấu chốt thiết yếu của thuật toán quick sort là việc phân đoạn dãy số (Xem hàm partition()). Mục tiêu của quá trình này là: cho một mảng và một trong những phần tử x là pivot. Đặt x vào đúng vị trí của mảng đã sắp đến xếp. Dịch chuyển tất cả các phần tử của mảng mà nhỏ hơn x sang phía bên trái vị trí của x, và di chuyển tất cả các phần tử của mảng mà to hơn x quý phái bên cần vị trí của x.

Khi đó ta sẽ sở hữu 2 mảng con: mảng bên trai của x với mảng bên đề xuất của x. Tiếp tục công việc với từng mảng con(chọn pivot, phân đoạn) tính đến khi mảng được sắp đến xếp.

Thuật toán phân đoạn

Đặt pivot là thành phần cuối thuộc của dãy số arr. Bọn chúng ta bước đầu từ phần tử trái độc nhất của dãy số tất cả chỉ số là left, và thành phần phải độc nhất của dãy số bao gồm chỉ số là right -1(bỏ qua phần tử pivot). Chừng như thế nào left pivot cùng arr

*
Minh họa quy trình phân đoạn trong thuật toán quick sort

Thuật toán sắp xếp nhanh vào C

Ví dụ minh họa

#include #define MAX 7int intArray = 4,6,3,2,1,9,7;void printline(int count)int i;for(i = 0;i 0 && intArray<--rightPointer> > pivot)//khong lam giif(leftPointer >= rightPointer)break;elseprintf(" Phan tu duoc trao doi :%d,%d ",intArray,intArray);swap(leftPointer,rightPointer);printf(" Phan tu chot duoc trao doi :%d,%d ", intArray,intArray);swap(leftPointer,right);printf("Hien thi mang sau moi lan trao doi: ");display();return leftPointer;// say mê sap xepvoid quickSort(int left, int right)if(right-left Hiển thị:

*

Shell Sort

Thuật toán bố trí Shell Sort là gì?

Shell Sort là 1 giải thuật sắp xếp mang lại kết quả cao dựa vào giải thuật sắp xếp chèn (Insertion Sort). Giải thuật này khá công dụng với những tập dữ liệu có kích cỡ trung bình khi nhưng mà độ tinh vi trường hòa hợp xấu nhất và trường hòa hợp trung bình là O(n), với n là số phần tử.

Giải thuật này tránh các trường hợp phải tráo đổi địa chỉ của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ dại hơn tại phần bên cần khá xa so với bộ phận lớn hơn mặt trái).

Đầu tiên, lời giải này sử dụng lời giải sắp xếp lựa chọn trên các bộ phận có khoảng cách xa nhau, kế tiếp sắp xếp các thành phần có khoảng cách hẹp hơn. Khoảng cách này có cách gọi khác là khoảng (interval) – là số địa chỉ từ phần tử này tới phần tử khác. Khoảng này được tính nhờ vào các loại cách làm sau

Shell’s original sequence: N/2 , N/4 , …, 1Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,...Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....

Cách Shell Sort chuyển động với bí quyết Shell’s original sequence

Ví dụ sắp xết dãy a = <9, 1, 3, 7, 8, 4, 2, 6, 5> thành dãy không giảm.

*

Với interval = 9/2 = 4, ta sẽ phân tách dãy thành những dãy con với những số bí quyết nhau một khoảng là interval: <9, 8, 5>, <1, 4>, <3, 2> và <7, 6>.

Sắp xếp các dãy nhỏ này theo cách sắp xếp chèn (Insertion Sort).

*

Sau khi sắp xếp các dãy bé dãy đã thành.

*

Với interval = 9/4 = 2, ta sẽ phân tách dãy thành các dãy nhỏ với những số phương pháp nhau một khoảng chừng là interval: <9, 8, 5>, <1, 4>, <3, 2> và <7, 6>.

*

Sau khi sắp xếp các dãy nhỏ dãy vẫn thành.

*

Với interval = 9/8 = 1, lúc này interval = 1 ta áp dụng sắp xếp chèn đối với cả dãy a:

*

Dãy sau khoản thời gian sắp xếp là:

*

Sắp xếp Shell trong xây dựng C

Ví dụ minh họa, bài xích tập vận dụng:

#include #include #define MAX 7int intArray = 4,6,3,2,1,9,7;void printline(int count)int i;for(i = 0;i 0) printf("Vong lap thu %d#:",i);display();for(outer = interval; outer interval -1 && intArray>= valueToInsert) intArray = intArray;inner -=interval;printf(" Di chuyen phan tu :%d ",intArray);intArray = valueToInsert;printf(" Chen phan tu :%d, tai vi tri :%d ",valueToInsert,inner);interval = (interval -1) /3;i++;int main() printf("Mang du lieu dau vao: ");display();printline(50);shellSort();printf("Mang ket qua: ");display();printline(50);return 1;Hiển thị:

*

Thuật toán bố trí đếm (Counting Sort)

Thuật toán bố trí đếm là gì?

Counting sort là một thuật toán sắp xếp cực nhanh một mảng các thành phần mà mỗi thành phần là các số nguyên ko âm; Hoặc là 1 trong những danh sách những ký trường đoản cú được ánh xạ về dạng số nhằm sort theo bảng chữ cái. Counting sort là một trong những thuật toán sắp tới xếp các con số nguyên không âm, không phụ thuộc vào so sánh.

Trong khi những thuật toán bố trí tối ưu sử dụng đối chiếu có độ phức hợp O(nlogn) thì Counting sort chỉ cần O(n) giả dụ độ nhiều năm của danh sách không quá nhỏ dại so với bộ phận có giá bán trị lớn nhất.

Ý tưởng bài bác toán

Hình hình ảnh dưới đây cho họ thấy cách hoạt động của thuật toán thu xếp này.

Bước 1:

Trong những bước đầu tiên tiên, cửa hàng chúng tôi đếm số lần mở ra của từng bộ phận trong mảng yêu cầu sắp xếp A. Hiệu quả được lưu vào mảng C.

Xem thêm: Tên Viết Tắt Bằng Tiếng Anh Của Trường Đại Học Công Nghệ Thông Tin

*

Bước 2: Ở cách này, chúng ta cần để mắt tới sửa đổi cực hiếm của C. C thể hiện giới hạn trên của chỉ số của phần tử i sau khi sắp đến xếp.

*

Bước 3: Duyệt qua từng phần tử của A và đặt nó vào đúng chỉ số của mảng chứa những giá trị đã chuẩn bị xếp B dựa vào C.

*

Thuật toán bố trí đếm trong C

Ví dụ minh họa

#include // Function that sort the given inputvoid counting_sort(int input<>, int n){ int output; // The đầu ra will have sorted đầu vào array int max = input<0>; int min = input<0>; int i; for(i = 1; i max) max = input; // Maximum value in array else if(input Kết quả:

Sorted Array : 1 1 2 3 4 4 5 5 7

Ví Dụ 2:

*
*
*

Hiển thị:

*

Thuật toán bố trí theo cơ số (Radix Sort)

Thuật toán sắp xếp cơ số là gì?

Sắp xếp dựa trên cơ số là 1 trong kỹ thuật sắp đến xếp các phần tử bằng phương pháp nhóm các chữ số riêng lẻ của một giá bán trị bao gồm cùng một vị trí. Sau đó, thu xếp các thành phần theo vật dụng tự tăng hoặc giảm.

Sắp xếp cơ số thường được dùng làm sắp xếp số có nhiều chữ số (số lớn)

Giả sử, họ có một mảng tất cả 8 phần tử. Đầu tiên, bọn họ sẽ bố trí các phần tử dựa trên quý hiếm của vị trí 1-1 vị. Sau đó, họ sẽ bố trí các phần tử dựa trên quý giá của vị trí thứ mười. Quy trình này tiếp tục cho tới vị trí cuối cùng.

Giả sử, ta gồm mảng thuở đầu là <121,432,564,23,1,45,788>. Nó được bố trí theo cơ số như vào hình mặt dưới.

*

Cách thức hoạt động vui chơi của thuật toán thu xếp theo cơ số.

Bước 1: tìm bộ phận lớn độc nhất vô nhị trong mảng, được hotline là biến đổi max. Gọi X là số chữ số trong biến đổi max. X có thể tính toán được bỏi vì họ phải đi qua tất cả các vị trí quan trọng của tất cả các phần tử. Vào mảng <121,432,564,23,1,45,788>, chúng ta có số lớn nhất là 788. Nó tất cả 3 chữ số. Bởi đó, vòng lặp sẽ lên đến mức chữ số mặt hàng trăm.Bước 2: bây giờ, ta lần lượt trải qua từng địa chỉ quan trọng.

Sử dụng bất kỳ kỹ thuật sắp xếp ổn định nào để sắp xếp các chữ số trên mỗi vị trí quan trọng. Chúng ta sử dụng thu xếp đếm cho bài toán này.

Sắp xếp các phần tử dựa trên những chữ số hàng đơn vị (X=0)

*

+ Sử dụng bố trí đếm để bố trí các bộ phận dựa bên trên vị trí

Bước 3: Bây giờ, ta sẽ sắp xếp các phần tử dựa trên những chữ số ở sản phẩm chục.

*

Bước 4: Cuối cùng, sắp xếp các phần tử dựa trên những chữ số ở trong phần hàng trăm.

*

Sắp xếp cơ số trong C

Ví dụ minh họa

*
*
*

Hiển thị:

*

Thuật toán sắp xếp theo khối (Bucket Sort)

Thuật toán thu xếp theo khối là gì?

Thuật toán bố trí dựa trên khối tuyệt Bucket Sort là 1 kỹ thuật chuẩn bị xếp các phần tử bằng phương pháp chia các phần tử thành một trong những nhóm được gọi là khối tuyệt Bucket ban đầu. Những phần tử bên trong mỗi nhóm được sắp xếp bằng phương pháp sử dụng bất kỳ thuật toán sắp tới xếp tương xứng nào hoặc call đệ quy đến cùng một thuật toán.

Một số đội được tạo nên ra. Từng nhóm chứa đầy hàng loạt các phần tử nhất định. Những phần tử phía bên trong nhóm được sắp xếp bằng phương pháp sử dụng bất kỳ thuật toán làm sao khác. Cuối cùng, các thành phần trong khối được tập phù hợp lại để có được mảng sắp xếp theo lắp thêm tự tuyệt nhất định.

Quá trình sắp xếp theo khối có thể được hiểu là 1 trong những cách tiếp cận phân chia và tập hợp. Đầu tiên các phần tử được phân tạo thành các nhóm tiếp đến các phần tử của những nhóm được chuẩn bị xếp. Cuối cùng, các bộ phận được tập thích hợp lại với nhau và được thu xếp theo một đơn côi tự.

*

*

*

Sắp xếp theo khối cùng với C

Ví dụ minh họa

*
*
*

*

Thuật toán sắp xếp vun lô (Heap Sort)

Thuật toán bố trí vun lô là gì?

Sắp xếp vun gò hay Heap Sort là một trong thuật toán sắp xếp thông dụng và tác dụng trong lập trình. Học biện pháp viết thuật toán sắp xếp vun đống đòi hỏi kiến thức về hai loại kết cấu dữ liệu là mảng cùng cây.

Tập phù hợp số lúc đầu mà chúng ta muốn thu xếp được lưu trữ trong một mảng, ví dụ, <12, 5, 78, 36, 25, 34> và sau khoản thời gian sắp xếp, bọn họ nhận được một mảng đã thu xếp là <5, 12, 25, 34, 36, 78>

Sắp xếp vun lô hoạt động bằng cách coi các bộ phận của mảng như một các loại cây nhị phân hoàn chỉnh quan trọng đặc biệt được gọi là Heap. Điều khiếu nại tiên quyết là bạn phải biết về cấu tạo dữ liệu Heap và cây nhị phân hoàn chỉnh.

Mối quan hệ tình dục giữa chỉ số của mảng và thành phần của cây

Một cây nhị phân hoàn hảo có một đặc tính mà chúng ta cũng có thể sử dụng để tìm nút nhỏ và nút cha của bất kỳ nút nào.

Nếu chỉ số của bất kỳ phần tử nào trong mảng là i, bộ phận trong chỉ số 2i+1 sẽ biến chuyển nút nhỏ bên trái và phần tử trong chỉ số 2i+2 sẽ phát triển thành nút nhỏ bên phải. Quanh đó ra, nút thân phụ của ngẫu nhiên phần tử như thế nào tại chỉ số i được mang lại bởi số lượng giới hạn dưới là (i-1)/2.

*

Nút bé bên trái của 3 (Chỉ số là 0)

= thành phần tại chỉ số (2*0+1)

= bộ phận trong chỉ tiên phong hàng đầu = 12

Nút con bên đề xuất của 3

= bộ phận tại chỉ số (2*0+2)

= bộ phận trong chỉ số 2 = 9

Tương tự,

Nút nhỏ bên trái của 14 (Chỉ số 1)

= thành phần tại chỉ số (2*1+1)

= bộ phận tại chỉ số 3 = 5

Nút con bên yêu cầu của 14

= bộ phận tại chỉ số (2*1+2)

= bộ phận tại chỉ số 4 = 6

Ta sẽ xác nhận rằng các quy tắc sẽ luôn luôn đúng cho việc tìm kiếm kiếm nút phụ thân của ngẫu nhiên nút nào

Nút cha của 11 (Vị trí 2)

= (2-1)/2 = một nửa = 0.5 ~ chỉ số 0

= 3

Nút cha của 14 (Vị trí 1)

= (1-1)/2 = chỉ số 0

= 3

Hiểu được việc ánh xạ của các chỉ số của mảng với những vị trí vào cây là rất quan trọng để gọi được phương pháp thức hoạt động vui chơi của cấu trúc tài liệu Heap và bí quyết nó được sử dụng để thực hiện sắp xếp vun đống.

Cấu trúc tài liệu Heap là gì?

Heap là một cấu tạo dữ liệu quan trọng dựa trên cấu tạo cây. Cây nhị phân biết đến tuân theo cấu tạo dữ liệu lô nếu

Nó là 1 trong những cây nhị phân hoàn chỉnh.

Tất cả những nút vào cây tuân theo ở trong tính cơ mà chúng khủng hơn bộ phận con của chúng, tức là phần tử lớn nhất nằm ở nút gốc và các thành phần con của nó nhỏ dại hơn nút gốc,…. Một Heap bởi thế được điện thoại tư vấn là Max heap. Nếu cầm vào đó, tất cả các nút đều nhỏ dại hơn nút nhỏ của chúng, nó được call là Min Heap.

Hình dưới đây đang minh họa về kết cấu dữ liệu Max Heap cùng Min Heap.

*

Làm gắng nào để để sản xuất một cấu tạo Heap cho 1 cây?

Bắt đầu xuất phát từ một cây nhị phân hoàn chỉnh, chúng ta cũng có thể sửa thay đổi nó để đổi thay Max Heap bằng phương pháp thực hiện một hàm mang tên là Heapify trên toàn bộ các bộ phận không bắt buộc là nút lá của Heap. Do hàm Heapify thực hiện đệ quy nên hoàn toàn có thể khó cố kỉnh bắt. Bởi vậy, trước tiên chúng ta hãy nghĩ về phong thái ta sẽ tạo nên Heap cho 1 cây chỉ với ba phần tử.

heapify(array)

Root = array<0>

Largest = largest( array<0> , array <2*0 + 1>. Array<2*0+2>)

if(Root != Largest)

Swap(Root, Largest)

*

*

Ví dụ trên chỉ dẫn 2 trường hợp, một trong những đó bao gồm nút nơi bắt đầu là bộ phận lớn độc nhất vô nhị và họ không đề nghị phải làm cái gi cả. Và một trong những phần tử khác trong các số ấy nút gốc có một nút con to hơn và chúng ta cần hoán đổi để duy trì thuộc tính Max Heap.

Nếu ta đã thao tác với các thuật toán đệ quy, ta hoàn toàn có thể đã xác định rằng đây cần là trường hợp cơ sở (trường hòa hợp để dứt lời call đệ quy).

Ví dụ 2:

*

Tuy nhiên, nút trên cùng chưa hẳn có cấu trúc Max Heap nhưng tất cả các cây con đều là Max Heap.

Để duy trì thuộc tính Max Heap cho toàn bộ cây, họ sẽ phải thường xuyên đẩy 2 cây xuống dưới cho tới khi nó đến đúng địa điểm của nó.

*

*

Do đó, để gia hạn thuộc tính Max Heap trong một cây cơ mà cả nhị cây nhỏ đều là Max Heap, chúng ta cần thực hiện quy trình Heapify bên trên nút gốc nhiều lần cho đến khi nó to hơn cây bé của nó hoặc nó vươn lên là một nút lá.

Chúng ta hoàn toàn có thể kết hợp cả hai điều kiện này vào một hàm Heapify như sau:

void heapify(int arr<>, int n, int i) int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left arr)largest = left;if (right arr)largest = right;if (largest != i) swap(&arr, &arr);heapify(arr, n, largest);Hàm này vận động hiệu quả đến trường hợp các đại lý và cho 1 cây có size bất kỳ. Bởi vì đó, chúng ta cũng có thể di đưa nút gốc mang đến vị trí đúng mực để gia hạn trạng thái Max Heap cho bất kỳ kích thước cây như thế nào miễn là các cây bé có cấu tạo Max Heap.

Xây dựng cấu tạo Max heap

Để chế tác Max Heap từ ngẫu nhiên cây nào, ta tất cả thể ban đầu xếp từng cây bé từ dưới lên và có được kết cấu Max Heap sau thời điểm hàm được vận dụng cho toàn bộ các phần tử bao hàm cả bộ phận gốc.

Trong trường vừa lòng của một cây trả chỉnh, chỉ số thứ nhất của một nút không hẳn nút lá được cho vì chưng n/2-1. Toàn bộ các nút khác tiếp đến là nút lá và vì chưng đó không nhất thiết phải tạo kết cấu heap mang lại nó nữa.

Vì vậy, bạn cũng có thể xây dựng một kết cấu Max heap như sau:

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

*

*

*

*

*

Như thể hiện trong sơ thứ trên, họ sẽ bắt đầu bằng phương pháp xếp vun đống cho các cây bé dại nhất thấp duy nhất và dần dần di đưa lên cho đến khi bọn họ đạt đến phần tử gốc.

Sắp xếp vun đống chuyển động như nào?

Vì cây vừa lòng thuộc tính Max Heap, nên bộ phận lớn tuyệt nhất được lưu trữ tại nút gốc.

Hoán đổi: nhiều loại bỏ thành phần gốc và đặt tại cuối mảng (vị trí sản phẩm n). Đặt thành phần cuối thuộc của cây (đống) vào nơi trống.

Xóa: Giảm size của Heap đi 1 1-1 vị.

Heapify: Tạo cấu trúc Heap cho phần tử gốc để họ có bộ phận cao nhất ở nút gốc.

Quá trình này được lặp lại cho tới khi toàn bộ các thành phần của danh sách được sắp đến xếp.

*

*

*

*

*

*

*

*

*

*

*

*

*

*

Sắp xếp vun đụn với C

Ví dụ minh họa

for (int i = n - 1; i >= 0; i--) swap(&arr<0>, &arr);//Tạo kết cấu heap cho phần tử gốc để lấy ra thành phần lớn nhấtheapify(arr, i, 0);#include void swap(int *a, int *b) int c = *a;*a = *b;*b = c;void heapify(int arr<>, int n, int i) int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left arr)largest = left;if (right arr)largest = right;if (largest != i) swap(&arr, &arr);heapify(arr, n, largest);void sort_heap(int arr<>, int n) for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);for (int i = n - 1; i >= 0; i--) swap(&arr<0>, &arr);heapify(arr, i, 0);void print(int arr<>, int n) {for (int i = 0; i Kết quả:

Mảng sau khi sắp xếp là:

3 7 8 11 12 14

Lời kết

Có rất nhiều loại thuật toán sắp đến xếp, trong bài bác này mình chỉ nêu ra một số phương thức thường sử dụng nhất và vận dụng chúng với ngữ điệu C. đề nghị nhớ những thuật toán có thể áp dụng cùng với bất kì ngôn từ nào, chỉ với cách xúc tiến chúng vào mỗi ngôn ngữ sẽ hơi khác biệt mà thôi