常见排序算法

《常见排序算法》由会员分享，可在线阅读，更多相关《常见排序算法（9页珍藏版）》请在装配图网上搜索。

1、常见排序算法(冒泡，选择，快速)的C语言实现要实现这几种算法的关键是要熟悉算法的思想。简单的说，冒泡排序，就如名字说的，每经过一轮排序，将最大 的数沉到最底部。选择排序的思想是将整个数列，分为有序区和无序区。每轮排序，将无序区里的最小数移入到 有序区。快速排序的思想是以一个数为中心，通常这个数是该数列第一个数，将整个数列分为两个部分，一个部 分是大于这个数的区域，一个部分是小于这个数的区域。然后再对这两个部分的数列分别排序。如果将数列分为 两个部分是通过，一方面从后向前的搜索，另一方面从前向后的搜索来实现的。具体的参考后面的来自百度百科 的文档。从这几个简单的排序算法上看，有几个特点：冒泡排序

2、是最简单的，也是最稳定的算法。选择排序不太稳定，但是效率上较冒泡还是有较大的提升。其实在分析的过程中就能发现，选择排序和冒泡排序 相比，中间少了很多的交换过程，和比较的次数，这个应该是时间较少的原因。选择排序能够满足一般的使用。 当比较的数超过以万为单位时，选择排序也还是要一点时间的。快速排序据说是最快的。这个可以从思想上看的出来。，当记录较多的时候，快速排序的比较循环次数比上面 2 个都要少。但是在具体的实现过程中，并不见得 如此。这是因为递归效率的低下导致的。当然，估计在实际使用 过的过程，快速排序估计都会使用非递归操作栈的方式来实现。那样应该会效率高伤不少。估计我会在后期出一 个快速排序

3、的非递归实现来真正比较它们 3个性能。在下面的程序中，可以通过调高 N 的数字就能看的出来冒 泡排序和选择排序性能的差异。在 N 较小，大概几百的时候，是看不出来的。 N 较大的的时候，比如 N=1000 或者N = 10000的时候，快速排序的递归实现就会卡死在那里了，出不了结果。以下是具体的代码：/* 常见排序算法比较*/#include #include #include #include #define N 10#define Demo 1void BubbleSort( int arr, int n);void SelectSort( int arr, int n);void Qui

4、ckSort( int arr, int n);void PrintArray( int arr, int n);void GenerateArray( int arr, int n);int main(int argc, char *argv)int arrN;GenerateArray(arr, N);#if Demoprintf(Before the bubble sortn );PrintArray(arr, N);#endifprintf(Start Bubble sortn );clock_t start_time1= clock (); /开始计时BubbleSort(arr,

5、N);clock_t end_time1= clock (); / 结束计时printf(Running time is: %lf msn , (double)(end_time1-start_time1)/C LOCKS_PER_SEC*1000);#if Demoprintf(After the bubble sortn );PrintArray(arr, N);#endifprintf(sleep(1000); / 单位是毫秒即千分之一秒GenerateArray(arr, N);#if Demoprintf(Before the selection sortn );PrintArray

6、(arr, N);#endifprintf(Start selection sortn );clock_t start_time2= clock (); /开始计时SelectSort(arr, N);clock_t end_time2= clock (); / 结束计时printf(Running time is: %lf msn , (double)(end_time2-start_time2)/C LOCKS_PER_SEC*1000);#if Demoprintf(After the selection sortn );PrintArray(arr, N);#endifprintf(s

7、leep(1000); / 单位是毫秒即千分之一秒GenerateArray(arr, N);#if Demoprintf(Before the quick sortn );PrintArray(arr, N);#endifprintf(Start quick sortn );clock_t start_time3= clock (); /开始计时QuickSort(arr, N);clock_t end_time3= clock (); / 结束计时/输出运行时间n);/输出运行时间n );printf(Running time is: %lf msn ,(double)(end_time3

8、-start_time3)/C LOCKS_PER_SEC*1000); /输出运行时间#if Demoprintf(After the quick sortn );PrintArray(arr, N);#endifsystem(PAUSE);return 0;/ 产生随机列表void GenerateArray( int arr, int n)int i;srand(unsigned)time(0);for(i = 0; i N; i+)arri = rand(); / 生成随机数 范围在 0-32767 之间/ 打印列表void PrintArray( int arr, int n)int

9、 i = 0;for(i = 0; i n; i+)printf(%6d, arri);printf(n);/ 经典冒泡排序void BubbleSort( int arr, int n)int i = 0, j =0;for(i = 0; i n; i+)for(j = 0; j arrj + 1)arrj = arrj人 arrj + 1;arrj+1 = arrj人 arrj + 1;arrj = arrj人 arrj + 1;/ 快速排序的递归实现void QuickSort( int arr, int n) if(n = 1) return;int i =0 , j = n - 1;

