排序算法及MATLAB实现

排序算法排序例：对1、9、6、11、3这5个数字进行从小到大排序？结果：1、3、6、9、11思考：如何编程让计算机完成排序？？排序算法的种类：•1、冒泡排序（BubbleSort）•2、选择排序（SelectionSort）•3、插入排序（InsertionSort）•4、希尔排序（ShellSort）•5、归并排序（MergeSort）•6、快速排序（QuickSort）•7、堆排序（HeapSort）•8、计数排序（CountingSort）•9、桶排序（BucketSort）•10、基数排序（RadixSort）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、111、冒泡排序•MATLAB程序实现：X=[1,9,6,11,3];a=size(X,2);fori=1:aforj=1:a-1y=X(j);z=X(j+1);ifX(j)X(j+1)X(j)=z;X(j+1)=y;endendXend2、选择排序•原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。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、112、选择排序•MATLAB程序实现：X=[1,9,6,11,3,12,18];a=size(X,2);fori=1:ax=X(i:a);y=min(x);b=find(X==y);X(b)=X(i);X(i)=y;Xend3、插入排序•原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。3、插入排序•例：对1、9、6、11、3这5个数字进行从小到大排序？选择排序：（1）1、9、6、11、3（2）1、6、9、11、3（3）1、6、9、11、3（4）1、3、6、9、113、插入排序•MATLAB程序实现：•X=[1,9,6,11,3,12,18];•a=size(X,2);•forj=2:a•key=X(j);•i=j-1;•whilei0&&X(i)key•X(i+1)=X(i);•i=i-1;•end•X(i+1)=key;•X•end4、希尔排序•插入排序当原始数据比较有序时，效率非常高。但当原始数据无序时，效率比较低。•希尔排序是对插入排序的改进。•希尔排序目标：在进行排序之前让数据变得更为有序，提高排序效率。4、希尔排序•步骤：将待排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。4、希尔排序•例：利用希尔方法对592、401、874、141、348、72、911、887、820、283进行排序。5、归并排序•基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列。•在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。5、归并排序如何进行两路归并？将两个有序表的元素进行比较，小者复制到目标表中。5、归并排序5243574222()192330()ij()k5192324303574222两路归并动画演示ikjkjkikjk[s][m][t][m+1]5、归并排序•具体实现步骤假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……如此重复，直至得到一个长度为n的有序序列为止。5、归并排序初始时：[49][38][65][97][76][13][27]初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]6、快速排序•思考：利用冒泡排序将38、49、65、13、27完成排序需要几步？解：（1）3849651327（2）3849651327（3）3849136527（4）3849132765（5）3849132765（6）38134927656、快速排序（7）3813274965（8）3813274965（9）1338274965（10）1327384965冒泡算法最少需要10步。能否用更少的步数完成排序？6、快速排序•基本思想：（1）从数列中挑出一个元素，称为“基准”（2）所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（3）对上步分成的两端无序数组重复（1）和（2）步操作，直到完成排序。6、快速排序•例：利用快速排序将38、49、65、13、27完成排序？（1）选取38为基准，将大于38的值放右边，小的放左边：（2）在左边数组选取13为基准，重复上步（3）在右边数组选取49为基准，重复上步13273849656、快速排序•MATLAB实现•X=[1,9,6,11,3];•Sta=X(3);%基准•X1=X(XSta);•X2=X(XSta);•Sta1=X1(1);•X11=X1(X1Sta1);•X12=X1(X1Sta1);•Sta2=X2(1);•X21=X2(X2Sta2);•X22=X2(X2Sta2);•X=[X11Sta1X12StaX21Sta2X22]7、堆排序•堆的定义：若n个元素的序列{a1a2…an}满足则分别称该序列{a1a2…an}为小根堆和大根堆。7、堆排序•例:下面序列为堆，对应的完全二叉树分别为:987735625514354814483562559835779877356255143548(a)一个大根堆1448356255983577(b)一个小根堆9877356255143548(a)一个大根堆1448356255983577(b)一个小根堆小根堆大根堆7、堆排序•建堆在实际应用中，大多数数据构建的二叉树并不是堆，比如：解决方案：调整次序，构建大根堆或小根堆。7、堆排序•建堆例：7、堆排序•建堆例：将序列{28,25,16,36,18,32}构建成大根堆7、堆排序•堆排序原理若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值）……如此反复，便能得到一个有序序列，这个过程称之为堆排序。问题：如何在输出堆顶元素后，调整剩余元素为一个新的堆？7、堆排序问题：如何在输出堆顶元素后，调整剩余元素为一个新的堆？解决方案：输出堆顶元素之后，以堆中最后一个元素替代之，然后重新构建堆。7、堆排序•例题：用堆排序将序列{20,60,26,30,36,10}调整为递增序列。（1）构建小根堆7、堆排序（2）提取堆顶10，并用最后一个元素替换堆顶，重新构建小根堆。7、堆排序（3）提取堆顶20，并用最后一个元素替换堆顶，重新构建小根堆。7、堆排序（4）提取堆顶26，并用最后一个元素替换堆顶，重新构建小根堆。7、堆排序（5）提取堆顶30，并用最后一个元素替换堆顶，重新构建小根堆。（6）提取堆顶36，剩余一个数60，提取60。8、计数排序•排序原理：利用哈希的方法，将每个数据出现的次数都统计下来。哈希表是顺序的，所以我们统计完后直接遍历哈希表，将数据再重写回原数据空间就可以完成排序。8、计数排序•对一组数据进行排序做出图解：8、计数排序•MATLAB代码•X=[1,9,6,6,3,11,3,12,18];•x=max(X);•Y=[];•fori=0:x•a=find(X==i);•ifisempty(a)==1•continue•else•b=size(a,2)•y=i*ones(1,b);•Y=[Y,y];•end•end•Y