简介冒泡排序和快速排序

简介冒泡排序和快速排序

徐丹 T21414018 新闻传播学院

大纲： 算法简介

常见排序算法

冒泡算法（简介和性能介绍）

冒泡排序的改进——快速排序算法（分治法，简介和性能介绍） 快速排序算法的改进 总结

算法的定义：定义良好的计算过程，取一个或一组值作为输入，并产生一个或一组值作为输出。算法是一系列计算步骤，用来将输入数据转换成输出结果。通常计算机解决问题遵循：输入——解决——输出的模式，因此算法是连接输入输出的纽带，它提供了解决问题的具体思路和方法。也可以说它指解题方案的准确而完整的描述，是一系列解决问题的清晰指令（计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统），算法代表着用系统的方法描述解决问题的策略机制。算法在解决问题时必须要结合一定的数据结构。它们是相辅相成，密不可分的整体。程序设计中的一个经典公式：程序设计＝算法＋数据结构正说明了这种融合的重要性。要通俗地理解算法，我们不妨回溯算法的历史，可以看到，算法由来已久，在遥远古代人们就用算法来解决数学问题和现实问题。这提供了一种思路：算法即解决问题的思想和方法。当算法与数据结构相互匹配，并通过适当的程序设计语言编译出来，就形成了有效的程序。 算法拥有五大特征： 有穷性（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止； 确切性(Definiteness)

