Thuật toán sắp xếp tốt nhất trong JavaScript là gì?

Trả lời các câu hỏi nâng cao hơn để hoàn toàn sẵn sàng phỏng vấn. Kiểm tra bài kiểm tra ở cuối. Đọc blog này để đạt điểm tuyệt đối trong bài kiểm tra đó. )

---

Việc sắp xếp dữ liệu theo một thứ tự cụ thể (tăng dần hoặc giảm dần) được gọi là sắp xếp trong cấu trúc dữ liệu. Sắp xếp dữ liệu giúp tìm kiếm thông qua một mẫu dữ liệu nhất định dễ dàng hơn, hiệu quả và nhanh chóng

Tại sao các thuật toán sắp xếp lại quan trọng?

Vì việc sắp xếp thường có thể giúp giảm độ phức tạp thuật toán của một vấn đề, nên nó được sử dụng đáng kể trong khoa học máy tính

Tìm kiếm nhanh trên Google cho thấy có hơn 40 thuật toán sắp xếp khác nhau được sử dụng trong thế giới điện toán ngày nay. Điên phải không?

Chà, bạn sẽ sửng sốt khi nhận ra các thuật toán sắp xếp hữu ích như thế nào trong cuộc sống thực. Một số ví dụ tốt nhất về triển khai trong thế giới thực giống nhau là

• Sắp xếp bong bóng được sử dụng trong lập trình TV để sắp xếp các kênh dựa trên thời gian xem của khán giả
• Cơ sở dữ liệu sử dụng sắp xếp hợp nhất bên ngoài để sắp xếp các bộ dữ liệu quá lớn để tải hoàn toàn vào bộ nhớ
• Tỷ số thể thao được sắp xếp nhanh chóng bằng thuật toán sắp xếp nhanh theo thời gian thực

---

Làm thế nào để bạn biết các thuật toán sắp xếp của bạn?

---

Các kiểu sắp xếp trong cấu trúc dữ liệu

Bạn muốn cải thiện các thuật toán sắp xếp của mình trước một cuộc phỏng vấn?

• Sắp xếp dựa trên so sánh. Trong các kỹ thuật sắp xếp dựa trên so sánh, một bộ so sánh được định nghĩa để so sánh các phần tử hoặc mục của một mẫu dữ liệu. Bộ so sánh này xác định thứ tự của các phần tử. Ví dụ là. Sắp xếp bong bóng, Sắp xếp hợp nhất
• sắp xếp dựa trên đếm. Không có so sánh liên quan giữa các phần tử trong các loại thuật toán sắp xếp này mà hoạt động dựa trên các giả định được tính toán trong quá trình thực thi. Ví dụ là. Sắp xếp đếm, Sắp xếp cơ số
• Sắp xếp tại chỗ và không tại chỗ. Kỹ thuật sắp xếp tại chỗ trong cấu trúc dữ liệu sửa đổi thứ tự của các phần tử mảng trong mảng ban đầu. Mặt khác, kỹ thuật sắp xếp Not-in-Place sử dụng cấu trúc dữ liệu phụ trợ để sắp xếp mảng ban đầu. Ví dụ về kỹ thuật sắp xếp tại chỗ là. Sắp xếp bong bóng, Sắp xếp lựa chọn. Một số ví dụ về thuật toán sắp xếp Not in Place là. Sắp xếp Hợp nhất, Sắp xếp Nhanh

Mọi thứ bạn cần biết về sắp xếp hợp nhất

Tìm hiểu các nguyên tắc cơ bản của Sắp xếp hợp nhất với một ví dụ. Nâng cao hiểu biết của bạn với các câu đố và hoạt động thú vị

Blog CrioAbheetha Pradhan

Hướng dẫn sắp xếp nhanh hoàn chỉnh

Tìm hiểu các nguyên tắc cơ bản của Sắp xếp nhanh với một ví dụ. Nâng cao hiểu biết của bạn với các câu đố và hoạt động thú vị

Blog CrioAbheetha Pradhan

Bài viết này sẽ nâng cao kỹ năng giải quyết vấn đề của bạn với 10 thuật toán sắp xếp hàng đầu được sử dụng trong thế giới điện toán ngày nay bao gồm thuật toán sắp xếp bong bóng và sắp xếp hợp nhất

Bạn cũng sẽ đi sâu vào hoạt động của các kỹ thuật sắp xếp khác nhau với các ví dụ trực quan bao gồm sự phức tạp về thời gian và không gian trong các tình huống tốt nhất và xấu nhất

Độ phức tạp của thời gian được đơn giản hóa với các ví dụ dễ dàng

Tìm hiểu độ phức tạp của thời gian là gì. Hiểu cách phân tích độ phức tạp của thời gian với các ví dụ đơn giản

Blog CrioSandipan Das

Cuối cùng, chúng ta sẽ kết thúc với một phân tích phổ rộng để xem thuật toán nào nổi bật về độ phức tạp của thời gian và không gian

Thuật toán sắp xếp trong Java so với C++

Java là ngôn ngữ được lựa chọn phổ biến nhất khi triển khai các thuật toán và làm việc với các cấu trúc dữ liệu trong ngành công nghiệp phần mềm

---

Nâng cao kỹ năng lập trình nền tảng của bạn trong Java và thực hành các câu hỏi về Cấu trúc dữ liệu phù hợp nhất trong Chương trình nhà phát triển phụ trợ của Crio.

---

Mặc dù blog này tập trung chủ yếu vào việc triển khai dựa trên C++, nhưng đừng lo lắng vì miễn là bạn hiểu rõ về các thuật toán này, thì điều duy nhất cản trở bạn là sự khác biệt về cú pháp cơ bản giữa Java và C++

