首页 > 代码库 > 算法:三种简单排序算法

算法:三种简单排序算法

    排序算法比较常见的有:冒泡排序、简单选择排序、直接插入排序;希尔排序、堆排序、归并排序和快速排序算法等。今天先学习一下前面三种比较简单的算法。排序的相关概念:

①排序的稳定性:两个或多个元素相等,排序过后仍然是原来的顺序则为稳定排序。

②内部排序:排序过程都在内存中进行;外部排序:需要对外存进行访问的排序过程。

③内排序算法性能因素:1、时间性能,比较与移动;2、辅助空间;3、算法复杂性


实例:冒泡排序、简单选择排序与直接插入排序

#include "stdio.h"

#define MAXSIZE 6

int data[MAXSIZE] = {0,5,4,3,2,1};

/*
*	功能:数组元素交换
*	输入:数据、交换元素的下标
*	输出:无	
*/
void swap(int data[],int i,int j)
{
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;	
}

/*
*	功能:冒泡排序
*	输入:数组
*	输出:无
*	算法:循环一次,下标所在位置即为最小值,不断地比较和移动
*/
void bubble1(int data[])
{
	for(int i = 0; i < MAXSIZE-1; i++)  
		for(int j = i+1; j < MAXSIZE ; j++)
			if(data[j] < data[i])  
				swap(data,i,j);
} 

/*
*	功能:改进冒泡排序
*	输入:数组
*	输出:无
*	算法:改进后的算法除了关注当前最小值外,还可以顺便移动其他较小值在前面
*/
void bubble2(int data[])
{
	int flag = 1;  // 标志位
	for(int i = 0; i < MAXSIZE-1 && flag; i++)
	{
		flag = 0;  // 每次循环标志位都赋为0
		for(int j = MAXSIZE - 1; j > i; j--)
			if(data[j] < data[j-1])  // 相邻两个元素之前的比较,而不是上面的算法只关注最小值。
			{
				swap(data,j-1,j);
				flag = 1;  // 当有发生移动时,才赋为1,否则排序已经完成,无需多余的比较。
			}
	}
}

/*
*	功能:简单选择排序
*	输入:数组
*	输出:无
*	算法:比较记录最小值的下标,最后才移动,而非每次都比较后就移动
*/
void simple(int data[])
{
	int min = 0;
	for(int i = 0; i < MAXSIZE-1; i++)
	{
		min = i;  // 假设第一个下标为最小值
		for(int j = i+1; j < MAXSIZE; j++)
		{
			if(data[j] < data[min])  // 当出现比第一个下标小的数据,记录其下标
				min = j;
		}
		if(min != i)  // 如果最小值不是第一个下标才交换
			swap(data,min,i);
	}
}

/*
*	功能:直接插入排序
*	输入:数组
*	输出:无
*	算法:将数据插入到已经排好序的有序表中,得到记录增1的有序表。
*/
void insertSort(int data[])
{
	for(int i = 2; i < MAXSIZE; i++)  // 第一次循环,排序为data[1],data[2]两个元素,data[0]是哨兵作用
	{
		if(data[i] < data[i-1])  // 如果data[2]比data[1]小,哨兵data[0]设为data[2]
		{
			data[0] = data[i];
			int j = i;
			while(data[j-1] > data[0])  // 当data[1] > data[0]时,将其右移即data[2] = data[1]
			{	
				data[j] = data[j-1];
				j--;
			}
			data[j] = data[0];  // data[1] = data[0],实现了data[1]和data[2]的交换,
								// 此时data[1]和data[2]即为排好序的有序表,开始第二次循环
		}
	}
}

void print(int *data)
{
	for(int i = 0; i < MAXSIZE; i++)
		printf("%d ",data[i]);
	printf("\n");
}

int main(int argc, char* argv[])
{
	print(data);
//	bubble1(data);
//	bubble2(data);
//	simple(data);
	insertSort(data);
	print(data);
}

    小结:三种简单排序算法的时间复杂性都是O(n^2),都是稳定的排序。



算法:三种简单排序算法