算法的每一步骤必须有确切的定义； 输入项(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件； 输出项(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

可行性(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

算法的评估主要经过时间复杂度，空间复杂度，正确性，可读性，健壮性。 时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。 T(n)=Ο(f(n))

算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time

Complexity）。（只考虑函数中去常数项最高阶），时间复杂度有最好和最坏情况的区分，通常最坏情况更有意义，因为这是算法时间复杂度的上限。而最好情况通常没有太大现实操作意义，因为它涵盖范围不够广泛，有时甚至会是特殊情况。 空间复杂度

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。 正确性：是评价一个算法优劣的最基本最重要的标准。 可读性：一个算法可供人们阅读的容易程度。

健壮性：一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。 其中算法的时间复杂度和空间复杂度是主要的算法高效性指标。算法作为一种计算机科学的技术，它的效率体现在实现高效算法——此算法能否节约有限的存储空间和运行时间，形成高效集约的解决方法。 算法要素：

一，数据对象的运算和操作：一个计算机的基本运算和操作有如下四类： 1，算术运算：加减乘除等运算 2，逻辑运算：或、且、非等运算

3，关系运算：大于、小于、等于、不等于等运算 4，数据传输：输入、输出、赋值等运算

二，算法的控制结构：一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。 通常有顺序结构，选择结构和循环结构。

算法的表现手法通常有：自然语言、结构化流程图、伪代码和PAD图等，其中最普遍的是流程图。

算法的方法通常有：递推法／递归法／穷举法／贪心算法／分治法／动态规划法／迭代法／分支界限法／回溯法。 排序算法：

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。 排序分内排序和外排序。

内排序:指在排序期间数据对象全部存放在内存的排序。

外排序:指在排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内、外存之间移动的排序。

内排序的方法有许多种,可归纳为五类:插入排序、选择排序、交换排序、归并排序、分配排序和计数排序。

插入排序主要包括直接插入排序，折半插入排序和希尔排序两种; 选择排序主要包括直接选择排序和堆排序; 交换排序主要包括冒泡排序和快速排序;

归并排序主要包括二路归并(常用的归并排序)和自然归并。 分配排序主要包括箱排序和基数排序。 计数排序就一种。

稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。

其中冒泡,插入,基数,归并属于稳定排序;选择,快速,希尔,堆属于不稳定排序。 冒泡算法

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 冒泡排序算法的运作如下：（从后往前）

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 （A0，A1，A2....An-1）有n个数 i=0~n-2,依次比较Aj和Aj+1(j=0~n-i-2) 如（5,2,4,3,7） i=0时，

（【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-1 i=1,比较次数为n-2 . . . .

i=n-2,比较次数为1

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

1.#include 2.#include 3.#include

4.void bubble_sort(int value[], int length) 5.{

6. int i = 0; 7. int j = 0; 8. int temp;

9. for(i = 1; i < length ; i++) 10. {

11. for(j = 0; j< length - i; j++) 12. {

13. if (value[j] > value[j+1]) 14. {

15. temp = value[j];

16. value[j] = value[j + 1]; 17. value[j+1] = temp; 18. } 19. 20. } 21. 22. } 23. 24. 25.}

26.int main() 27.{

28. int value[8] = {1,10, 9, 20,29, 3, 10, 5}; 29. int i = 0; 30. int length = 8; 31.

32. printf(\33. for(i =0; i < length; i++) 34. {

35. if(i == length-1)

36. printf(\37. else

38. printf(\39. } 40.

41. bubble_sort(value, length); 42. printf(\43. for(i =0; i < length; i++) 44. {

45. if(i == length-1)

46. printf(\47. else

48. printf(\49. }

50.

51. return 0; }

快速排序算法

快速排序由C. A. R. Hoare在1962年提出。它是冒泡排序的提升和改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法基于分治模式，而分治模式体现了递归的思想。 对一个典型子数组A[p,r]排序的分治过程：

分解：数组A[p,r]被分成两个子数组A[p..q-1]/A[q+1..r]，使得A[p..q-1]中的每个元素都小于等于A(q)，而且小于等于A[q+1..r]中的元素。下标q也在这个划分过程中进行计算. 解决：通过递归调用快排，对子数组A[p..q-1]/A[q+1..r]排序 合并：因两个子数组是就地排序，将它们合并不需要操作。 实现：

QUICKSORT(A,p,r) if p

then q=PARTITION(A,p,r) QUICKSORT(A,p,q-1) QUICKSORT(A,q+1,r)

为排序一个完整的数组Ａ，最初调用的是QUICKSORT(A,１,length[A]) 主要内容： 涉及分治

在求解一个输入规模为n，而n的取值又很大的问题时，直接求解往往非常困难。这时，可以先分析问题本身所具有的某些特性，然后从这些特性出发，选择某些适当的设计策略来求解。这种方法，就是所谓的分治法。 分治法试用条件：

1. 问题的规模缩小到一定的规模就可以较容易地解决。

2. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。 3. 合并问题分解出的子问题的解可以得到问题的解。

4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题。 分治法的步骤：

1.分解：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。 2. 解决：当问题的规模大于某个预定的阈值n0时，治理步由k个递归调用组成。

3. 合并：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。 分治法通常见于快速排序和合并排序。 算法内容是：

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。 Ｃ语言实现：

void sort(int *a, int left, int right) {

if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/ {

return ; }

int i = left; int j = right; int key = a[left];

while(i < j) /*控制在当组内寻找一遍*/ {

while(i < j && key <= a[j])

/*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升

序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ {

j--;/*向前寻找*/ }

a[i] = a[j];

/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是 a[left]，那么就是给key）*/

while(i < j && key >= a[i])

/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反， 因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/ {

i++; }

a[j] = a[i]; }

a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/

sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/ sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/ /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/ 快排的优化： 三平均分区法

与一般的快速排序方法不同，它并不是选择待排数组的第一个数作为中轴，而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说，主要有两点优势：

（1） 首先，它使得最坏情况发生的几率减小了。

（2） 其次，未改进的快速排序算法为了防止比较时数组越界，在最后要设置一个哨点。

具体操作方法有：根据分区大小调整算法，不同分区不同方案，并行的快速排序 快排变种：随机化快排，平衡快排，外部快排和三路基数快排 总结

算法是解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。与数据结构完美结合的算法能够高效解决计算机现实问题。通过算法的学习，我增强了对计算机的理性认知，初步明白了一些基本的知识，同时也锻炼了自己的思维能力，已经有“算法”意识，无论是在现实生活中还是在解题过程中，我都会时不时想起“算法”的思想，用策略达到问题的最优解。我想，在算法学习中我还是受益匪浅的。这种影响可能也是终身的。感谢算法。

其次，不同的排序算法大大开阔了我的眼界，让我了解到算法的世界很博大，问题的解决方法远远不止一种，而算法的目的很大程度在于算法的高效实现，因此对比特定数据结构和问题下的算法设计，我们总可以得到问题的最优解或者问题的较优解。排序的相关算法从一个更为微观的角度阐释了算法的思想和精髓。

最后，我想说，算法这种计算机科学博大精深，值得我们认真探寻其中的奥秘和求索其中的精髓。当我们快乐地深入了解学习算法时，我们会更加沉浸其中，获得非凡的乐趣和广博的知识和视野。身为非计算机专业的学生，能够通过算法及其高效实现这门课接触到基础的算法知识，我感到十分荣幸，今后有机会我将会更加深入了解这门精深而无比吸引人的科学。 参考：《算法导论》百度等

本文来源：https://www.bwwdw.com/article/o9ud.html