冒泡排序、快速排序算法理解及C程序实现_实现冒泡排序和快速排序算法主函数怎么写

前言：关于 快速排序算法的相关理解，本文借鉴了 啊哈磊 老师的《常用排序——快速排序》 ，在此向作者 致敬，写的挺好。

目录

 

一、冒泡排序

二、快速排序

三、小结

---

一、冒泡排序

    冒泡排序是各种教材中 经常提到的一种排序 方法，基本思想就是：

    ① 从数组的头部开始，比较相邻两个数，如果第1个数比第2个数大，就交换他们两个。也就是让较大

  的数逐渐往后 移动，直到数组的末尾，经过第一轮的比较，就可以找到最大的元素，并将它移动到最后一个位置。

   ② 第一轮结束后，继续第二轮，仍然从数组的头部开始比较，直到数组的倒数第2个元素为止，经过第2轮比较，就可以找到次大的元素，并将它放到倒数第二个位置。

   ③ 一次类推，经过n-1轮“冒泡”后，就可以将所有的元素都排列好。

C程序代码如下：

/*
 * 冒泡排序函数。
 * 
 * src：数据源指针。
 *
 * n ： 数组大小。
 * 
 * 注意 ：经过排序后，会打乱 src 源数组，呈递增排序。
 */
void bubbleSort(int *src, int n)
{
	int i = 0, j = 0, tmp = 0;
	for(i = n - 1; i > 0; --i){
		for(j = 0; j < i; ++j){
			if(src[j] > src[j + 1]){
				tmp = src[j];
				src[j] = src[j + 1];
				src[j + 1] = tmp;     //数据交换
			}
		}
	}
}

二、快速排序

    快速排序是对冒泡排序的一种优化，平均效率较高，为什么说平均效率高呢？如果数组的元素大小是递减排列，那么快速排序法与冒泡法的效率是一样的，只有数组元素随机排列时，其平均效率才比较高。快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法。（分治翻译的不太容易理解，应该是 分段）。

该方法的基本思想是：

① 先从数组中取出一个数作为基准数（一般取第一个数）。

② 分区过程：将比这个数大的数全部放到它的右边，小于或等于它的数，全放到它的左边。

③ 经过步骤②，我们取的那个基数就在整个数组的中间某个位置（不一定正中间），将整个数组分成了两段，左边是小于基数的一段，而右边是大于基数的一段。然后再分别对左右两段区间重复步骤②，直到各个区 间只有一个数。

下面参考 啊哈磊 老师的讲解，再来分析一下，具体操作步骤：

 啊哈磊老师的 C 程序代码，需要定义好全局 数组缓冲 区，我对其进行了修改，可以作为一个通用的“快速排序”函数，程序代码如下：

/*
 * 快速排序算法 函数
 *
 * src : 要进行排序的数据指针。
 *
 * num ：数组元素个数
 *
 * 说明： 排序完成后，会改变src原来的数据顺序，数组元素呈递增排序。
 */
void quick_sort(int *src, int num)
{
	int i,j,t,temp;
	if(num < 2)
		return;
 
	temp = src[0];
	i = 0;
	j = num - 1;
 
	while(i != j){
		//from right to left- first
		while((src[j] >= temp) && (i < j))
			j--;
		//from left to right 
		while((src[i] <= temp) && (i < j))
			i++;
		//find ok
		if(i < j){
			t = src[i];
			src[i] = src[j];
			src[j] = t;
		}
	}
 
	src[0] = src[i];
	src[i] = temp;
 
	quick_sort(src, i);
	quick_sort(&src[i + 1], num - i - 1);
}

 程序测试可用。

三、小结

    快速排序算法的平均效率要高于冒泡排序算法，不过由于使用了递归的思路，所以对于数据量比较小的，还是使用冒泡排序算法，对于数据量比较大的，推荐使用快速排序算法。