简介冒泡排序和快速排序

1、简介冒泡排序和快速排序徐丹 T21414018新闻传播学院大纲：算法简介常见排序算法冒泡算法（简介和性能介绍）冒泡排序的改进快速排序算法（分治法，简介和性能介绍）快速排序算法的改进总结算法的定义：定义良好的计算过程，取一个或一组值作为输入，并产生一个或一组值作为输出。算法是一系列计算步骤，用来将输入数据转换成输出结果。通常计算机解决问题遵循：输入解决输出的模式，因此算法是连接输入输出的纽带，它提供了解决问题的具体思路和方法。也可以说它指解题方案的准确而完整的描述，是一系列解决问题的清晰指令（计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指

2、令系统），算法代表着用系统的方法描述解决问题的策略机制。算法在解决问题时必须要结合一定的数据结构。它们是相辅相成，密不可分的整体。程序设计中的一个经典公式：程序设计算法数据结构正说明了这种融合的重要性。要通俗地理解算法，我们不妨回溯算法的历史，可以看到，算法由来已久，在遥远古代人们就用算法来解决数学问题和现实问题。这提供了一种思路：算法即解决问题的思想和方法。当算法与数据结构相互匹配，并通过适当的程序设计语言编译出来，就形成了有效的程序。算法拥有五大特征：有穷性（Finiteness）算法的有穷性是指算法必须能在执行有限个步骤之后终止；确切性(Definiteness)算法的每一步骤必须有确切

3、的定义；输入项(Input)一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；输出项(Output)一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；可行性(Effectiveness)算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。算法的评估主要经过时间复杂度，空间复杂度，正确性，可读性，健壮性。时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。T(n)=(f(n)

4、算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。（只考虑函数中去常数项最高阶），时间复杂度有最好和最坏情况的区分，通常最坏情况更有意义，因为这是算法时间复杂度的上限。而最好情况通常没有太大现实操作意义，因为它涵盖范围不够广泛，有时甚至会是特殊情况。空间复杂度算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。正确性：是评价一个算法优劣的最基本最重要的标准。可读性：一个算法可供人们阅读的容易程度。健壮性：一个算法对不合

5、理数据输入的反应能力和处理能力，也称为容错性。其中算法的时间复杂度和空间复杂度是主要的算法高效性指标。算法作为一种计算机科学的技术，它的效率体现在实现高效算法此算法能否节约有限的存储空间和运行时间，形成高效集约的解决方法。算法要素：一，数据对象的运算和操作：一个计算机的基本运算和操作有如下四类：1，算术运算：加减乘除等运算2，逻辑运算：或、且、非等运算3，关系运算：大于、小于、等于、不等于等运算4，数据传输：输入、输出、赋值等运算二，算法的控制结构：一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。 通常有顺序结构，选择结构和循环结构。算法的表现手法通常有：自然语言、

6、结构化流程图、伪代码和PAD图等，其中最普遍的是流程图。算法的方法通常有：递推法递归法穷举法贪心算法分治法动态规划法迭代法分支界限法回溯法。排序算法：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序分内排序和外排序。内排序:指在排序期间数据对象全部存放在内存的排序。外排序:指在排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内、外存之间移动的排序。内排序的方法有许多种,可归纳为五类:插入排序、选择排序、交换排序、归并排序、分配排序和计数排序。插入排序主要包括直接插入排序，折半插

7、入排序和希尔排序两种;选择排序主要包括直接选择排序和堆排序;交换排序主要包括冒泡排序和快速排序;归并排序主要包括二路归并(常用的归并排序)和自然归并。分配排序主要包括箱排序和基数排序。计数排序就一种。稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。其中冒泡,插入,基数,归并属于稳定排序;选择,快速,希尔,堆属于不稳定排序。冒泡算法它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成

8、。冒泡排序算法的运作如下：（从后往前）    比较相邻的元素。如果第一个比第二个大，就交换他们两个。    对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。    针对所有的元素重复以上的步骤，除了最后一个。    持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。（A0，A1，A2.An-1）有n个数i=0n-2,依次比较Aj和Aj+1(j=0n-i-2)如（5,2,4,3,7） i=0时，（【

9、2,5】,4,3,7）（2,【4,5】,3,7）（2,4,【3,5】,7）（2,4,3,【5,7】）i=1时（【2,4】,3,5,7）（2,【3,4】,5,7）（2,3,【4,5】,7）i=2时（【2,3】,4,5,7）（2,【3,4】,5,7）i=3时（【2,3】,4,5,7）i=0,比较次数为n-1i=1,比较次数为n-2.i=n-2,比较次数为1所以时间复杂度为O(2*(n-1)*n/2)=O（n2)最坏情况当已排序时，第一次为i=0,O(n-1)=O(n)最好情况依据上面的介绍我们可以看到，对冒泡排序可增加一个布尔变量，在每轮排序中判断是否已为排好序数列，若是则直接跳出算法省略多余步骤

