-
1、冒泡排序
• 原理：重复地走访过要排序的数列，一次比较 两个元素，如果它们的顺序错误就把它们交换 过来。走访数列的工作是重复地进行直到没有 再需要交换，也就是说该数列已经排序完成。
-
1、冒泡排序
•例：对1、9、6、11、3这5个数字进 行从小到大排序？
冒泡排序：
（1）1、6、9、11、3 （2）1、6、9、3、11 （3）1、6、3、9、11 （4）1、3、6、9、11
（1）选取38为基准，将大于38的值放右边， 小的放左边：
13 27 38 49 65 （2）在左边数组选取13为基准，重复上步 （3）在右边数组选取49为基准，重复上步
-
6、快速排序
•MATLAB实现 •X=[1,9,6,11,3]; •Sta=X(3); % 基准 •X1=X(X<Sta); •X2=X(X>Sta); •Sta1=X1(1); •X11=X1(X1<Sta1); •X12=X1(X1>Sta1); •Sta2=X2(1); •X21=X2(X2<Sta2); -
-
5、归并排序
❖ 如何进行两路归并？ 将两个有序表的元素进行比较，小 者复制到目标表中。
-
5、归并排序
两路归并动画演示
iii
( 5 24 35 74 222 )
[s]
[m]
jjjj
( 19 23 30 )
[m+1]
[t]
(
)
kk k
kk k
-
5、归并排序
•具体实现步骤 假设初始序列含有n个记录，则可看成
能否用更少的步数完成排序？
-
6、快速排序
•基本思想： （1）从数列中挑出一个元素，称为 “基准” （2）所有元素比基准值小的摆放在基准前 面，所有元素比基准值大的摆在基准的后 面
（3）对上步分成的两端无序数组重复（1） 和（2）步操作，直到完成排序。
-
6、快速排序
•例：利用快速排序将38、49、65、13、 27完成排序？
（2）38 49 65 13 27 （3）38 49 13 65 27 （4）38 49 13 27 65 （5）38 49 13 27 65 （6）38 13 49 27 65
-
6、快速排序
（7）38 13 27 49 65 （8）38 13 27 49 65 （9）13 38 27 49 65 （10）13 27 38 49 65 冒泡算法最少需要10步。
选择排序：
（1）1、9、6、11、3 （2）1、6、9、11、3 （3）1、6、9、11、3 （4）1、3、6、9、11
-
3、插入排序
•MATLAB程序实现：
•X=[1,9,6,11,3,12,18];
•a=size(X,2);
•for j=2:a
• key=X(j);
• i=j-1;
• while i>0 && X(i)>key
n个有序的子序列，每个子序列长度为1。 然后两两归并，得到n/2个长度为2或1 的有序子序列；再两两归并，……如此重 复，直至得到一个长度为n的有序序列为 止。
-
5、归并排序
初始时： [49] [38] [65] [97] [76] [13] [27] 初始关键字： [49] [38] [65] [97] [76] [13] [27]
•
X(i+1)=X(i);
•
i=i-1;
• end -
4、希尔排序
• 插入排序当原始数据比较有序时，效率非 常高。但当原始数据无序时，效率比较低。
• 希尔排序是对插入排序的改进。 • 希尔排序目标：在进行排序之前让数据变
得更为有序，提高排序效率。
-
4、希尔排序
• 步骤：将待排序列划分为若干组，在每一 组内进行插入排序，以使整个序列基本有 序，然后再对整个序列进行插入排序。
一趟归并后： [38 49] [65 97] [13 76] [27]
二趟归并后： [38 49 65 97] [13 27 76]
三趟归并后： [13 27 38 49 65 76 97]
-
6、快速排序
•思考：利用冒泡排序将38、49、65、 13、27完成排序需要几步？ 解：（1）38 49 65 13 27
-
1、冒泡排序
•MATLAB程序实现：
X=[1,9,6,11,3]; a=size(X,2); for i=1:a
for j=1:a-1 y=X(j); z=X(j+1); if X(j)>X(j+1) X(j)=z; X(j+1)=y; end
end X end
-
2、选择排序
• 原理：首先在未排序序列中找到最小（大） 元素，存放到排序序列的起始位置，然后， 再从剩余未排序元素中继续寻找最小（大） 元素，然后放到已排序序列的末尾。以此 类推，直到所有元素均排序完毕。
-
4、希尔排序
• 例：利用希尔方法 对592、401、874、 141、348、72、 911、887、820、 283进行排序。
-
5、归并排序
• 基本思想：将两个或两个以上的有序子序 列“归并”为一个有序序列。
• 在内部排序中，通常采用的是2-路归并排 序。即：将两个位置相邻的有序子序列归 并为一个有序序列。
-
2、选择排序
•例：对1、9、6、11、3这5个数字进 行从小到大排序？
选择排序：
（1）1、9、6、11、3 （2）1、3、6、11、9 （3）1、3、6、11、9 （4）1、3、6、9、11
-
2、选择排序
•MATLAB程序实现：
X=[1,9,6,11,3,12,18];
a=size(X,2);
for i=1:a
x=X(i:a);
y=min(x);
b=find(X==y);
X(b)=X(i);
X(i)=y;
X
-
3、插入排序
• 原理：通过构建有序序列，对于未排序数据， 在已排序序列中从后向前扫描，找到相应位置 并插入。
-
3、插入排序
•例：对1、9、6、11、3这5个数字进行从小到大 排序？
排序算法
-排序Βιβλιοθήκη 例：对1、9、6、11、3这5个数字 进行从小到大排序？ 结果：1、3、6、9、11 思考：如何编程让计算机完成排 序？？
-
排序算法的种类：
• 1、冒泡排序（Bubble Sort） • 2、选择排序（Selection Sort） • 3、插入排序（Insertion Sort） • 4、希尔排序（Shell Sort） • 5、归并排序（Merge Sort） • 6、快速排序（Quick Sort） • 7、堆排序（Heap Sort） • 8、计数排序（Counting Sort） • 9、桶排序（Bucket Sort） • 10、基数排序（Radix Sort）