45
4
CFSDN nhấn mạnh vào giá trị tạo ra nguồn mở và chúng tôi cam kết xây dựng nền tảng chia sẻ tài nguyên để mọi nhân viên CNTT có thể tìm thấy thế giới tuyệt vời của bạn tại đây.
Bài viết blog CFSDN này triển khai các mã ví dụ thuật toán sắp xếp khác nhau trong ngôn ngữ C (lựa chọn, bong bóng, chèn, hợp nhất, Hill, sắp xếp nhanh, sắp xếp heap, đếm) do tác giả sưu tầm. Nếu bạn quan tâm đến bài viết này, hãy nhớ thích nó.
Nếu bạn đã quen với việc sử dụng các ngôn ngữ cấp cao, các công cụ nâng cao và các thuật toán nâng cao thì chắc chắn bạn sẽ cảm thấy xa lạ với một số thuật toán cơ bản. Tuy nhiên, thuật toán sắp xếp cơ bản nhất thực sự chứa khá nhiều tư duy tối ưu hóa và việc sử dụng thành thạo có thể có tác dụng rút ra các suy luận từ trường hợp này sang trường hợp khác.
。
Sắp xếp lựa chọn gần như là thuật toán sắp xếp ngớ ngẩn nhất. Bằng cách duyệt qua mảng một lần, giá trị lớn nhất (nhỏ nhất) được chọn và đặt đầu tiên trong mảng mới; sau đó giá trị lớn nhất (nhỏ nhất) được chọn từ các số còn lại trong mảng). , đặt nó ở vị trí thứ hai, v.v.
Các bước thuật toán
Giả sử mảng có n phần tử, { a 0 , a 1 , … , an } .
Vì mỗi lần truyền tải cần được tính toán O ( n ) lần và cần được tạo điều kiện thuận lợi n lần, nên độ phức tạp về thời gian là O ( n 2 )); do dữ liệu bổ sung chỉ được yêu cầu trong quá trình trao đổi, nên độ phức tạp của không gian là O ( n ) .
Triển khai ngôn ngữ C.
Trung tâm cá nhân
Điều phát hành
từ bỏ//sort.cvoid SelectionSort(double *p, int n);int main(){ double test[5] = {3,2,5,7,9}; SelectionSort(test,5); for (int i = 0; i < 5; i++) printf("%f\n", test[i]); return 0;}//Phân tích phương sai i,j void mySwap(double *arr, int i, int j){ double temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}//Phân tích phương sai void SelectionSort(double *arr, int n){ int pMax; double temp; for (int i = 0; i < n-1; i++){ pMax = i; đối với (int j = i+1; j < n; j++) nếu (arr[j]>arr[pMax]) pMax = j; mySwap(arr,pMax,i); }}
xác minh.
>gcc sort.c >a 9.000000 7.000000 5.000000 3.000000 2.000000 。
。
Sắp xếp bong bóng cũng là một phương pháp sắp xếp không cần não. Bằng cách truy cập liên tục vào mảng cần sắp xếp, so sánh hai phần tử liền kề, nếu thứ tự không đạt yêu cầu thì vị trí của hai số sẽ bị hoán đổi cho đến khi không cần hoán đổi.
Các bước thuật toán
Giả sử mảng có n phần tử, { a 0 , a 1 , … , an } .
Vì mỗi lần truyền cần được tính toán O ( n ) lần và cần được duyệt n lần, nên độ phức tạp về thời gian là O ( n 2 ) và độ phức tạp về không gian là O ( n ).
Triển khai ngôn ngữ C.
// Sắp xếp bong bóng void BubbleSort(double *arr, int n){ n = n-1; double temp; for (int i = 0; i < n; i++) for (int j = 0; j < ni; j++ ) if (arr[j]>arr[j+1]) mySwap(arr,i,j); /*hàm được xác định trước đó*/}
。
Sắp xếp chèn là thuật toán đầu tiên trong phần Giới thiệu về thuật toán, có nghĩa là nó không còn thiếu não nữa. Ý tưởng cơ bản là chia mảng thành hai phần, phần trước và phần sau, phần trước là mảng có thứ tự và phần sau là mảng không có thứ tự. Quét từng mảng không có thứ tự và chèn số được quét mỗi lần vào mảng có thứ tự. Bằng cách này, mảng có thứ tự sẽ ngày càng dài hơn và mảng không có thứ tự sẽ ngày càng ngắn hơn cho đến khi toàn bộ mảng được sắp xếp.
Các bước thuật toán
Giả sử mảng có n phần tử, { a 0 , a 1 , … , an } .
Có thể thấy, mỗi lần chèn của sắp xếp chèn có độ phức tạp là O(n), cần duyệt n n lần nên độ phức tạp về thời gian vẫn là O(n 2).
Triển khai ngôn ngữ C.
// Sắp xếp chèn void InsertionSort(double *arr, int n){ double temp; int j; for (int i = 1; i < n; i++){ j = i-1; temp=0){ arr[j+1] = arr[j]; // Di chuyển phần tử thứ j trở lại bằng j--; } arr[j+1] = temp; }}
。
Sắp xếp hợp nhất là một thuật toán sắp xếp được đề cập khi giới thiệu khái niệm chia để trị trong phần giới thiệu về thuật toán. Ý tưởng cơ bản của nó là chia mảng thành các mảng con, sau đó sắp xếp thứ tự các mảng con rồi sắp xếp các mảng sao cho sao cho sắp xếp hợp nhất. toàn bộ mảng có thể là chuỗi.
Các bước thuật toán
Giả sử mảng có n phần tử, { a 0 , a 1 , … , an } .
Có thể thấy rằng đối với một mảng có độ dài n nn, cần phải phân chia log 2 n. Mỗi mức phân chia có độ phức tạp thời gian là O ( n ) và độ phức tạp không gian là O ( n ), do đó độ phức tạp thời gian của nó là và độ phức tạp không gian. lần lượt là O ( n log 2 n ) và O(n).
Triển khai ngôn ngữ C.
Đầu tiên hãy xem xét vấn đề hợp nhất hai mảng có thứ tự.
//sort.cvoid myMerge(double *arr, int nL, int nR);int main(){ int n = 6; double arr[6] = {2,4,5,1,3,7}; mảng,3,3); for (int i = 0; i < n; i++) printf("%f\n", arr[i]); 0;}//Trộn hai mảng có thứ tự, arr là mảng đầu vào//nL, nR lần lượt là độ dài của mảng bên trái và mảng bên phải void Merge(double *arr, int nL, int nR){ nL = nL -1 ; //Chỉ số của phần tử cuối cùng bên trái int sInsert = 0; //Giá trị bắt đầu được chèn vào double temp; for (int i = 1; i <= nR; i++) { while (arr[nL+i]>arr[sInsert]) sInsert++; if (sInsert sInsert; j--) arr[j]=arr[j-1]; arr[sInsert] = temp } khác ngắt; //Nếu sInsert==nL+i, có nghĩa là chuỗi bên phải không cần chèn thêm}}
xác minh.
> gcc sort.c > a 1.000000 2.000000 3.000000 4.000000 5.000000 7.000000 。
Sau đó xem xét quá trình đệ quy của sắp xếp hợp nhất.
void MergeSort(double *arr, int n);void myMerge(double *arr, int nL, int nR);int main(){ int n = 6; 1,3}; MergeSort(arr,n); for (int i = 0; i < n; i++) printf("%f\n", arr[i]); return 0;}void MergeSort(double *arr, int n){ if (n>2) { int nL = n/2; (arr+nL,nR); Hợp nhất(arr,nL,nR); } else if(n==2) Hợp nhất(arr,1,1); //Khi n==1 nghĩa là mảng chỉ còn lại một phần tử nên không cần làm gì cả}
xác minh.
> gcc sort.c > a 1.000000 2.000000 3.000000 4.000000 5.000000 7.000000 。
Tại thời điểm này, thuật toán sắp xếp cuối cùng cũng có một chút hương vị thuật toán.
。
Nó được cho là thuật toán sắp xếp đầu tiên vượt qua O ( n 2 ), còn được gọi là sắp xếp tăng dần thu hẹp, về cơ bản là một sơ đồ chia để trị.
Trong sắp xếp hợp nhất, một mảng có độ dài n trước tiên được chia thành hai mảng có độ dài nL và nR, sau đó tiếp tục được chia cho đến khi độ dài của mỗi mảng không lớn hơn 2, sau đó mỗi mảng không lớn hơn 2 được sắp xếp . Bằng cách này, mỗi mảng con được sắp xếp nội bộ nhưng toàn bộ mảng không có thứ tự, sau đó mảng được sắp xếp lại được tổ chức lại cho đến khi nó lại trở thành một mảng có độ dài n.
Chiến lược phân chia của sắp xếp Hill thì khác. Sau khi chia mảng thành nL và nR, nR và nR được sắp xếp theo từng bit, sao cho nL và nR bị xáo trộn bên trong, nhưng thứ tự tổng thể được sắp xếp theo thứ tự. Sau đó, mảng được chia nhỏ. Khi độ dài của mảng trở thành 1, phần bên trong không còn bị xáo trộn nữa và tất cả các mảng có độ dài bằng 1 được sắp xếp theo thứ tự tổng thể. Có trật tự.
Các bước thuật toán
Giả sử mảng có n nn phần tử, { a 0 , a 1 , … , an } .
Triển khai ngôn ngữ C.
//Hill Sort void ShellSort(double *arr, int n){ double temp; int j; for (int nSub = n/2; nSub >0; nSub/=2) //nSub là độ dài của mảng con cho ( int i = nSub; i < n; i++) { temp = arr[i]; for (j = i-nSub; j >= 0&& temp
。
Chiến lược chia để trị của sắp xếp nhanh tương tự như sắp xếp Hill. Ý tưởng cốt lõi của nó là bắt đầu từ sự hỗn loạn trong nhóm và thứ tự giữa các nhóm. Khi độ dài của mảng con giảm xuống còn 1, toàn bộ mảng sẽ giảm. theo thứ tự.
Các bước thuật toán
Giả sử mảng có n nn phần tử, { a 0 , a 1 , … , an } .
Vì có một lựa chọn ngẫu nhiên trong quá trình sắp xếp nhanh nên độ phức tạp về thời gian của nó có thể bị ảnh hưởng bởi lựa chọn ngẫu nhiên này. Nếu bạn không may mắn, việc sắp xếp nhanh có thể trở thành sắp xếp bong bóng. Tất nhiên, nói chung, may mắn không đến nỗi tệ và độ phức tạp về thời gian trung bình của việc sắp xếp nhanh là O ( n log 2 n ).
Triển khai ngôn ngữ C.
//Sắp xếp nhanh void QuickSort(double *arr, int n){ double Pivot = arr[0] // Chọn điểm thứ 0 làm cơ sở int i = 1; { if (arr[i]pivot) i--; mySwap(arr,i,0); if (i>1) QuickSort(arr,i); //Sắp xếp nhanh mảng trước i i++; /Sắp xếp nhanh mảng sau i+1}
。
Heap là cấu trúc dữ liệu đầu tiên được giới thiệu trong phần giới thiệu về thuật toán. Về cơ bản, nó là một cây nhị phân. Heap tối đa yêu cầu giá trị của nút con không lớn hơn nút cha và điều ngược lại cũng đúng với heap tối thiểu. Vì vùng heap là cấu trúc dữ liệu có các nút nên việc biểu diễn cấu trúc sẽ trực quan hơn. May mắn thay, có một mối quan hệ đệ quy đơn giản giữa số sê-ri của nút cha và nút con của cây nhị phân, do đó vùng heap có thể được biểu diễn bằng một mảng trong ngôn ngữ C.
Theo hình trên, nếu số thứ tự của nút cha là n nn thì số thứ tự của nút con bên trái là 2 n + 1 và số thứ tự của nút con bên phải là 2 n + 2.
Hình trên có thể hiểu là một đống tối thiểu được sắp xếp. Nếu bit 1 trở thành 15 thì nút này sẽ vi phạm nguyên tắc heap tối thiểu. Sau khi so sánh, vị trí của 15 và 3 sẽ được hoán đổi. Sau khi trao đổi, 15 vẫn lớn hơn 7 và 8, khi đó vị trí của 15 và 7 được hoán đổi và đống tối thiểu trở thành.
Do đó, nó tiếp tục đáp ứng các thuộc tính của vùng heap tối thiểu và điều tương tự cũng đúng với vùng heap tối đa và việc triển khai ngôn ngữ C của nó như sau.
//Nếu điểm có số nút m trong heap không đáp ứng yêu cầu, hãy điều chỉnh điểm này //Đây là heap tối đa void adjustmentHeap(double *arr, int m, int n){ int left = m*2+1 ; // Nút trái while (leftarr[left]) break; //Nếu nút cha lớn hơn nút con, điều đó có nghĩa là vùng heap tổng hợp tối đa else{ mySwap(arr,m,left); *2+1;
Quá trình điều chỉnh heap là quá trình so sánh nút cha với hai nút con trái và phải của nó. Nghĩa là, heap thu được theo cách này có thể thỏa mãn mối quan hệ kích thước của nút cha và nút con, nhưng hai nút cháu. các nút sẽ không được sắp xếp. Tuy nhiên, nếu một mảng đã đáp ứng các yêu cầu về vùng heap tối đa thì tất cả các nút chỉ cần được sắp xếp lại ở nút gốc và vùng heap tối đa cuối cùng phải đáp ứng mối quan hệ có thứ tự giữa bất kỳ nút nào.
// Sắp xếp đống void HeapSort(double *arr, int n){ for (int i = n/2; i >= 0; i--) adjustmentHeap(arr,i,n); //Khởi tạo vùng heap cho (int i = n-1; i > 0 ; i--){ mySwap(arr,0,i); //Đặt các phần tử cần sắp xếp ở trên cùng adjustmentHeap(arr,0,i); } }
。
Tất cả các thuật toán sắp xếp trước đó đều không tính đến sự phân bố vốn có của mảng. Nếu dữ liệu chúng ta nhập là một số nguyên trong một khoảng nhất định thì chúng ta chỉ cần thiết lập một chỉ số nguyên trong khoảng này, sau đó phân loại từng số vào chỉ mục này. . Chỉ cần đánh nó.
Đây là ý tưởng của việc sắp xếp nhóm. Cái gọi là sắp xếp nhóm là chia dữ liệu đã biết thành nhiều phần có thứ tự và đặt chúng vào các nhóm khác nhau. Quá trình phân chia này là sắp xếp nhóm. Ngoài việc sắp xếp đếm, sắp xếp cơ số là một dạng sắp xếp nhóm rộng hơn, có thể chia cho số bit trong dữ liệu và nhóm được xác định là giá trị của bit cao nhất của dữ liệu.
Ví dụ: chúng ta có một tập hợp dữ liệu được phân bổ đều trong [0, 100] Cái gọi là sắp xếp cơ số trước tiên là chia thành 10 nhóm khác nhau [0, 10), [10, 20), …, [90, 100 ) , rồi sắp xếp từng nhóm riêng lẻ. Nếu chia theo cách này thì độ phức tạp của việc sắp xếp cơ số là O (10 ∗ n).
Cách sắp xếp trong từ điển cũng có thể hiểu là sắp xếp cơ số, tức là trước tiên nhìn vào thứ tự của chữ cái đầu tiên, sau đó là chữ cái thứ hai, v.v. Vì việc sắp xếp nhóm đưa ra các giả định về dữ liệu nên độ phức tạp về thời gian tối ưu của nó có thể đạt tới O ( n + k ), trong đó k là số lượng nhóm.
Ví dụ: nếu chúng ta có một mảng gồm một trăm mục 1 và 2, thì chúng ta chỉ cần tạo chỉ mục 1: n 1, 2: n 2, sau đó đếm số lần xuất hiện của 1 và 2. phức tạp Mức độ cũng sẽ trở thành O(n).
Ở đây chỉ có cách sắp xếp đếm đơn giản nhất được thực hiện.
/Đếm sắp xếp, mảng đầu vào là một số nguyên void CountingSort(int *arr,int n){ int aMax = arr[0]; int aMin = arr[0] for (int i = 0; i < n; i++) // Tìm giá trị lớn nhất và nhỏ nhất if (arr[i]>aMax) aMax = arr[i]; else if (arr[i]
。
Phần này kết thúc bài viết này về việc triển khai các thuật toán sắp xếp khác nhau (lựa chọn, tạo bong bóng, chèn, hợp nhất, Hill, sắp xếp nhanh, sắp xếp theo đống, đếm) trong ngôn ngữ C. Vui lòng liên quan nhiều hơn đến việc triển khai các thuật toán sắp xếp khác nhau trong ngôn ngữ C. tìm kiếm các bài viết trước của tôi hoặc tiếp tục duyệt các bài viết liên quan bên dưới, tôi hy vọng bạn sẽ ủng hộ tôi trong tương lai! .
Liên kết gốc: https://blog.csdn.net/m0_37816922/article/details/103439486.
Cuối cùng, bài viết này về việc triển khai các mã ví dụ thuật toán sắp xếp khác nhau trong ngôn ngữ C (lựa chọn, bong bóng, chèn, hợp nhất, Hill, sắp xếp nhanh, sắp xếp theo đống, đếm) kết thúc tại đây nếu bạn muốn biết thêm về cách triển khai ngôn ngữ C. các mã ví dụ về thuật toán sắp xếp khác nhau (lựa chọn, bong bóng, chèn, hợp nhất, Hill, sắp xếp nhanh, sắp xếp đống, đếm), vui lòng tìm kiếm các bài viết CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .
45
4
0
Lời nói đầu: Tôi đã quen với việc sử dụng các ngôn ngữ cấp cao, các công cụ nâng cao và các thuật toán nâng cao nên khó tránh khỏi cảm giác xa lạ với một số thuật toán cơ bản. Tuy nhiên, thuật toán sắp xếp cơ bản nhất thực sự chứa khá nhiều tư duy tối ưu hóa và việc sử dụng thành thạo có thể có tác dụng rút ra các suy luận từ trường hợp này sang trường hợp khác. Sắp xếp lựa chọn Sắp xếp lựa chọn gần như
Tôi là một lập trình viên xuất sắc, rất giỏi!