一、概述
我们常说的排序就是将一组数据按一定顺序排列起来，以便方便查询和处理。排序大致分为两类：内部排序和外部排序，区别在于是否需要访问外存。这里不展开讲解。
二、常见排序算法
1、冒泡排序法
博主认为冒泡排序可以算是一种接触地非常频繁的算法。其基本思想是：从后往前进行多次扫描，当发现相邻两个关键字的次序与排序要求不符时，将这两个数据进行位置交换。当然了，说得再多，还不如看个demo来得快。假设现有6个数据，需要将其按从小到大排序。为便于读者理解，直接上代码。
#include <stdio.h>
#include <stdlib.h>
#define ARRAYLENGTH 6
int main()
{
int temp; //temp为临时值
int data[ARRAYLENGTH] = {23, 15, 2, 92, 65, 132}; //需要排序的数据
//int flag = 0; //设置标志flag
for(int i = 0; i < ARRAYLENGTH - 1; i++) //总共6个数据，因此需要5次排序 ，每次冒泡按从后往前的顺序将最小的数据往前推
{
for (int j = ARRAYLENGTH - 1; j >= i; j--) //将相邻的数据进行，若前一个数据大于后一个就将两个数据交换位置
{
if(data[j-1] > data[j])
{
temp = data[j-1];
data[j-1] = data[j];
data[j] = temp;
//flag = 1; //若相邻数据交换位置，则将flag赋值为1
}
}
//if(flag == 0) break; //若flag为0，则跳出排序
//else flag = 0; //若flag为1，则将flag重置为0，并继续进行冒泡排序
}
for(int i = 0; i < 6; i++) //将得到排好序的数据输出
{
printf("%d ",data[i]);
}
system("pause");
return 0;
}
从上可以看出如果将长度为6的数据组排序需要5次冒泡，但如果两次冒泡后已经按要求排序，剩下的执行将做无用功。如何解决这个问题呢？我们可以加入一个初始值为0的标志flag。每次冒泡后，如有顺序改动将flag赋值为1。在执行完内循环后进行判断flag的值，若为1，则跳出循环。
2、快速排序法
快速排序法是一种对冒泡排序的改进。其基本思想：第一遍排序时，将数据组分为两组，一组比标准值大，一组比标准值小。再对这两组数据分别进行快速排序。这里涉及到了递归的概念。不多说，上代码。
#include <stdio.h>
#include <stdlib.h>
#define ARRAYLENGTH 6
int Division(int a[], int left, int right)
{
int base = a[left]; //设置基准值base为最左边的数
while(left < right)
{
while((left < right) && (a[right] > base)) //从右向左寻找第一个小于基准值的数
right--;
a[left] = a[right]; //将该数移到最左边
while((left < right) && (a[left] < base)) //从左向右寻找第一个大于基准值的数
left++;
a[right] = a[left]; //将该数移到最右边
}
a[left] = base; //将最小值设为基准
return left; //返回最小值的位置
}
void QuickSort(int a[], int left, int right) //快速排序
{
int i;
if(left < right)
{
i = Division(a,left,right); //分割数据
QuickSort(a,left,i-1);
QuickSort(a,i+1,right);
}
}
int main()
{
int temp; //temp为临时值
int data[ARRAYLENGTH] = {23, 15, 2, 92, 65, 132}; //需要排序的数据
QuickSort(data,0,ARRAYLENGTH-1); //进行快速排序
for(int i = 0; i < 6; i++) //将得到排好序的数据输出
{
printf("%d ",data[i]);
}
system("pause");
return 0;
}
3、简单选择排序法
简单选择排序，顾名思义，每一次排序，选择最小的数据输出。博主认为这比较符合人类的思想。举个简单的demo。
#include <stdio.h>
#include <stdlib.h>
#define ARRAYLENGTH 6
void SelectSort(int a[],int n) //简单选择排序
{
int i,j,k,temp;
for(i = 0; i < n-1; i++)
{
k = i;
for(j=i+1; j<n; j++)
if(a[k] > a[j]) k = j; //找出最小值的位置
temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
int main()
{
int temp; //temp为临时值
int data[ARRAYLENGTH] = {23, 15, 2, 92, 65, 132}; //需要排序的数据
SelectSort(data, ARRAYLENGTH); //简单选择排序
for(int i = 0; i < 6; i++) //将得到排好序的数据输出
{
printf("%d ",data[i]);
}
system("pause");
return 0;
}
本文暂时写到这里，在下一篇文章中，博主将讲述堆排序、直接插入排序、希尔排序、合并排序。