10、。这样可以优化算法。 1.#include<stdio.h>  2.#include<stdlib.h>  3.#include<string.h>  4.void bubble_sort(int value, int length)  5.  6. int i = 0;  7. int j = 0; 

11、 8. int temp;  9. for(i = 1; i < length  i+)  10.   11.  for(j = 0; j< length - i; j+)  12.    13.   if (valu

12、ej > valuej+1)  14.     15.    temp = valuej;  16.    valuej = valuej + 1;  17.    valuej+1 = temp;  18.   

13、  19.  20.    21.   22.   23.  24.  25.  26.int main()  27.   28. int value8 = 1,10, 9, 20,29, 3, 10, 5;  29. 

14、int i = 0;  30. int length = 8;  31.  32. printf("Before:n");  33. for(i =0; i < length; i+)  34.   35.  if(i = length-1)  

15、;36.   printf("%dn", valuei);  37.  else  38.   printf("%dt", valuei);  39.   40.   41. bubble_sort(value, length);  42. printf("After:n&quo

16、t;);  43. for(i =0; i < length; i+)  44.   45.  if(i = length-1)  46.   printf("%dn", valuei);  47.  else  48.   printf("%

17、dt", valuei);  49.   50.   51. return 0;  快速排序算法快速排序由C. A. R. Hoare在1962年提出。它是冒泡排序的提升和改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法基于分治模式，而分治模式体现了递归的思想。对一个典型子

18、数组Ap,r排序的分治过程：分解：数组Ap,r被分成两个子数组Ap.q-1/Aq+1.r，使得Ap.q-1中的每个元素都小于等于A(q)，而且小于等于Aq+1.r中的元素。下标q也在这个划分过程中进行计算.解决：通过递归调用快排，对子数组Ap.q-1/Aq+1.r排序合并：因两个子数组是就地排序，将它们合并不需要操作。实现：QUICKSORT(A,p,r)if p<rthen q=PARTITION(A,p,r)QUICKSORT(A,p,q-1)QUICKSORT(A,q+1,r)为排序一个完整的数组，最初调用的是QUICKSORT(A,lengthA)主要内容：涉及分治在求解一个输入

19、规模为n，而n的取值又很大的问题时，直接求解往往非常困难。这时，可以先分析问题本身所具有的某些特性，然后从这些特性出发，选择某些适当的设计策略来求解。这种方法，就是所谓的分治法。分治法试用条件：1. 问题的规模缩小到一定的规模就可以较容易地解决。2. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。3. 合并问题分解出的子问题的解可以得到问题的解。4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题。分治法的步骤：1.分解：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。2. 解决：当问题的规模大于某个预定的阈值n0时，治理步

20、由k个递归调用组成。3. 合并：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。分治法通常见于快速排序和合并排序。算法内容是：设要排序的数组是A0AN-1，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。一趟快速排序的算法是：1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；2）以第一个数组元素作为关键数据，赋值给key，即ke

21、y=A0；3）从j开始向前搜索，即由后开始向前搜索(j-)，找到第一个小于key的值Aj，将Aj和Ai互换；4）从i开始向后搜索，即由前开始向后搜索(i+)，找到第一个大于key的Ai，将Ai和Aj互换；5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中Aj不小于key,4中Ai不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i=j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。语言实现：void sort(int *a, int left, int right) 

22、;   if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/            return ;        int i = left;    int j = right;    int key = aleft;        

23、 while(i < j)                               /*控制在当组内寻找一遍*/            while(i < j && k

24、ey <= aj)        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/                     j-;/*向前寻找*/&#

25、160;                        ai = aj;        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是        aleft，那么就是给key）*/   

26、;              while(i < j && key >= ai)        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/    &

27、#160;               i+;                         aj = ai;             ai = key;/*当在当组内找完一遍以后就把中间数key回归*/    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/ &