---

Bạn muốn xây dựng nền tảng của các khái niệm Java?

---

Vì vậy, không có gì khó chịu, hãy đi sâu vào ngay

---

Cần hướng dẫn giải quyết vấn đề và cấu trúc dữ liệu? .  

---

Top 10 thuật toán sắp xếp bạn cần biết

10 thuật toán sắp xếp tốt nhất

1. Sắp xếp bong bóng

Ý tưởng cơ bản của sắp xếp bong bóng là nó liên tục hoán đổi các phần tử liền kề nếu chúng không theo thứ tự mong muốn. CÓ, nó đơn giản như vậy

Nếu một mảng các phần tử nhất định phải được sắp xếp theo thứ tự tăng dần, sắp xếp theo bong bóng sẽ bắt đầu bằng cách so sánh phần tử đầu tiên của mảng với phần tử thứ hai và ngay lập tức hoán đổi chúng nếu nó lớn hơn phần tử thứ hai, rồi tiếp tục

Hiểu thuật toán Sắp xếp bong bóng với một ví dụ đơn giản

Hãy cố gắng hiểu cách tiếp cận trực quan đằng sau sắp xếp bong bóng với một ví dụ

Giải thích thuật toán sắp xếp bong bóng

Bây giờ bạn đã hiểu ý tưởng trực quan đằng sau sắp xếp bong bóng, đã đến lúc xem cách triển khai C++ tiêu chuẩn của nó

Triển khai trong C++

#include 
using namespace std;

void Bubble_Sort(int vec[], int n){
	int i, j;
	for (i = 0; i < n-1; i++)
	for (j = 0; j < n-i-1; j++)
		if (vec[j] > vec[j+1])
			swap(vec[j], vec[j+1]);
}
int main(){
	int vec[] = {5, 3, 4, 2, 1};
	int n = sizeof(vec)/sizeof(vec[0]);
	Bubble_Sort(vec, n);
	cout<<"Sorted array: \n";
	for (int i = 0; i < n; i++)
		cout << vec[i] << " ";
	cout << endl;
}

Triển khai sắp xếp bong bóng

Thời gian phức tạp

• Trường hợp xấu nhất. O(n^2)
• trường hợp trung bình. O(n*logn)
• Trường hợp tốt nhất. O(n*logn)

Độ phức tạp không gian phụ trợ. Ô(1)

Cũng đọc. Độ phức tạp của thời gian được đơn giản hóa với các ví dụ dễ dàng

Trường hợp sử dụng

• Nó được sử dụng để giới thiệu khái niệm thuật toán sắp xếp cho sinh viên Khoa học Máy tính
• Trong đồ họa máy tính, sắp xếp bong bóng khá phổ biến khi phát hiện một lỗi rất nhỏ (như hoán đổi chỉ hai phần tử) trong các mảng được sắp xếp gần hết

Hãy tự mình thử

Q. Cho một mảng gồm n số nguyên nhập vào, trả về tổng các phần tử lớn nhất và nhỏ nhất của mảng. [Hạn chế. Sử dụng Sắp xếp bong bóng]

Đầu vào

• n -> Kích thước của mảng (n>1)
• 'n' phần tử mảng bên dưới

đầu ra. Một dòng duy nhất đại diện cho tổng cần thiết

P. S. Đừng quên để lại bình luận bên dưới nếu bạn gặp vấn đề với vấn đề này

---

2. Sắp xếp lựa chọn

Sắp xếp lựa chọn là một thuật toán sắp xếp trong đó mảng đã cho được chia thành hai mảng con, phần bên trái đã sắp xếp và phần bên phải chưa sắp xếp

Ban đầu, phần được sắp xếp trống và phần chưa được sắp xếp là toàn bộ danh sách. Trong mỗi lần lặp lại, chúng tôi lấy phần tử tối thiểu từ danh sách chưa sắp xếp và đẩy nó vào cuối danh sách đã sắp xếp, do đó xây dựng mảng được sắp xếp của chúng tôi

Vẫn còn một chút mờ?

Hiểu thuật toán Sắp xếp lựa chọn với một ví dụ

Hãy cố gắng hiểu ý tưởng trực quan đằng sau sắp xếp lựa chọn bằng một ví dụ đơn giản

Giải thích thuật toán sắp xếp lựa chọn

Có vẻ dễ dàng phải không?

Bây giờ hãy tiếp tục và xem triển khai dựa trên C++ cơ bản của nó

#include 
using namespace std;

void Selection_Sort(int vec[], int n){
	int i, j, pos;
	for (i = 0; i < n-1; i++){
		pos = i;
		for (j = i+1; j < n; j++)
		if (vec[j] < vec[pos])
			pos = j;
		swap(vec[pos], vec[i]);
	}
}

int main(){
	int vec[] = {25, 22, 27, 15, 19};
	int n = sizeof(vec)/sizeof(vec[0]);
	Selection_Sort(vec, n);
	cout << "Sorted array: \n";
	for (int i=0; i < n; i++)
		cout << vec[i] << " ";
	cout << endl;
	return 0;
}

Thực hiện Sắp xếp Lựa chọn

Thời gian phức tạp

• Trường hợp xấu nhất. O(n*n)
• trường hợp trung bình. O(n*logn)
• Trường hợp tốt nhất. O(n*logn)

Độ phức tạp không gian phụ trợ. Ô(1)

Cũng đọc. Độ phức tạp của thời gian được đơn giản hóa với các ví dụ dễ dàng

