本文简单介绍了C语言的冒泡排序、选择排序、快速排序，结合本人的理解与使用做一下记录。
思想：（以小到大排序为例）假设一个数组有n个数，第一轮遍历这个数组的前（n-1）个数，遍历的时候比较当前位置和下一个位置的数，如果当前位置的数比较大，就跟下一个数交换位置；所以第一轮结束之后，就会把最大的数“沉”到数组的末尾位置；第二轮遍历这个数组的前（n-2）个数，按照前面的方法把第二大的数“沉”到数组的倒数第二个位置；依此类推，（n-1）轮之后每一个较大的数都按顺序沉到了数组的相应位置。
思想：使用for循环对数组进行排序；每循环一次，选择出一个较大的数，然后与
数组中的第n个位置交换数据，n从0开始。假设这个数组有n个数据，那么循环（n-1）次即可完成排序。
思想：
编写一个程序，随机生成10个整数并赋值给数组；然后分别使用冒泡排序、选择排序和快速排序对这个数组进行排序并打印出排序后的结果。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
void BubbleSort(int *a, int length) ;
void select_sort(int *array, int size);
void quick_sort(int *array, int low, int high);
#define SIZE 10
//#define SELECT_SORT
//#define BUBBLE_SORT
#define QUICK_SORT
int main(void)
{
int array[SIZE];
int i;
srand(time(0)); //设置随机数种子
//使用随机数初始化数组
for(i = 0; i < SIZE; i++)
{
array[i] = rand() % (50-3+1)+3; //生成[3,50]范围内的随机整数
}
printf("排序之前，数组为:");
for(i = 0; i < SIZE; i++)
{
printf("%d\t", array[i]);
}
printf("\n");
#ifdef SELECT_SORT
//使用选择排序对数组从大到小排序
select_sort(array, SIZE);
#elif defined BUBBLE_SORT
//选择冒泡排序对数组从小到大排序
BubbleSort(array, SIZE);
#else
//使用快速排序对数组从小到大排序
quick_sort(array, 0, SIZE-1);
#endif
printf("排序之后，数组变为:");
for(i = 0; i < SIZE; i++)
{
printf("%d\t", array[i]);
}
printf("\n");
return 0;
}
//冒泡排序
void BubbleSort(int *a, int length)
{
int temp;
for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - i - 1; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
//选择排序(非稳定版本)
void select_sort(int *array, int size)
{
int max;
int pos;
int i,j;
int tmp;
max = array[0];
pos = 0;
for(i = 0; i < size-1; i++) //循环一次就找到一个较大的数，然后与数组的第n个数据交换位置(n从0开始)
{
max = array[i];
pos = i;
for(j = i; j <= size-1; j++)
{
if(array[j] > max)
{
max = array[j];
pos = j;
}
}
//交换pos位置与i位置的数据
tmp = array[i];
array[i] = array[pos];
array[pos] = tmp;
}
}
//快速排序
void quick_sort(int *array, int low, int high)
{
if(low < high)
{
int i = low;
int j = high;
int key = array[low];
while(i < j) //两个游标重合，即可确定key的位置
{
while(i < j && array[j] > key) //从右往左找，找到一个小于等于key的数据，然后与key交换位置
{
j--;
}
if(i < j)
{
array[i++] = array[j]; //把找到的这个数放到key的位置
}
while(i < j && array[i] <= key) //从左往右找，找到一个大于key的数据，然后与key交换位置
{
i++;
}
if(i < j)
{
array[j--] = array[i]; //把找到的这个数放到key的位置
}
}
array[i] = key;
quick_sort(array, low, i-1);
quick_sort(array, i+1, high);
}
}
代码分析：
首先是使用srand函数设置随机数种子，time(0)是用来获取随机数种子；
然后使用rand函数产生随机数，赋值给数组元素；
如果要产生[m,n]范围内的随机数num，可用：
int num=rand()%(n-m+1)+m;
其中的rand()%(n-m+1)+m算是一个公式
上面的代码可以选择冒泡排序、选择排序或者选择快速排序，可以通过宏选择。
我有看过别人写的快速排序，我觉得有些操作是可以优化的；比如交换数据这一步，因为key的位置有可能一直在变，所以没必要每次都把key写到某个位置（过渡位置），只需要确定好最终位置再赋值。
当然，上面这个只是示例代码，还可以再封装、再优化，需要大家再斟酌一下。
下图是冒泡排序，对数组从小到大排序
zzc@zzc-virtual-machine:~/share$ ./1
排序之前，数组为:26 43 47 37 22 48 48 8 37 15
排序之后，数组变为:8 15 22 26 37 37 43 47 48 48
下图是选择排序，对数组从大到小排序
zzc@zzc-virtual-machine:~/share$ ./1
排序之前，数组为: 40 10 31 26 23 48 50 6 30 41
排序之后，数组变为:50 48 41 40 31 30 26 23 10 6
下图是快速排序，对数组从小到大排序
zzc@zzc-virtual-machine:~/share$ ./1
排序之前，数组为:33 30 24 27 23 41 29 9 8 4
排序之后，数组变为:4 8 9 23 24 27 29 30 33 41
我们可以对冒泡进行改良，一个数组中的数据可以分为有序数列和无序数列；排序过程中，有序数列处于数组的后半段，不需要再给它排序，只需要对无序数列进行排序。
另外，如果第一轮比较下来发现没有数据交换位置，那就表示整个数组已经排列好了，直接结束排序即可。
按照这个思路，我们来实现一个示例，如下：
//冒泡排序改良版
void BubbleSortNew(int *a, int length)
{
int temp;
//记录最后一次交换的位置
int last_exchange_index = 0;
//无序数列的边界，每次比较只需要比到这里
int sort_border = length - 1;
for (int i = 0; i < length - 1; i++)
{
bool isSorted = true;
for (int j = 0; j < sort_border; j++)
{
if (a[j] > a[j + 1])
{
isSorted = false; //有数据要交换位置，所以不是有序，标志置为false
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
last_exchange_index = j;
}
}
sort_border = last_exchange_index;
if(isSorted) //一轮下来是否发生数据交换，没有就退出排序
break;
}
}
实测对10000个随机数（范围为0到9999）进行排序，在笔者的主机环境中传统的冒泡花费了158237 个cpu clock，而改良版话费了151638 个cpu clock，节省了6599个cpu clock，所以效率上还是有所提高的。
常见算法时间复杂度如下图：
1、快速排序虽然效率较高、耗时短，但是一直压栈（数据量很大的时候）很容易造成堆栈溢出
2、排序算法应该尽量避免使用递归。
3、排序算法非常多，应该结合具体的应用场景来选择合适的算法。（从来没有最好的，只有最适合你的）
本文主要介绍了C语言中冒泡排序、选择排序和快速排序的思想，并进行了相应的代码实现和调试。
同时对冒泡排序进行了改良。