一、 基本概念

· 排序：将一组数据（记录）按照某个关键字（如数字大小）以递增或递减的顺序重新排列的过程。

· 内部排序 vs. 外部排序：

  · 内部排序：所有排序操作都在内存中完成。

  · 外部排序：待排序数据量过大，无法全部加载到内存，需要借助外存（如硬盘）完成的排序。

二、 主要排序算法介绍

本章重点讲解以下四种排序算法

1. 冒泡排序 (Bubble Sort)

   · 核心思想：重复地遍历待排序序列，比较相邻元素，如果顺序错误就交换它们。每趟遍历都会将当前未排序部分中的最大（或最小）元素“浮”到其正确位置。

   · 特点：实现简单，但效率较低。

2. 选择排序 (Selection Sort)

   · 核心思想：不断从未排序序列中选择最小（或最大） 的元素，将其放到已排序序列的末尾。

   · 特点：相比冒泡排序，减少了交换次数，但效率依然不高。

3. 插入排序 (Insertion Sort)

   · 核心思想：将待排序元素插入到前方已经排好序的序列中的适当位置，直到全部插入完毕。

   · 特点：对于小规模数据或部分有序的数组非常高效。

4. 快速排序 (Quick Sort)

   · 核心思想：采用分治法。

     1. 分区：选取一个基准值，将数组划分为两部分，使得左边部分的所有元素都小于等于基准值，右边部分的所有元素都大于等于基准值。

     2. 递归：对左右两个子数组递归地执行快速排序。

   · 特点：在平均情况下效率非常高，是常用的高效排序算法之一。

三、 关键点回顾

· 每种算法都有其特定的核心思想和实现步骤。

· 算法的效率（时间复杂度、空间复杂度）各不相同，适用于不同的场景（数据规模、是否部分有序）。

· 希尔排序和归并排序在PPT中被列出但未详细展开，它们是更高效的改进算法。

四、练习

1.对数组[65,43,25,67,34,21,11,24,1,99]从小到大排序，采用冒泡排序和选择排序

2.对数组[65,43,25,67,34,21,11,24,1,99]从小到大排序，采用插入排序和快速排序