TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu: Sắp xếp - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

Bài giảng Cấu trúc dữ liệu: Sắp xếp cung cấp cho người học những kiến thức như: Chọn trực tiếp (Selection Sort); Chèn trực tiếp (Insertion Sort); Nổi bọt (Bubble Sort); Merge Sort; Quick Sort; Heap Sort; Radix Sort. Mời các bạn cùng tham khảo! | TS. Lê Minh Trung Lương Trần Ngọc Khiết Khoa CNTT Đại học Sư phạm TP. HCM Nội dung Chọn trực tiếp Selection Sort Chèn trực tiếp Insertion Sort Nổi bọt Bubble Sort Merge Sort Quick Sort Heap Sort Radix Sort Khái niệm Sắp thứ tự Đầu vào một mảng Đầu ra mảng có thứ tự tăng hoặc giảm trên khóa Phân loại Sắp thứ tự ngoại external sort tập tin Sắp thứ tự nội internal sort bộ nhớ Giả thiết Sắp thứ tự nội Sắp tăng dần Chọn trực tiếp Input int a n Output mảng đã được sắp xếp Ý tưởng Với mỗi i 0 1 2 n-2 Tìm phần tử nhỏ nhất của mảng con a và hoán vị phần tử này với a i . Sorted Unsorted 23 78 45 8 32 56 Original List 8 78 45 23 32 56 After pass 1 8 23 45 78 32 56 After pass 2 After pass 3 8 23 32 78 45 56 8 23 32 45 78 56 After pass 4 After pass 5 8 23 32 45 56 78 Chọn trực tiếp Chọn trực tiếp void SelectionSort int a int n for int i 0 iĐánh giá chọn trực tiếp Vòng lặp for ngoài có n-1 lần lặp i 0 1 n-2 Số phép so sánh của lần lặp thứ i n-i-1 Số phép so sánh 2 1 0 1 1 2 1 2 Độ phức tạp của thuật toán 2 Chèn trực tiếp Insertion Sort Input int a n Output mảng đã được sắp xếp Ý tưởng Với mỗi i 1 2 n-1 Mảng con a đã được sắp thứ tự tăng chèn a i vào vị trí thích hợp để mảng con a sắp thứ tự tăng. Sorted Unsorted 23 78 45 8 32 56 Original List 23 78 45 8 32 56 After pass 1 23 45 78 8 32 56 After pass 2 After pass 3 8 23 45 78 32 56 8 23 32 45 78 56 After pass 4 After pass 5 8 23 32 45 56 78 Chèn trực tiếp Chèn trực tiếp void InsertionSort int a int n for int i 1 ix a j 1 a j j- if j -1 break a j 1 x Đánh giá chèn trực tiếp Vòng lặp for ngoài có n-1 lần lặp i 1 2 n-1 Tốt nhất 1 1 1 1 Xấu nhất 1 1 2 2 1 2 1 1 2 Trung bình 2 Nổi bọt Bubble Sort Input int a n Output mảng đã được sắp xếp Ý tưởng Với mỗi i n-1 n-2 1 Với mỗi j 0 1 i Nếu a j Nổi bọt sorted Bước 1 6 4 7 2 3 sorted Bước 2 4 6 2 3 7 sorted Bước 3 4 2 3 6 7 sorted Bước 4 2 3 4 6 7 Nổi bọt void BubbleSort int a int n for int i n-1 i gt 1 i- for int j 1 ja j int temp a j-1 a j-1 a j a j temp Đánh giá .

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu
• Data Structures
• Đánh giá chọn trực tiếp
• Bubble Sort
• Cải tiến Bubble Sort
• Giải thuật chia để trị
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cơ sở dữ liệu
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Kiểu dữ liệu cây
• Phân loại cây
• Bài giảng Maple
• Cấu trúc dữ liệu trong maple
• Cấu trúc dữ liệu dãy
• Cấu trúc dữ liệu tập hợp
• Cấu trúc dữ liệu mảng
• Cấu trúc dữ liệu bảng
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Cấu trúc dữ liệu cây AA
• Cây AA
• Biến đổi hiệu chỉnh cây AA
• Danh sách liên kết
• Thao tác duyệt cây
• Cấu trúc dữ liệu ngăn xếp
• Hàng đợi
• Biểu thức toán học
• Cây nhị phân
• Cấu trúc dữ liệu nâng cao
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Quan hệ giải thuật
• Cấu trúc dữ liệu tuyến tính
• Cách dùng con trỏ
• Cài đặt danh sách
• Các kiểu dữ liệu cơ bản
• Giải thuật tìm tuyến tính