Với mỗi giai đoạn được triển khai, chúng tôi sẽ hướng dẫn bạn các thuật toán sắp xếp khác nhau. Python sẽ là thành phần thực thi. Khi bạn có thuật toán, bạn có thể nhanh chóng tích hợp nó vào bất kỳ ngôn ngữ nào. Đây là chủ đề về cú pháp của ngôn ngữ. Hãy ngâm mình trong các thuật toán để sắp xếp.

Hiểu triển khai danh sách được liên kết bằng Python

Sắp xếp chèn

Một trong những thuật toán sắp xếp đơn giản nhất là kiểu chèn. Thực hiện rất dễ dàng. Và bạn sẽ phải sắp xếp thêm một mảng thời gian. Nó không được sử dụng để sắp xếp cho các mảng lớn hơn trong hầu hết các trường hợp. Kỹ thuật loại chèn giữ các phần con được sắp xếp trong bảng được cung cấp. Khi bắt đầu quá trình sắp xếp, phần con sắp xếp chỉ bao gồm phần tử đầu tiên. Trong mảng con đã sắp xếp, chúng ta chọn một phần tử từ mảng chưa được sắp xếp và chèn nó vào đúng vị trí. Độ phức tạp thời gian là O (n2) và độ phức tạp không gian là O (1).

def insertion_sort(arr, n):
	for i in range(1, n):
		current_position = i
		current_element = arr[i]
		while current_position > 0 and current_element <
		 arr[current_position - 1]:

			arr[current_position] = arr[current_position - 1]
			current_position -= 1
		arr[current_position] = current_element
if __name__ == '__main__':
	arr = [2, 3, 6, 7, 8, 9, 1, 4, 5]
	insertion_sort(arr, 9)
	print(str(arr))

Việc sắp xếp lựa chọn giống như việc chèn với một chút thay đổi. Nó cũng tách mảng thành các thành phần được phân loại và không được sắp xếp. Sau đó, chúng tôi chọn phần tử ít nhất từ ​​mỗi lần lặp từ phần con chưa được sắp xếp và chèn nó vào vị trí cuối cùng của phần con đã sắp xếp. Độ phức tạp thời gian là O (n2) và độ phức tạp không gian là O (1).

def selection_sort(arr, n):
	for i in range(n):
		min_element_index = i
		for j in range(i + 1, n):
			if arr[j] < arr[min_element_index]:
				min_element_index = j
		arr[i], arr[min_element_index] = arr[min_element_index], arr[i]
if __name__ == '__main__':
	arr = [2, 3, 6, 7, 8, 9, 1, 4, 5]
	selection_sort(arr, 9)
	print(str(arr))

Sắp xếp bong bóng là một thuật toán đơn giản. Nó liên tục hoán đổi các mục lân cận trên mỗi lần lặp cho đến khi sắp xếp xong mảng cần quan tâm. Nó đi ngang qua bảng điều khiển và đẩy phần tử hiện tại đến vị trí tiếp theo cho đến khi nó thấp hơn phần tiếp theo. Độ phức tạp thời gian O (n2) và độ phức tạp không gian là O (1).

def bubble_sort(arr, n):
	for i in range(n):
		for j in range(n - i - 1):
			if arr[j] > arr[j + 1]:
				arr[j], arr[j + 1] = arr[j + 1], arr[j]
if __name__ == '__main__':
	arr = [2, 3, 6, 7, 8, 9, 1, 4, 5]
	bubble_sort(arr, 9)
	print(str(arr))

Merge sort là một thuật toán sắp xếp mảng đệ quy. Về độ phức tạp thời gian, nó hiệu quả hơn so với các thuật toán đã trình bày trước đây. Nó tuân theo cách tiếp cận của sự phân chia và chinh phục. Thuật toán sắp xếp hợp nhất chia nhỏ và sắp xếp mảng thành hai phần riêng lẻ. Nó hợp nhất hai nửa thành một mảng được sắp xếp duy nhất sau khi sắp xếp xong. Nó chia mảng cho đến khi mảng trở thành loại dễ dàng nhất. Vì đây là một thuật toán đệ quy. Độ phức tạp thời gian là O (nlogn) và độ phức tạp không gian là O (1).

def merge(arr, left_index, mid_index, right_index):
	left_array = arr[left_index:mid_index+1]
	right_array = arr[mid_index+1:right_index+1]
	left_array_length = mid_index - left_index + 1
	right_array_length = right_index - mid_index
	i = j = 0
	k = left_index
	while i < left_array_length and j < right_array_length:
		if left_array[i] < right_array[j]:
			arr[k] = left_array[i]
			i += 1
		else:
			arr[k] = right_array[j]
			j += 1
		k += 1
	while i < left_array_length:
		arr[k] = left_array[i]
		i += 1
		k += 1
	while j < right_array_length:
		j += 1
		k += 1
def merge_sort(arr, left_index, right_index):
	if left_index >= right_index:
		return
	mid_index = (left_index + right_index) 
	merge_sort(arr, left_index, mid_index)
	merge_sort(arr, mid_index + 1, right_index)
	merge(arr, left_index, mid_index, right_index)
if __name__ == '__main__':
	arr = [2, 3, 6, 7, 8, 9, 1, 4, 5]
	merge_sort(arr, 0, 8)
	print(str(arr))