10、int key = arr0;int index = 0;while(i i & arrj key) j-;if(j = i)break ;else/交换 aj aiarrj = arrj人arri; arri = arrj人arri; arrj = arrj人arri; index = j;/ 从前向后搜索while(i j & arri key)i+;if(i = j) break;else/ 交换 ai ajarrj = arrj人arri; arri = arrj人arri; arrj = arrj人arri; index = i;QuickSort(arr, index);Quick

11、Sort(arr + index + 1, n - 1 - index);/ 选择排序void SelectSort( int arr, int n)int i, j;int min;for(i = 0; i n - 1; i+)int index = 0;min = arri;for(j = i + 1; j n; j+) / 找出 i+1 - n 无序区的最小者与 arri 交换if(arrj min)min = arrj;index = j;if(index != 0) /表明无序区有比 arri 小的元素arri = arri人arri ndex;arri ndex = arri人ar

12、ri ndex;arri = arri人arri ndex;程序里有几点注意的地方：一，在程序里，交换 2 个数，我使用了异或来处理。这个可以根据个人喜好。为了避免产生临时变量，可以使用 如下几种方式来交换 2 个数：a=a人b;b=a人b;a=a人b;或者a=a+b;b=a-b;a=a-b;使用第二种也挺好的。第一种异或的方式，只适用于，2个数都为int型的，a,b可以正可以负，这个没有关系， 但是必须是int类型。二, sleep()函数是包含在 windows.h 里面的，要加入 #include 三，关于随机数生成的2个函数srand()种子发生器函数，还有rand()随机数生成器函数

13、，自己可以参考相关 文档。四，Demo宏来控制是演示还是比较性能用的。当把N调整的很小，比如10的时候，可以设置Demo为1, 那样就能打印数组了，可以看到比较前后的情况。当把N调整到很大比如10000的时候，就把Demo设置为0, 那样就不打印数组，直接比较性能。具体的算法文档参考下面的：冒泡排序基本概念冒泡排序(BubbleSort)的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一 趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第 2个数和第3个数，将小数放前，大数 放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数

14、放到了最后。在 第二趟：仍从第一对数开始比较(因为可能由于第 2个数和第3个数的交换，使得第1个数不再小于第2个数) 将小数放前，大数放后，一直比较到倒数第二个数(倒数第一的位置上已经是最大的)，第二趟结束，在倒数第 二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去，重复以上过程，直至最终完成 排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。用二重循环实现，外循环变量设为i,内循环变量设为j。外循环重复9次，内循环依次重复9，8, .，1 次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用aj和aj+1标识,i的值依次为1

15、,2,.,9, 对于每一个 i, j 的值依次为 1,2,.10-i。产生 在许多程序设计中，我们需要将一个数列进行排序，以方便统计，而冒泡排序一直由于其简洁的思想方法而 倍受青睐。排序过程设想被排序的数组R 1.N 垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下 的原则，从下往上扫描数组R,凡扫描到违反本原则的轻气泡，就使其向上漂浮，如此反复进行，直至最后任 何两个气泡都是轻者在上，重者在下为止。算法示例A0 、 A1、 A2、 A3、 A4、 A5、 A6：49 38 65 97 76 13 27第一趟冒泡排序过程38 49 65 97 76 13 2738 49 6

16、5 97 76 13 2738 49 65 97 76 13 2738 49 65 76 97 13 2738 49 65 76 13 97 2738 49 65 76 13 27 97 -这是第一趟冒泡排序完的结果第二趟也是重复上面的过程，只不过不需要比较最后那个数 97，因为它已经是最大的38 49 65 13 27 76 97 - 这是结果第三趟继续重复，但是不需要比较倒数 2 个数了38 49 13 27 65 76 97选择排序基本思想n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果： 初始状态：无序区为R1.n，有序区为空。 第 1 趟排序在无序区R1.n中

17、选出关键字最小的记录Rk,将它与无序区的第1个记录R1交换，使R1.1和R2. n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 第 i 趟排序第i趟排序开始时，当前有序区和无序区分别为R1.i-1和R(1iX 的值， 6549,两者交换，此时： I=3 ）进行第三次交换后： 27 38 13 97 76 49 65（ 按照算法的第五步将又一次执行算法的第三步从后开始找进行第四次交换后： 27 38 13 49 76 97 65（按照算法的第四步从前面开始找大于X的值，9749,两者交换，此时：I=4,J=6 ）此时再执行第三步的时候就发现I=J,从而结束一趟快速排序，那么经

18、过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于 49的数全部在49的前面。快速排序就是递归调用此过程 在以 49 为中点分割这个数据序列，分别对前面一部分和后面一部分进行 类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对 于上述数组 A 的快速排序的全过程如图 6 所示：初始状态 49 38 65 97 76 13 27进行一次快速排序之后划分为 27 38 13 49 76 97 65分别对前后两部分进行快速排序 27 38 13 经第三步和第四步交换后变成 13 27 38 完成排序76 97 65 经第三步和第四步交换后变成 65 76 97 完成排序。