Trường hợp sử dụng

• Nó được sử dụng khi kích thước của một danh sách nhỏ. (Độ phức tạp về thời gian của sắp xếp lựa chọn là O(N^2) khiến nó không hiệu quả đối với một danh sách lớn. )
• Nó cũng được sử dụng khi không gian bộ nhớ bị hạn chế vì nó tạo ra số lượng hoán đổi tối thiểu có thể trong quá trình sắp xếp

Hãy tự mình thử

Q. Cho một mảng gồm n số nguyên đầu vào, trả về sự khác biệt tuyệt đối giữa các phần tử lớn nhất và nhỏ nhất của mảng. [Hạn chế. Sử dụng Sắp xếp lựa chọn]

Đầu vào

• n -> Kích thước của mảng (n>1)
• 'n' phần tử mảng bên dưới

đầu ra. Một dòng duy nhất thể hiện sự khác biệt cần thiết

---

Xây dựng và làm chủ các thuật toán và cấu trúc dữ liệu thiết yếu mà bạn cần để vượt qua cuộc phỏng vấn công nghệ lớn tiếp theo của mình

---

3. Sắp xếp chèn

Sắp xếp chèn là thuật toán sắp xếp trong đó mảng đã cho được chia thành phần đã sắp xếp và phần chưa sắp xếp. Trong mỗi lần lặp, phần tử được chèn phải tìm vị trí tối ưu của nó trong dãy con đã sắp xếp và sau đó được chèn vào trong khi dịch chuyển các phần tử còn lại sang phải

Sắp xếp chèn chính trước cuộc phỏng vấn lớn tiếp theo của bạn

Tìm hiểu chi tiết về sắp xếp chèn và cách bạn có thể sử dụng nó một cách hiệu quả để sắp xếp tập dữ liệu của mình

Blog CrioHarshita Bansal

Hiểu thuật toán Sắp xếp Chèn với một ví dụ

Đây là một ví dụ để giúp bạn hiểu rõ hơn về sắp xếp chèn

Giải thích thuật toán sắp xếp chèn

Bây giờ bạn đã hiểu cách sắp xếp chèn thực sự hoạt động như thế nào, hãy xem triển khai C++ tiêu chuẩn của nó

#include 
using namespace std;

void Insertion_Sort(int vec[], int n){
	int i, x, j;
	for (i = 1; i < n; i++){
		x = vec[i];
		j = i - 1;
		while (j >= 0 && vec[j] > x){
			vec[j + 1] = vec[j];
			j = j - 1;
		}
		vec[j + 1] = x;
	}
}

int main(){
	int vec[] = { 25, 22, 27, 15, 19 };
	int n = sizeof(vec) / sizeof(vec[0]);
	Insertion_Sort(vec, n);
	for (int i = 0; i < n; i++)
		cout << vec[i] << " ";
	return 0;
}

Thực hiện sắp xếp chèn

Thời gian phức tạp

• Trường hợp xấu nhất. O(n*n)
• trường hợp trung bình. O(n*logn)
• Trường hợp tốt nhất. O(n*logn)

Độ phức tạp không gian phụ trợ. Ô(1)

Trường hợp sử dụng

• Thuật toán này ổn định và khá nhanh khi sắp xếp xong danh sách
• Nó rất hiệu quả khi sắp xếp các danh sách rất nhỏ (ví dụ: 30 phần tử. )

Hãy tự mình thử

Q. Cho một dãy số có số phần tử lẻ, tìm trung vị? . Sử dụng Sắp xếp Chèn]

Đầu vào

• n -> Kích thước của mảng (n>0)
• 'n' phần tử mảng bên dưới

đầu ra. Một dòng duy nhất đại diện cho trung vị cần thiết

P. S. Đừng quên chia sẻ cách tiếp cận của bạn với chúng tôi trong phần bình luận bên dưới

---

4. Sắp xếp nhanh chóng

Quick Sort là thuật toán chia để trị. Ý tưởng trực quan đằng sau sắp xếp nhanh là nó chọn một phần tử làm trục từ một mảng các phần tử đã cho và sau đó phân vùng mảng xung quanh phần tử trục. Sau đó, nó gọi chính nó theo cách đệ quy và phân vùng hai mảng con sau đó

Tìm hiểu thuật toán Sắp xếp nhanh bằng hình ảnh trực quan

Giải thích thuật toán sắp xếp nhanh

Các bước hợp lý liên quan đến thuật toán Quick Sort như sau

• lựa chọn trục. Chọn một phần tử làm trục (ở đây, chúng tôi chọn phần tử cuối cùng làm trục)
• phân vùng. Mảng được phân vùng theo kiểu sao cho tất cả các phần tử nhỏ hơn trục nằm trong mảng con bên trái trong khi tất cả các phần tử lớn hơn hoàn toàn so với phần tử trục được lưu trữ trong mảng con bên phải
• Gọi đệ quy tới Quicksort. Hàm Quicksort được gọi lại cho hai mảng con được tạo ở trên và các bước được lặp lại

Các comment đã được đưa vào phần triển khai bên dưới để giúp các bạn hiểu rõ hơn về thuật toán Quick Sort

#include 
using namespace std;
 
int partition (int vec[], int lt, int rt){
	int pivot = vec[rt]; // pivot
	int i = (lt - 1);
	for (int j = lt; j <= rt - 1; j++){
		if (vec[j] < pivot){
			i++; swap(vec[i], vec[j]);
		}
	}
	swap(vec[i + 1], vec[rt]);
	return (i + 1);
}
 
/* vec[] --> array to be sorted,
lt --> Starting index,
rt --> Ending index*/
void Quick_Sort(int vec[], int lt, int rt){
	if (lt < rt){
		/* mid is partitioning index, vec[p] is now
		at right place */
		int mid = partition(vec, lt, rt);
		// Separately sort elements before
		// partition and after partition
		Quick_Sort(vec, lt, mid - 1);
		Quick_Sort(vec, mid + 1, rt);
	}
}
 
int main(){
	int vec[] = {14, 21, 5, 2, 3, 19};
	int n = sizeof(vec) / sizeof(vec[0]);
	Quick_Sort(vec, 0, n - 1);
	cout << "Sorted array: ";
	for (int i = 0; i < n; i++)
		cout << vec[i] << " ";
	return 0;
}

Thực hiện Sắp xếp Nhanh

Thời gian phức tạp

• Trường hợp xấu nhất. O(n*n)
• trường hợp trung bình. O(n*logn)
• Trường hợp tốt nhất. O(n*logn)

Độ phức tạp không gian phụ trợ. Ô(1)

Trường hợp sử dụng

• Sắp xếp nhanh có lẽ hiệu quả hơn đối với các bộ dữ liệu phù hợp với bộ nhớ
• Sắp xếp nhanh phù hợp với mảng vì đây là thuật toán sắp xếp tại chỗ (i. e. nó không yêu cầu bất kỳ bộ nhớ bổ sung nào)

Hãy tự mình thử

Q. Đưa ra một danh sách các số có số phần tử lẻ/chẵn, hãy tìm trung vị? . Sử dụng Sắp xếp Nhanh]

Đầu vào

• n -> Kích thước của mảng (n>0)
• 'n' phần tử mảng bên dưới

đầu ra. Một dòng duy nhất đại diện cho trung vị cần thiết

P. S. Cần một gợi ý?

---

5. Hợp nhất Sắp xếp

Hợp nhất Sắp xếp là thuật toán chia để trị. Trong mỗi lần lặp lại, sắp xếp hợp nhất chia mảng đầu vào thành hai mảng con bằng nhau, gọi chính nó theo cách đệ quy cho hai mảng con và cuối cùng hợp nhất hai nửa đã sắp xếp

Mọi thứ bạn cần biết về sắp xếp hợp nhất

Tìm hiểu các nguyên tắc cơ bản của Sắp xếp hợp nhất với một ví dụ. Nâng cao hiểu biết của bạn với các câu đố và hoạt động thú vị

Blog CrioAbheetha Pradhan

Hiểu thuật toán Sắp xếp hợp nhất với trực quan hóa

Giải thích thuật toán sắp xếp hợp nhất

Bây giờ bạn đã quen thuộc với trực giác đằng sau sắp xếp hợp nhất, hãy xem cách triển khai nó

#include 
using namespace std;

void merge(long vec[], long lt, long m, long rt){
    long n1 = m - lt + 1;
    long n2 = rt - m;
    long L[n1], R[n2];
    for (long i = 0; i < n1; i++)
        L[i] = vec[lt + i];
    for (long j = 0; j < n2; j++) R[j] = vec[m+1+j];
    long i = 0, j = 0;
    long k = lt;
    while (i < n1 and j < n2) {
        if (L[i] <= R[j]) {
            vec[k] = L[i]; i++;
        }
        else {
            vec[k] = R[j]; j++;
        }
        k++;
    }
    while (i < n1) {
        vec[k] = L[i]; i++; k++;
    }
    while (j < n2) {
        vec[k] = R[j]; j++; k++;
    }
}

void Merge_Sort(long vec[],long lt,long rt){
    if(lt>=rt) return;
    long m =lt+ (rt-lt)/2;
    Merge_Sort(vec,lt,m);
    Merge_Sort(vec,m+1,rt);
    merge(vec,lt,m,rt);
}

void printArray(long A[], long size){
    for (long i = 0; i < size; i++)
        cout << A[i] << " ";
}
int main(){
    long arr[] = {16, 19, 14, 20, 12, 13};
    long arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << "Unsorted array is: ";
    printArray(arr, arr_size);
    Merge_Sort(arr, 0, arr_size - 1);
    cout << "\nSorted array is: ";
    printArray(arr, arr_size);
    return 0;
}

Thực hiện sắp xếp hợp nhất

Thời gian phức tạp

• Trường hợp xấu nhất. O(n*logn)
• trường hợp trung bình. O(n*logn)
• Trường hợp tốt nhất. O(n*logn)

Độ phức tạp không gian phụ trợ. Trên)

Trường hợp sử dụng

• Hợp nhất sắp xếp khá nhanh trong trường hợp danh sách được liên kết
• Nó được sử dụng rộng rãi để sắp xếp bên ngoài nơi truy cập ngẫu nhiên có thể khá tốn kém so với truy cập tuần tự

Hãy tự mình thử

Q. Tìm giao điểm của hai mảng chưa sắp xếp [Ràng buộc/Gợi ý. Sử dụng Sắp xếp hợp nhất]

Đầu vào

• n -> Kích thước của mảng (n>1)
• 'n' phần tử mảng bên dưới

đầu ra. Một mảng đại diện cho giao điểm của hai mảng chưa được sắp xếp

---

Làm chủ Mảng, Danh sách được liên kết, Ngăn xếp/Hàng đợi, Cây và Đồ thị và xây dựng sự nghiệp của bạn (với đảm bảo công việc) trong phát triển Back End hoặc Full Stack. Đây là

---

6. sắp xếp đếm

Sắp xếp đếm là một kỹ thuật sắp xếp thú vị chủ yếu vì nó tập trung vào tần suất của các phần tử duy nhất giữa một phạm vi cụ thể (một cái gì đó dọc theo dòng băm)

Nó hoạt động bằng cách đếm số phần tử có các giá trị khóa riêng biệt và sau đó xây dựng một mảng được sắp xếp sau khi tính toán vị trí của từng phần tử duy nhất trong chuỗi chưa sắp xếp

Nó khác biệt so với các thuật toán được liệt kê ở trên bởi vì nó thực sự liên quan đến việc so sánh bằng không giữa các phần tử dữ liệu đầu vào

Hiểu thuật toán Sắp xếp Đếm với một ví dụ

Giải thích thuật toán sắp xếp đếm

Bây giờ hãy tiếp tục và nhanh chóng xem cách triển khai nó trong C++

#include
using namespace std;

void print(long *vec, long n) {
   for(long i = 1; i<=n; i++)
      cout << vec[i] << " ";
   cout << "\n";
}

long getMax(long vec[], long n) {
   long max = vec[1];
   for(long i = 2; i<=n; i++) {
      if(vec[i] > max)
         max = vec[i];
   }
   return max;
}
void countSort(long *vec, long n) {
   long output[n+1];
   long max = getMax(vec, n);
   long count[max+1];
   for(long i = 0; i<=max; i++)
      count[i] = 0;
   for(long i = 1; i <=n; i++)
      count[vec[i]]++;
   for(long i = 1; i<=max; i++)
      count[i] += count[i-1];
   for(long i = n; i>=1; i--) {
      output[count[vec[i]]] = vec[i];
      count[vec[i]] -= 1;
   }
   for(long i = 1; i<=n; i++) {
      vec[i] = output[i];
   }
}
int main() {
   long n;
   cout << "Enter the size of array: ";
   cin >> n;
   long arr[n+1];
   cout << "Enter elements:" << endl;
   for(long i = 1; i<=n; i++)
      cin >> arr[i];
   cout << "Unsorted array: ";
   print(arr, n);
   countSort(arr, n);
   cout << "Sorted array: ";
   print(arr, n);
}

Thực hiện Sắp xếp Đếm

Thời gian phức tạp

• Trường hợp xấu nhất. O(n+k), trong đó n là kích thước của mảng đầu vào và k là số phần tử duy nhất trong mảng

Độ phức tạp không gian phụ trợ. O(n+k)

Trường hợp sử dụng

• Sắp xếp đếm khá hiệu quả khi sắp xếp các đối tượng đếm được (chẳng hạn như số nguyên bị chặn)
• Nó cũng được sử dụng khi sắp xếp đạt được độ phức tạp tuyến tính

Hãy tự mình thử

Q. Đưa ra một mảng gồm n số nguyên đầu vào, trả về sự khác biệt tuyệt đối giữa các phần tử tối đa và tối thiểu của mảng theo độ phức tạp thời gian tuyến tính

Đầu vào

• n -> Kích thước của mảng (n>1)
• 'n' phần tử mảng bên dưới

đầu ra. Một dòng duy nhất thể hiện sự khác biệt cần thiết

P. S. Đừng quên chia sẻ cách tiếp cận của bạn với chúng tôi trong phần bình luận bên dưới

---

Dừng cuộn

Bạn đã hoàn thành hơn 50% blog. Bạn muốn kiểm tra kiến ​​thức của mình xem bạn đã hiểu các thuật toán sắp xếp đến mức nào?

Bài kiểm tra thuật toán sắp xếp (Cấp 1)Bài kiểm tra thuật toán sắp xếp (Cấp 2)

---

7. Sắp xếp cơ số

Như bạn đã thấy trước đó, sắp xếp đếm khác biệt vì nó không phải là thuật toán sắp xếp dựa trên so sánh như Sắp xếp hợp nhất hoặc Sắp xếp bong bóng, do đó giảm độ phức tạp về thời gian của nó thành thời gian tuyến tính

NHƯNG, sắp xếp đếm không thành công nếu mảng đầu vào nằm trong khoảng từ 1 đến n^2, trong trường hợp đó độ phức tạp thời gian của nó tăng lên O(n^2)

Ý tưởng cơ bản đằng sau sắp xếp cơ số là mở rộng chức năng sắp xếp đếm để có độ phức tạp về thời gian tốt hơn khi các phần tử mảng đầu vào nằm trong khoảng từ 1 đến n^2

Hiểu Radix Sort với một ví dụ

thuật toán

Đối với mỗi chữ số i trong đó i thay đổi từ chữ số có nghĩa nhỏ nhất đến chữ số có nghĩa nhất của một số, hãy sắp xếp mảng đầu vào bằng thuật toán sắp xếp đếm theo chữ số thứ i. Hãy nhớ rằng chúng tôi sử dụng sắp xếp theo số lượng vì đây là thuật toán sắp xếp ổn định

Thí dụ

Giải thích thuật toán sắp xếp Radix

Do đó, chúng tôi quan sát thấy rằng sắp xếp cơ số sử dụng sắp xếp đếm như chương trình con của nó trong suốt quá trình thực hiện. Bây giờ hãy xem triển khai C++ của nó

#include
using namespace std;

long getMax(long vec[], long n){
    long maxval = vec[0];
    for (long i = 1; i < n; i++)
        if (vec[i] > maxval)
            maxval = vec[i];
    return maxval;
}

void Count_Sort(long vec[], long n, long x){
    long res[n];
    long i, count[10] = {0};
    for (i = 0; i < n; i++)
        count[(vec[i] / x) % 10]++;
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (i = n - 1; i >= 0; i--) {
        res[count[(vec[i] / x) % 10] - 1] = vec[i];
        count[(vec[i] / x) % 10]--;
    }
    for (i = 0; i < n; i++)
        vec[i] = res[i];
}

void Radix_Sort(long vec[], long n){
    long m = getMax(vec, n);
    for (long x = 1; m / x > 0; x *= 10)
        Count_Sort(vec, n, x);
}

int main(){
    long vec[] = { 53, 89, 150, 36, 633, 233 };
    long n = sizeof(vec) / sizeof(vec[0]);
    Radix_Sort(vec, n);
    for(long i = 0; i < n; i++)
      cout << vec[i] << " ";
    return 0;
}

Thực hiện sắp xếp Radix

Thời gian phức tạp. O(d(n+b)), trong đó b đại diện cho cơ sở của phần tử mảng (ví dụ: 10 đại diện cho số thập phân)

Độ phức tạp không gian phụ trợ. O(n+d), trong đó d là số chữ số tối đa trong một phần tử mảng

Trường hợp sử dụng

• Radix sorting tìm ứng dụng trong tính toán song song
• Nó cũng được sử dụng trong thuật toán DC3 (Kärkkäinen-Sanders-Burkhardt) khi tạo mảng hậu tố

Hãy tự mình thử

Q. Cho hai mảng được sắp xếp (mảng1[] và mảng2[]) có kích thước M và N gồm các phần tử riêng biệt. Cho trước một giá trị Sum. Vấn đề là đếm tất cả các cặp từ cả hai mảng có tổng bằng Sum

Ghi chú. Cặp này có một phần tử từ mỗi mảng. [Hạn chế. Sử dụng Sắp xếp Cơ số]

Đầu vào

• n -> Kích thước của mảng (n>1)
• 'n' phần tử mảng bên dưới

đầu ra. Một dòng duy nhất biểu thị số lượng cặp được yêu cầu

P. S. Đừng quên chia sẻ cách tiếp cận của bạn với chúng tôi trong phần bình luận bên dưới

---

8. Sắp xếp theo nhóm

Bucket Sort là một kỹ thuật sắp xếp dựa trên so sánh hoạt động trên các phần tử mảng bằng cách chia chúng thành nhiều nhóm theo cách đệ quy và sau đó sắp xếp các nhóm này riêng lẻ bằng cách sử dụng một thuật toán sắp xếp riêng hoàn toàn. Cuối cùng, các thùng đã sắp xếp được kết hợp lại để tạo ra mảng đã sắp xếp

Tìm hiểu thuật toán Bucket Sort với mã giả

Chúng ta có thể thăm dò sâu hơn về hoạt động của sắp xếp nhóm bằng cách giả sử rằng chúng ta đã tạo một mảng gồm nhiều 'nhóm' (danh sách). Các phần tử hiện được chèn từ mảng chưa sắp xếp vào các "nhóm" này dựa trên thuộc tính của chúng. Các nhóm này cuối cùng được sắp xếp riêng biệt bằng cách sử dụng thuật toán sắp xếp chèn như đã giải thích trước đó

mã giả

Begin
   for i = 0 to size-1
      insert array[i] into the bucket indexed (size * array[i])
   done
   for i = 0 to size-1
      sort bucket[i] using insertion sort
   done
   for i = 0 to size-1
      Combine items of bucket[i] and insert in array in sorted order
   done
End

Chà, nếu bạn vẫn không chắc chắn về thuật toán sắp xếp nhóm, hãy quay lại và xem lại mã giả một lần nữa

.

.

Xong? . Bây giờ hãy xem nhanh cách thực hiện của nó bên dưới

#include
#define pb push_back
using namespace std;

void Bucket_Sort(float arr[], int n){
	vector bucket[n];
	for (int i = 0; i < n; i++) {
		int bi = n * arr[i];
		bucket[bi].pb(arr[i]);
	}
	for (int i = 0; i < n; i++)
		sort(bucket[i].begin(), bucket[i].end());
	int pos = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < bucket[i].size(); j++)
			arr[pos++] = bucket[i][j];
}

int main(){
	float arr[]= { 0.474, 0.582, 0.452, 0.6194, 0.553, 0.9414 };
	int n = sizeof(arr) / sizeof(arr[0]);
	Bucket_Sort(arr, n);
	cout << "Sorted array is \n";
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	return 0;
}

Thực hiện sắp xếp theo nhóm

Thời gian phức tạp

• Trường hợp xấu nhất. O(n*n)
• trường hợp trung bình. O(n + k)
• Trường hợp tốt nhất. O(n + k)

Độ phức tạp không gian phụ trợ. O(k), trường hợp xấu nhất

Trường hợp sử dụng

• Sắp xếp nhóm được sử dụng khi đầu vào được phân phối đồng đều trên một phạm vi
• Nó cũng được sử dụng cho các giá trị dấu phẩy động

Hãy tự mình thử

Q. Bạn được cung cấp hai mảng A và B có kích thước bằng nhau N. Nhiệm vụ là tìm giá trị nhỏ nhất của A[0] * B[0] + A[1] * B[1] +…+ A[N-1] * B[N-1], trong đó xáo trộn các phần tử của . [Hạn chế. Sử dụng Sắp xếp nhóm]

Đầu vào

• n -> Kích thước của mảng (n>1)
• 'n' phần tử mảng đại diện cho mảng đầu tiên
• 'n' phần tử mảng đại diện cho mảng thứ hai

đầu ra. Một dòng duy nhất đại diện cho tổng cần thiết

P. S. Cần giúp đỡ?

---

9. Sắp xếp lược

Sắp xếp lược khá thú vị. Trên thực tế, nó là một cải tiến so với thuật toán sắp xếp bong bóng. Nếu bạn đã quan sát trước đó, sắp xếp bong bóng sẽ so sánh các phần tử liền kề cho mỗi lần lặp lại

Nhưng đối với lược sắp xếp, các mục được so sánh và hoán đổi bởi một giá trị khoảng cách lớn. Giá trị khoảng cách co lại theo hệ số 1. 3 cho mỗi lần lặp lại cho đến khi giá trị khoảng cách đạt đến 1, tại thời điểm đó, nó dừng thực thi

Hệ số co rút này đã được tính toán theo kinh nghiệm là 1. 3 (sau khi thử nghiệm thuật toán Comb Sort trên hơn 2.00.000 mảng ngẫu nhiên) [Source. Wiki]

Hiểu thuật toán Sắp xếp theo lược với một ví dụ đơn giản

Giải thích thuật toán sắp xếp lược

Khá đơn giản phải không?

#include
using namespace std;
void Comb_Sort(long *vec, long size) {
   long gap = size;
   bool f = true;
   while(gap != 1 || f == true) {
      gap = (gap)/1.3;
      if(gap<1) gap = 1;
      f = false;
      for(long i = 0; i< size - gap; i++) {
         if(vec[i] > vec[i+gap]) {
            swap(vec[i], vec[i+gap]);
            f = true;
         }
      }
   }
}
int main() {
   long arr[10]={ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
   cout << "Array before Sorting: ";
   for(long i = 0; i < 10; i++)
      cout << arr[i] << " ";
   cout << endl;
   Comb_Sort(arr, 10);
   cout << "Array after Sorting: ";
   for(long i = 0; i < 10; i++)
      cout << arr[i] << " ";
   cout << endl;
}

Thực hiện sắp xếp theo lược

Thời gian phức tạp

• Trường hợp xấu nhất. O(n^2)
• trường hợp trung bình. O(n^2/2^p), trong đó p là số gia
• Trường hợp tốt nhất. O(n*logn)

Độ phức tạp không gian phụ trợ. Ô(1)

Trường hợp sử dụng

• Comb Sort loại bỏ các giá trị nhỏ ở cuối danh sách bằng cách sử dụng các khoảng trống lớn hơn
• Đó là một cải tiến đáng kể so với Sắp xếp bong bóng

Hãy tự mình thử

Q. Cho một mảng, tìm phần tử xuất hiện nhiều nhất trong đó. Nếu có nhiều phần tử xuất hiện với số lần tối đa, hãy in bất kỳ phần tử nào trong số đó. [Hạn chế. Sử dụng Sắp xếp theo lược]

Đầu vào

• n -> Kích thước của mảng (n>0)
• 'n' phần tử mảng bên dưới

đầu ra. Một dòng duy nhất biểu thị phần tử có tần số tối đa

P. S. Bạn có thích kỹ thuật sắp xếp này không?

---

10. Sắp xếp vỏ

Thuật toán sắp xếp Shell là một cải tiến so với thuật toán sắp xếp chèn trong đó chúng tôi sử dụng các phân vùng giảm dần để sắp xếp dữ liệu của mình

Trong mỗi lần vượt qua, chúng tôi giảm kích thước khoảng cách xuống một nửa giá trị trước đó cho mỗi lần vượt qua mảng. Do đó, đối với mỗi lần lặp, các phần tử mảng được so sánh bằng giá trị khoảng cách được tính toán và hoán đổi (nếu cần)

Hiểu thuật toán Shell Sort với mã giả

#include 
using namespace std;

void Selection_Sort(int vec[], int n){
	int i, j, pos;
	for (i = 0; i < n-1; i++){
		pos = i;
		for (j = i+1; j < n; j++)
		if (vec[j] < vec[pos])
			pos = j;
		swap(vec[pos], vec[i]);
	}
}

int main(){
	int vec[] = {25, 22, 27, 15, 19};
	int n = sizeof(vec)/sizeof(vec[0]);
	Selection_Sort(vec, n);
	cout << "Sorted array: \n";
	for (int i=0; i < n; i++)
		cout << vec[i] << " ";
	cout << endl;
	return 0;
}

0

Ý tưởng của sắp xếp vỏ là nó cho phép trao đổi các phần tử nằm cách xa nhau. Trong Shell Sort, chúng tôi sắp xếp mảng N cho giá trị lớn của N

Sau đó, chúng tôi tiếp tục giảm giá trị của N cho đến khi nó trở thành 1. Mảng được gọi là sắp xếp N nếu tất cả các mảng con của mọi phần tử thứ N đều được sắp xếp

Ở đây, kích thước khoảng cách = sàn (N/2) cho mỗi lần lặp

Cuối cùng, hãy xem triển khai C++ của nó

#include 
using namespace std;

void Selection_Sort(int vec[], int n){
	int i, j, pos;
	for (i = 0; i < n-1; i++){
		pos = i;
		for (j = i+1; j < n; j++)
		if (vec[j] < vec[pos])
			pos = j;
		swap(vec[pos], vec[i]);
	}
}

int main(){
	int vec[] = {25, 22, 27, 15, 19};
	int n = sizeof(vec)/sizeof(vec[0]);
	Selection_Sort(vec, n);
	cout << "Sorted array: \n";
	for (int i=0; i < n; i++)
		cout << vec[i] << " ";
	cout << endl;
	return 0;
}

1Triển khai Sắp xếp Shell

Thời gian phức tạp

• Trường hợp xấu nhất. Phụ thuộc vào kích thước khoảng cách
• trường hợp trung bình. Phụ thuộc vào kích thước khoảng cách
• Trường hợp tốt nhất. O(n*logn)

Độ phức tạp không gian phụ trợ. Ô(1)

Trường hợp sử dụng

• Sắp xếp chèn không hoạt động tốt khi các phần tử gần nhau cách xa nhau. Shell sort giúp giảm khoảng cách giữa các phần tử gần nhau
• Nó cũng được sử dụng khi đệ quy vượt quá giới hạn. Máy nén bzip2 nén nó

Hãy tự mình thử

Q. Cho một mảng số nguyên chưa sắp xếp. Viết chương trình loại bỏ các giá trị trùng lặp khỏi mảng chưa sắp xếp. [Hạn chế. Sử dụng Shell Sắp xếp]

Đầu vào

• n -> Kích thước của mảng (n>1)
• 'n' phần tử mảng bên dưới

đầu ra. Một dòng duy nhất đại diện cho mảng sửa đổi

---

Bây giờ bạn đã khám phá 10 thuật toán sắp xếp hàng đầu, tất cả những gì còn lại là trả lời một số câu hỏi cơ bản (thực tế chỉ có 3 câu hỏi). Điều này sẽ khó mất một phút

Q1. Thuật toán sắp xếp nào tốt nhất?

Nếu bạn đã quan sát, độ phức tạp về thời gian của Quicksort là O(n logn) trong trường hợp trung bình và tốt nhất và O(n^2) trong trường hợp xấu nhất

Nhưng vì nó chiếm ưu thế trong các trường hợp trung bình đối với hầu hết các đầu vào, nên Quicksort thường được coi là thuật toán sắp xếp “nhanh nhất”

Tuy nhiên, vào cuối ngày, thuật toán sắp xếp tốt nhất phụ thuộc vào bản chất của dữ liệu đầu vào của bạn (và người bạn hỏi)

quý 2. Thuật toán sắp xếp đơn giản nhất là gì?

Sắp xếp bong bóng được công nhận rộng rãi là thuật toán sắp xếp đơn giản nhất hiện có. Ý tưởng cơ bản của nó là quét qua toàn bộ mảng và so sánh các phần tử liền kề và hoán đổi chúng (nếu cần) cho đến khi danh sách được sắp xếp. Khá đơn giản phải không?

Q3. Bạn thích thuật toán sắp xếp nào hơn cho các danh sách được sắp xếp gần hết?

Khi nói đến việc sắp xếp dữ liệu gần như đã được sắp xếp, sắp xếp chèn là người chiến thắng rõ ràng, đặc biệt vì đã đến lúc độ phức tạp giảm xuống còn O(n) từ một con số khổng lồ O(n^2) trên một mẫu như vậy

Sắp xếp chèn chính trước cuộc phỏng vấn lớn tiếp theo của bạn

Tìm hiểu chi tiết về sắp xếp chèn và cách bạn có thể sử dụng nó một cách hiệu quả để sắp xếp tập dữ liệu của mình

Blog CrioHarshita Bansal

Mặt khác, các thuật toán sắp xếp hợp nhất hoặc sắp xếp nhanh không thích ứng tốt với dữ liệu được sắp xếp gần

Vâng, đó là về nó. Vào cuối ngày, bạn sẽ quyết định kỹ thuật sắp xếp nào phù hợp với mình nhất. Và vâng, đừng quên thử các bài tập thực hành đi kèm với mỗi kỹ thuật sắp xếp

Bây giờ bạn cảm thấy thoải mái như thế nào với việc sắp xếp?

Trước khi bạn tham gia cuộc phỏng vấn tiếp theo, hãy chắc chắn biết câu trả lời cho những câu hỏi Thuật toán sắp xếp thường gặp này. Nếu bạn đọc kỹ blog này, bạn đã sẵn sàng để đạt điểm tuyệt đối. Sẵn sàng để làm bài kiểm tra?

bắt đầu bài kiểm tra

---

Vượt ra ngoài các khóa học cấp chứng chỉ dựa trên video và bootcamp trực tuyến. Xây dựng sự tự tin mà bạn cần để trả lời các câu hỏi về Cấu trúc dữ liệu và Thuật toán trong cuộc phỏng vấn quan trọng tiếp theo và đạt được công việc mơ ước của bạn với tư cách là Nhà phát triển phụ trợ hoặc Nhà phát triển ngăn xếp đầy đủ - Được đảm bảo. Tìm hiểu làm thế nào

---

tài nguyên bổ sung

Đừng bỏ lỡ những tài nguyên học tập miễn phí tuyệt đối cần thiết cho tất cả các nhà phát triển

1. Hơn 100 lệnh Linux cần thiết bạn phải biết. Tải xuống bản PDF >>
2. Các phím tắt VScode hữu ích để trở thành lập trình viên Ninja. Tải xuống bản PDF >>
3. Lệnh Git Cheat Sheet. Tải xuống Cheat Sheet >>
4. Hơn 20 dự án công nghệ thú vị với hướng dẫn từng bước. Tải xuống dự án >>

---

Tìm thấy bài viết này thú vị?

Chúng tôi cũng rất muốn biết kỹ thuật sắp xếp khiến bạn hào hứng nhất - hãy cho chúng tôi biết trong phần bình luận bên dưới

Thuật toán sắp xếp hiệu quả nhất là gì?

Thuật toán sắp xếp nào tốt nhất và nhanh hơn?

Thuật toán sắp xếp nào là tốt nhất trong trường hợp tốt nhất?